斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21。这个数列从第3项开始,每一项都等于前两项之和。
根据这个定义,斐波那契数列的递推公式是:f(n)=f(n-1)+f(n-2) ,
function _fbnq($n){ if($n <= 0){ return 0; } if($n == 1 || $n == 2){ return 1; } return _fbnq($n - 1) + _fbnq($n - 2); }
测试
$arr= []; for ($i=1;$i<=10;$i++){ array_push($arr,_fbnq($i)); } print_r($arr);
Array (
[0] => 1
[1] => 1
[2] => 2
[3] => 3
[4] => 5
[5] => 8
[6] => 13
[7] => 21
[8] => 34
[9] => 55
)
上面函数也可以优化成尾递归,要提供两个累积变量。减少调用栈(call stack)。
function fibonacci($n, $n1, $n2) { if($n <= 0) { return 0; } if($n <= 1) { return $n2; } return fibonacci($n - 1, $n2, $n1 + $n2); }
测试
$arr= []; for ($i=1;$i<=10;$i++){ array_push($arr,fibonacci($i,0,1)); }