home1.gif

说明： 斐波那契数列（Fibonacci sequence），又称黄金分割数列，是意大利数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）在《计算之书》中提出一个在理想假设条件下兔子成长率的问题而引入的数列，所以这个数列也被戏称为”兔子数列”。斐波那契数列的特点是数列的前两个数都是1，从第三个数开始，每个数都是它前面两个数的和，形如：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …。斐波那契数列在现代物理、准晶体结构、化学等领域都有直接的应用。

1. 分析/思路

Fib number: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

分析

  • 设数列第 n 项为 f(n)，则有 f(n) = f(n-1) + f(n-2)
  • 从数列看出，当 n =< 2时，有 f(1) = 1，f(2) = 1；当 n > 2 时，有 f(n) = f(n-1) + f(n-2)

2. 程序

【实例 1-1】迭代实现 生成斐波那契数列的前 n 个数

  1. def fib(n):
  2.     pre, cur = 0, 1
  3.     res = []
  4.     for i in range(n):
  5.         res.append(cur)
  6.         pre, cur = cur, pre + cur
  8.     return res

【实例 1-2】生成器实现 生成斐波那契数列的前 n 个数

  1. def f(n):
  2.     pre, cur = 0, 1
  3.     res = []
  4.     for i in range(n):
  5.         yield cur
  6.         pre, cur = cur, pre + cur
  8. res_obj = f(n)
  9. res = [x for x in res_obj]

【实例 1-3】递归实现 生成斐波那契数列的前 n 个数

  1. def f(n):
  2.     if n == 1 or n ==2:
  3.         return 1
  4.     return f(n-1) + f(n-2)
  6. def fib(n):
  7.     res = []
  8.     for i in range(1, n + 1):
  9.         res.append(f(i))
  11.     return res

思考：

迭代方法和生成器实现方法差不多，循环微复杂一些，但只要不是死循环就没有太大问题。递归方法，函数简单易懂，但它的效率呢？ 递归函数 f() 只能获取最外层的调用，内部递归结果都是中间结果，且为了第 n 项需要 2n 次递归（f(n-1)、f(n-2)）。如果是获取斐波那契数列的话，还需要在外面再套一层循环，效率就更低了。

还有，递归有深度限制，如果递归复杂，函数反复压栈，栈内存会很快溢出。

思考：递归实现能否提高性能呢 ？

改进递归，将迭代循环的思想应用进去，将前一次的计算结果作为下一次递归的实参，这样实现

【实例 1-4】递归实现 生成斐波那契数列的前 n 个数

  1. def fib(n, pre=0, cur=1, res=[]):
  2.     res.append(cur)
  3.     pre, cur = cur, pre + cur
  4.     if n == 1:
  5.         print(res)
  6.         return
  7.     fib(n-1, pre, cur, res)

注意，上面的 fib() 返回的是 None，数列只是通过 print 函数打印出来的。

2. 扩展

end1.gif