首页 > 代码库 > 谨慎地使用递归之斐波那契递归实现的分析

谨慎地使用递归之斐波那契递归实现的分析


【斐波那契函数的定义】

    斐波那契数列,又称黄金分割数列,指的是这样一个数列:1、1、2、3、5、8、13、21、……在数学上,斐波纳契数列以如下被以递归的方法定义:F0=1,F1=1,Fn=F(n-1)+F(n-2)(n>=2,n∈N*)。

【用递归求解斐波那契函数的弊端】

    斐波那契函数用递归实现如下面的代码:


wKioL1P8jbyiUwf8AABfC3Xjldc436.jpg



    计算斐波那契的自然递归程序效率时很低的,上面的程序虽然写法简单,看上去时递归的聪明的使用,但其实效率是及其低下的。特别是当n=40以后,效率衰减的特别明显。为了计算 fib( n ) ,需存在一个对 fib( n - 1 ) 和 fib( n - 2 ) 的调用,然而,由于计算F fib( n - 1 )又需要递归地调用 fib( n - 2 ) fib( n - 3 ),因此 fib( n - 2 ) 被计算了两遍,跟踪整个算法,可以发现 fib( n - 3 )被计算了33次,fib( n - 4 )被计算了55次,fib( n - 5 )被计算了88次。

    wKioL1P8ki_CuEfFAADpqGfRtwg006.jpg


                             图例-跟踪斐波那契数的递归计算

    程序之所以效率低下是因存在大量的冗余的工作要做,这违反了合成效益法则(求解一个问题的同一实例是,切勿在不同的递归调用中做重复性工作),在第一次调用fib( n - 1 )时,其实在某处已经计算了fib( n - 2 ),fib( n - 2 )的信息没有被存储,导致f调用fib( n - 2 )时,又做了重复性计算,这样递归重复冗余的计算导致巨大的运行时间。


【用for循环计算代替递归】

    由于计算 fib( n ) 所需要的是 fib( n - 1 )和fib( n - 2 ),因此,把最近算出2个的斐波那契数记录下来,以避免重复的计算。for循环计算斐波那契数代码如下:

wKiom1P8kiqAWIQIAADDRKL9IcQ935.jpg

【使用递归的四条基本法则】

    使用递归时编写程序时,要遵循以下4条法则,不然很容易编写出效率很低程序。

    11、基准情形。必须总要有某些基准情形,它无需递归就能解出。

    2、不断推进、对于需要使用递归求解的情形、每一次递归调用必须都必须使状况向一种基准情形推进。

    3、设计法则。假设所有递归都能运行。

    4、合成效益法则。 求解一个问题的同一实力时,切勿在不同的递归调用中做重复性工作。

    


谨慎地使用递归之斐波那契递归实现的分析