3.2.2 实践演练——解决“斐波那契数列”问题

为了说明递归算法的基本用法，接下来将通过一个具体实例的实现过程，详细讲解递归算法思想在编程过程中的基本应用。

1．问题描述

斐波那契数列因数学家列昂纳多·斐波那契以兔子繁殖为例而引入，故又称为“兔子数列”。一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔子都不死，那么一年以后可以繁殖多少对兔子？

2．算法分析

以新出生的一对小兔子进行如下分析。

（1）第一个月小兔子没有繁殖能力，所以还是一对。

（2）2个月后，一对小兔子生下一对新的小兔子，所以共有两对兔子。

（3）3个月以后，老兔子又生下一对，因为小兔子还没有繁殖能力，所以一共是3对。

……

依此类推，可以列出关系表，如表3-1所示。

表3-1 月数与兔子对数关系表

表中的数字1，1，2，3，5，8，…构成一个数列，这个数列有个十分明显的特点：前面相邻两项之和，构成后一项。对这个特点的证明：每月的大兔子数为上月的兔子数，每月的小兔子数为上月的大兔子数，某月兔子的对数等于前面紧邻两个月兔子对数的和。

由此可以得出具体算法，如下所示：

设置初始值为F0=1，第1个月兔子的总数是F1=1。

第2个月兔子的总数是F2=F0+F1。

第3个月兔子的总数是F3=F1+F2。

第4个月兔子的总数是F4=F2+F3。

……

第n个月兔子的总数是Fn=Fn−2+Fn−1。

3．具体实现

在下面的实例文件di.py中，演示了使用递归算法计算斐波那契数列的第n项值的过程。

源码路径：daima\第3章\di.py

fib_table = {}
def fib_num(n):
     if (n <= 1):
           return n
     if n not in fib_table:
           fib_table[n] = fib_num(n - 1) + fib_num(n - 2)
     return fib_table[n]
n=int(input("输入斐波那契数列的第n项 \n"))
print("斐波那契数数列的第", n, "项是", fib_num(n))

执行后会输出：

输入斐波那契数列的第n项
4
斐波那契数数列的第4项是3