c# - 斐波那契递归解释

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

它不会每次都返回一个值，至少不会立即返回。

每次方法调用自身时，它都会将新调用放入堆栈中。此堆栈上的空间有限，因此具有足够递归调用的大数字将引发 stackoverflow 异常。这也是为什么你有这个终止条件，告诉它什么时候停止调用自己。

if (n <= 2)  
{   
    return 1;  
}

在你的方法最后一次在树的每个分支上调用自身后(当 n <= 2 并且方法返回 1 而不是调用自身时)，它将展开堆栈，最终评估所有这些调用和总结返回值，返回13在 Fib(7) 的情况下.