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

quant001

迭代和递归
从概念上讲，递归就是指程序调用自身的编程思想，即一个函数调用本身；迭代是利用已知的变量值，根据递推公式不断演进得到变量新值得编程思想。
对于刚入门的编程小白而言，对递归的理解应该是要难于对迭代的理解的。下面将以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. 
   
4. from timeit import timeit
   
5. 
   
6. def fib(n):
   
7.     list = [1,1]
   
8.     if n > 2:
   
9.        for i in range(2,n,1):
   
10.             listNew = list[i - 2] + list[i - 1]
    
11.             list.append(listNew)
    
12.     return list[n - 1]
    
13. n = 35
    
14. print('第%d个斐波那契数为%d'%(n,fib(n)))
    
15. t = timeit('fib(%d)'%n, 'from __main__ import fib', number=1)
    
16. print('递归所需时间%fs'%t)
    

复制代码

输出结果为：

1. 第35个斐波那契数为9227465
   
2. 递归所需时间0.000016s

复制代码

2.递归实现

递归算法实现代码为：

1. #!/usr/bin/python
   
2. # coding=utf-8
   
3. 
   
4. from timeit import timeit
   
5. 
   
6. def fib(n):
   
7.     if n == 1 or n == 2:
   
8.         return 1
   
9.     return fib(n - 1) + fib(n - 2)
   
10. n = 35
    
11. print('第%d个斐波那契数为%d'%(n,fib(n)))
    
12. t = timeit('fib(%d)'%n, 'from __main__ import fib', number=1)
    
13. print('递归所需时间%fs'%t)
    

复制代码

输出结果为：

1. 第35个斐波那契数为9227465
   
2. 递归所需时间4.570864s

复制代码

结论

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