Fibonacci数列的递归算法

来自计算思维百科
跳转至: 导航搜索

1202年,意大利数学家斐波那契出版了他的《算盘全书》。他在书中提出了一个关于兔子繁殖的问题:如果一对兔子每月能生一对小兔(一雄一雌),而每对小兔在他出生后的第三个月里,又能开始生一对小兔,假定在不发生死亡的情况下,由一对出生的小兔开始,50月后会有多少对兔子?

显然,第一个月只有一对兔子,第二个月仍只有一对兔子,第三个月兔子对数为第二个月兔子对数加第一月兔子新生的对数。同理,第i个月兔子对数为第i-1月兔子对数加第i-2月兔子新生的对数。即从第一个月开始计算,每月兔子对数依次为: 1,1,2,3,5,8,13,21,34,55,89,144,233…,此数列称为Fibonacci'数列('Fibonacci'Sequence'),也称兔子数列。

根据上述分析,可按如下公式递归地定义Fibonacci数列(Fi):

Fibonacci数列递归实现的伪代码如下:     9.2.3.png

输入:正整数n

输出:Fibonacci数列的第n项

Fib(n)                              

1  IF n≤2

2 THEN RETURN 1                      

3  RETURN Fib(n-1)+Fib(n-2)    //调用自身                       

Fibonacci数列也称黄金分割数列,因为其相邻两项的比值越来越趋近黄金分割比例0.6180339887…。Fibonacci数列在现代物理、化学、经济等领域都有直接应用。它与自然界的许多现象也有很多巧合,如与植物花瓣、叶、径等,许多植物的花瓣、叶等呈现着Fibonacci数列特性。斐波那契以兔子问题猜中了大自然的奥秘。

                         9.2.4.png


                                        图1  Fib(5)的调用图

通过图1可以理解Fibonacci数列对自身的调用。图1给出了n=5时,Fib(5)的计算过程。从图中可以看出,为计算Fib(5),需计算Fib(4)、Fib(3),为计算Fib(4),需计算Fib(3)和Fib(2),依次调用下去,直到Fib(1)或Fib(0)。

图1中有些值被重复计算多次,如Fib(2)、Fib(3)、Fib(1)、Fib(0)。当n更大时,这种重复计算越来越严重,因此,Fibonacci数列递归算法的效率很低。