斐波那契數列 – 遞歸和遞歸優化
斐波那契數列，即兔子問題；演算法筆試題可能會出現；
function fun($n){ if($n==1||$n==2){ return 1; }
return fun($n-1) + fun($n-2); }
性能問題： 1，自身嵌套太深，可能會引起堆棧溢出；
堆棧溢出：函數調用會使用棧來保存臨時變數。每調用一個函數，都會將臨時變數封裝為棧幀壓入記憶體棧，等函數執行完成返回時，才出棧。系統棧或者虛擬機棧空間一般都不大。如果遞歸求解的數據規模很大，調用層次很深，一直壓入棧，就會有堆棧溢出的風險。
2，重複計算，拖慢計算速度；
優化方面：
1，遞歸方式的優化：
$a = 1; $b = 1; function fun($a, $b, $n){ if($n > 2){ return fun($a+$b, $a, $n-1); } return $a; }
2，非遞歸方式：
function fun($n){ if($n==1||$n==2){ return 1; } $a = $b = 1; for($i=2; $i<$n; $i++){ $temp = $b; $b += $a; $a = $temp; } return $b; }
測試 n = 20 的時候的結果：
// 遞歸未優化 值：6765 執行時間：0.00088596343994141 遞歸次數：13529 // 遞歸優化 值：6765 執行時間：4.0531158447266E-6 遞歸次數：19 // 非遞歸 值：6765 執行時間：3.0994415283203E-6 遞歸次數：1
綜上所述，性能方面： 非遞歸 > 優化的遞歸 > 未優化後的遞歸
