描述PHP代码功能/递归;11年级的功能/递归

Question

function f($n)
{
   if ($n == 0 || $n == 1)
      return 2;
   return  f($n-1) + f($n-2);
}
echo f(5);

这给了我16，但我不知道为什么。

我知道它是这样的：

return f(4) + f(3)
return f(4) + f(3)+ f(3) + f(1)

现在，由于n的值是1，因此应该返回2。

所以它本质上是

return f(4) + f(3)+ f(2)

应该是9，但它给了我16。

任何人都可以解释如何？

Answer 1

f(5) = f(4)                        + f(3)
     = f(3)           + f(2)       + f(2)        + f(1)
     = f(2)     +f(1) + f(1) + f(0) + f(1) + f(0) + 2
     = f(1)+f(0)+ 2   + 2    + 2    + 2    + 2    + 2
     = 2   + 2  + 2   + 2    + 2    + 2    + 2    + 2
     = 16

希望上述解释将解释值16

Answer 2

f(0)=2
f(1)=2
f(2)=f(1)+f(0)=2+2=4
f(3)=f(2)+f(1)=4+2=6
f(4)=f(3)+f(2)=6+4=10
f(5)=f(4)+f(3)=10+6=16

Answer 3

这是递归函数的视觉表示，显示了每个迭代的返回

                      f(5)                          1st
                    /       
                   /         
                  /           
                 /             
                /               
               /                 
            f(4)       +        f(3)                2nd
          /                    /  
         /                    /    
      f(3)  +   f(2)   +    f(2)  +f(1)             3rd
      /        /          /       |
   f(2)+f(1)+f(1)+f(0) + f(1)+f(0)+  2              4th
   /     |    | +  |      |    |    |
f(1)+f(0)+2 +  2 +  2  +   2 +  2 +  2              5th
  |    |  |    |    |      |    |    |
  2 +  2 +2 +  2 +  2  +   2 +  2 +  2 = 16        Result

Answer 4

这是计算的更容易读取的分解：

f(5 - 1) + f(5 - 2)
(f(4 - 1) + f(4 - 2)) + (f(3 - 1) + f(3 - 2))
((f(3 - 1) + f(3 - 2)) + (f(2 - 1) + f(2 - 2))) + ((f(2 - 1) + f(2 - 2)) + 2)
Above simplifies to:
((f(2) + 2) + (2 + 2)) + ((2 + 2) + 2)
Then to:
((f(2) + 2) + 4) + (6)
Then remove extra parenthesis:
f(2) + 2 + 4 + 6
Then simplify:
f(2) + 12
Continuing:
f(2 - 1) + f(2 - 2) + 12
Simplify:
2 + 2 + 12 = 16

Answer 5

每次调用递归功能并传递一个大于 1的值时，您都会得到"叉"（或后续递归调用）。

凝结语法：（演示）

function f($n){
  return $n<2 ? 2 : f($n-1)+f($n-2);
}

当f(1)时，没有叉子。返回2

当f(2)时，只有1个叉子。返回4（LHS = 2 RHS = 2）

当f(3)（初始叉子）后，有一个后续叉 @ lhs分支。返回6（LHS = 4 RHS = 2）

当f(4)（初始叉子）后，有3个叉子：2xlhs＆amp;1xrhs。返回10（LHS = 6 RHS = 4）

当f(5)（初始叉子）之后，有6个叉子：4xlhs＆amp;2x $ rhs。返回16（LHS = 10 RHS = 6）