PHP-f(1)=2;f(2)=3;f(n)=f(n-1)+f(n-2),写一个foo($num)方法

Question

有一道题是这样的：
f(1)=2;f(2)=3;f(n)=f(n-1)+f(n-2),写一个foo($num)方法。采用递归和非递归两种方式。我写不出来了。

<?php
function foo($num){
    $arr=array();//声明一个空数组
    $result=0;
    $arr[0]=2;
    $arr[1]=3;
    $array=array();
    for($i=2;$i<$num;$i++){
        $arr[$num-1]=$arr[$i-1]+$arr[$i-2];
        $array[$i-2]=$arr[$num-1];
        $result=$result+$array[$i-2];
    }
    
    print_r($array);
}

foo(4);

Answer 1

代码大意同Runaria的，斐波纳契数列，去掉了IF语句，简化了不少，把$f2 = 0的话就是输出斐波纳契数列

 function foo($n) {
$rs = 0;
$f1 = 1;
$f2 = 1;
for ($i = 1; $i <= $n; $i++) {
$rs = $f1 + $f2;
$f2 = $f1;
$f1 = $rs;
}

return $rs;
}

Answer 2

1.递归的方法:这种方法其实很简单，定义好最初两项的值，然后剩下的就按构成格式f(n)=f(n-1)+f(n-2)照着嵌套函数就行了，下面是我自己打的javascript代码，思路都是一样的。

function foo(n){
if(n>0){
if(n==1){
return 2;
}else if(n==2){
return 3;
}else{
return foo(n-1)+foo(n-2);
}
}
}
console.log(foo(10));

2.非递归的方法：这个我忘记了有没有数学方面直接计算的公式，不过可以把递归计算的方向倒过来用循环。（递归是从大到小一个一个拆解计算，循环就是从小一直加到大）
依然是javascript的代码

 function foo2(n){
if(n>0){
if(n==1){
return 2;
}else if(n==2){
return 3;
}else{
var f1 = 2; //f(n-2)的初始值
var f2 = 3; //f(n-1)的初始值
var out;
for(var i =3;i<=n;i++){
out = f1+f2; //计算当前f(i)的值
f1=f2; //设置下一次循环中的f(n-2)
f2=out; //设置下一次循环中的f(n-1)
}
return out;
}
}
}
console.log(foo2(10));

Answer 3

<?php
//非递归
function foo_1($num){
$arr = array();
if ($num > 0) $arr[0] = 2;
if ($num > 1) $arr[1] = 3;
if ($num > 2) {
$result = $arr[0] + $arr[1];
for($i=2; $i<$num; $i++) {
$arr[$i] = $arr[$i-1] + $arr[$i-2];
$result = $result + $arr[$i];
}
}
print_r($arr);
}

//递归
function foo_2($num){
if ($num == 1) {
return 2;
} elseif ($num == 2) {
return 3;
} elseif ($num > 2) {
return foo_2($num-1) + foo_2($num-2);
}
}

foo_1(4);
echo foo_2(4);

?>