关于Fibonacci递归的解释

Question

我必须对此有所了解.似乎没有明确解释的好指南.功能树是什么样的？

static long Fib(int n)
{  
    if (n <= 2)  
    {   
        return 1;  
    }  
    return Fib(n - 1) + Fib(n - 2); 
}

假设我这样做Fib(7),我实际上明白它应该是这样的:

事情是,看起来树似乎fib(7)实际意味着fib(6)+ fib(5)应该是真的....但是,如果我理解递归而不是fib(7)实际fib(6)+ fib(5)但是fib(5)还没有操作,因为fib(6)现在将自己称为fib(4)+ fib(3)并且再一次fib(3)将不会执行,因为它fib(4)会自动调用,直到它停止在"停止"状态...而不是什么？

如果fib(7)呼叫fib(6)等等......直到fib(1),所有其他fib(n-2)功能呢？

每次结果如何实际返回并告诉我它的值是fib(7)多少？

Answer 1

好吧，在你理解它之前，回避并不容易理解......

因此函数fib(7)是用fib(6) + fib(5)计算的

（使用较小的值调用同一函数，这会导致函数调用内的函数调用内的函数调用）

fib(6)又是fib(5) + fib(4)
而 fib(5)是fib(4) + fib(3)

这个链一直持续到fib(3) = fib(2) + fib(1)因为fib(1)和fib(2)是1。这意味着fib(3) 的值为2

现在你可以再退一步看看fib(4)，它是fib(3) + fib(2)，它计算出2 + 1，即3

在这个阶段，我们回到fib(5)，即fib(4) + fib(3)或3 + 2或5

在这种风格中，您沿着树向上返回，直到再次到达fib(7)，然后计算出5 + 8或13 ，这是斐波那契行的第七个数字的正确值

停止条件用于停止调用进一步的函数并开始将实际值返回到调用该函数的函数。

我希望这个能有一点帮助。