当前位置: 首页 >> 程序设计 >> 从斐波那契数列看递归的性能

从斐波那契数列看递归的性能

作者：来源：zz 发表时间：2007-11-09 浏览次数：字号：大 中 小

所谓的斐波那契数列,就是形如:1,1,2,3,5,8,........即这个数列从第三项开始，每一项都等于前两项之和。
要取得第N项的数值,用普通方法:
PHP代码:
function fibo($n){
        $array = array(1,1);
        if ($n > 2){
                for ($i=2;$i<$n;$i++){
                        $array[] = $array[$i-1] + $array[$i-2];
                }
        }
        return $array[$n-1];
}

用递归方法:
PHP代码:
function fibo_r($n){
    if ($n<=2){
        return 1;
    }
    elseif($n>2){
        return fibo_r($n-1)+fibo_r($n-2);
    }
}

现在来对比性能(从N=3开始,每种方法运算5次取平均值,时间为秒,精确到小数点后6位):
N      fibo($n)     fibo_r($n)
-------------------------------
3      0.000070     0.000053
4      0.000071     0.000058
5      0.000072     0.000070
6      0.000073     0.000087
7      0.000074     0.000112
8      0.000077     0.000154
9      0.000078     0.000223
10     0.000080     0.000334

11     0.000082     0.000513
12     0.000082     0.000801
13     0.000084     0.001277
14     0.000086     0.002129
15     0.000086     0.003922
16     0.000087     0.007062
17     0.000088     0.011629
18     0.000091     0.020691
19     0.000092     0.034425
20     0.000093     0.054018

21     0.000094     0.089756
22     0.000096     0.147333
23     0.000097     0.223109
24     0.000098     0.384106
25     0.000100     0.600214

可以看到,从N=8开始,递归消耗的时间就成倍增加,所以在这种情况下还是不用递归为妙
欢迎讨论!