python实现斐波那契数列:迭代和递归对比

0
回复
5435
查看
[复制链接]

209

主题

26

回帖

1424

积分

超级版主

积分
1424
来源: 2020-6-15 06:40:03 显示全部楼层 |阅读模式
迭代和递归
从概念上讲,递归就是指程序调用自身的编程思想,即一个函数调用本身;迭代是利用已知的变量值,根据递推公式不断演进得到变量新值得编程思想。
对于刚入门的编程小白而言,对递归的理解应该是要难于对迭代的理解的。下面将以python实现斐波那契数列为例,对比说明迭代和递归的区别。

斐波那契数列
斐波那契数列(Fibonacci sequence),又称黄金分割数列,指的是这样一个数列:F(0)=0,F(1)=1, F(n)=F(n-1)+F(n-2)(n>=2,n∈N*)。在现代物理、准晶体结构、化学等领域,斐波纳契数列都有直接的应用

1.迭代实现
迭代算法实现代码为:
  1. #!/usr/bin/python
  2. # coding=utf-8

  3. from timeit import timeit

  4. def fib(n):
  5.     list = [1,1]
  6.     if n > 2:
  7.        for i in range(2,n,1):
  8.             listNew = list[i - 2] + list[i - 1]
  9.             list.append(listNew)
  10.     return list[n - 1]
  11. n = 35
  12. print('第%d个斐波那契数为%d'%(n,fib(n)))
  13. t = timeit('fib(%d)'%n, 'from __main__ import fib', number=1)
  14. print('递归所需时间%fs'%t)
复制代码
输出结果为:
  1. 第35个斐波那契数为9227465
  2. 递归所需时间0.000016s
复制代码
2.递归实现

递归算法实现代码为:

  1. #!/usr/bin/python
  2. # coding=utf-8

  3. from timeit import timeit

  4. def fib(n):
  5.     if n == 1 or n == 2:
  6.         return 1
  7.     return fib(n - 1) + fib(n - 2)
  8. n = 35
  9. print('第%d个斐波那契数为%d'%(n,fib(n)))
  10. t = timeit('fib(%d)'%n, 'from __main__ import fib', number=1)
  11. print('递归所需时间%fs'%t)
复制代码

输出结果为:

  1. 第35个斐波那契数为9227465
  2. 递归所需时间4.570864s
复制代码
结论

用python实现递归算法,代码结构较为简单,但效率非常低下,而迭代算法可读性强,执行效率也非常之快。所以在运用递归算法时应谨慎。


回复

使用道具 举报

您需要登录后才可以回帖 登录 | 免费注册
关注微信