首先是轉載地址:  http://blog.csdn.net/star_yt/article/details/53103172

原博主不在線,如您看到這篇文章,可聯系我刪除,謝謝.

    最近在看php面試題,看到一個斐波拉契數列的題: 有一列數的規則如下 1、1、2、3、5、8、13、21、34... 求第30位數是多少.寫出相關函數和算法名稱 ,

大部分網友都選擇了遞歸,其實我自己看到題的時候也是首先想起遞歸,但是,遞歸的拙劣性大家也是有目共睹,所以我也在找有沒有高手寫了其他的方式,找到了上面鏈接里面的文章,所以忍不住想要copy過來,網上搜索也是太多地方說遞歸,所以我也想多一篇文章來描述非遞歸.

非遞歸寫法：

function fbnq($n){  //傳入數列中數字的個數    if($n <= 0){        return 0;    }    $array[1] = $array[2] = 1; //設第一個值和第二個值為1    for($i=3;$i<=$n;$i++){ //從第三個值開始        $array[$i] = $array[$i-1] + $array[$i-2];         //后面的值都是當前值的前一個值加上前兩個值的和    }    return $array;}

遞歸寫法：function fbnq($n){    if($n <= 0) return 0;    if($n == 1 || $n == 2) return 1;    return fbnq($n - 1) + fbnq($n - 2);}