python实现斐波那契数列：迭代和递归对比
迭代和递归从概念上讲，递归就是指程序调用自身的编程思想，即一个函数调用本身；迭代是利用已知的变量值，根据递推公式不断演进得到变量新值得编程思想。
对于刚入门的编程小白而言，对递归的理解应该是要难于对迭代的理解的。下面将以python实现斐波那契数列为例，对比说明迭代和递归的区别。
斐波那契数列
斐波那契数列（Fibonacci sequence），又称黄金分割数列，指的是这样一个数列：F(0)=0，F(1)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）。在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用
1.迭代实现
迭代算法实现代码为：
#!/usr/bin/python
# coding=utf-8
from timeit import timeit
def fib(n):
list =
if n > 2:
for i in range(2,n,1):
listNew = list + list
list.append(listNew)
return list
n = 35
print('第%d个斐波那契数为%d'%(n,fib(n)))
t = timeit('fib(%d)'%n, 'from __main__ import fib', number=1)
print('递归所需时间%fs'%t)
输出结果为：
第35个斐波那契数为9227465
递归所需时间0.000016s2.递归实现递归算法实现代码为：#!/usr/bin/python
# coding=utf-8
from timeit import timeit
def fib(n):
if n == 1 or n == 2:
return 1
return fib(n - 1) + fib(n - 2)
n = 35
print('第%d个斐波那契数为%d'%(n,fib(n)))
t = timeit('fib(%d)'%n, 'from __main__ import fib', number=1)
print('递归所需时间%fs'%t)
输出结果为：第35个斐波那契数为9227465
递归所需时间4.570864s结论用python实现递归算法，代码结构较为简单，但效率非常低下，而迭代算法可读性强，执行效率也非常之快。所以在运用递归算法时应谨慎。
页:
[1]