斐波那契递归函数是如何“工作”的？
我是Javascript的新手，当我读到描述函数递归的一章时，我正在阅读它。它使用了一个示例函数来查找Fibonacci序列的第n个数字。代码如下：
function fibonacci(n) {
if (n < 2){
return 1;
}else{
return fibonacci(n-2) + fibonacci(n-1);
}
}
console.log(fibonacci(7));
//Returns 21我很难理解这个函数到底在做什么。有人能解释一下这是怎么回事吗？我被卡在第五行了，在那里函数调用自己。这是怎么回事？
回答 7
Stack Overflow用户
发布于 2015-12-01 05:14:30
这里有很多很好的答案，但我制作了这个图表，它有助于更好地解释函数的结果。唯一会返回的值是1或0(当n< 2时，您的示例返回1，但应该返回n)。
这意味着每个递归调用最终将返回0或1，它们最终被“缓存”在堆栈中，并被“携带”到原始调用中，然后相加在一起。
因此，如果您要为每个“n”值绘制相同的图表，您可以手动找到答案。
此图大致说明了如何为fib(5)返回每个函数。
这显示了控制流，即函数的执行顺序。请记住，代码总是在左侧->右侧和顶部->底部执行。因此，每当新函数被调用时，它就会暂停，然后下一次调用就会发生。
下面说明了基于你的原始帖子的实际控制流程。请注意，为简化起见，基本条件为if (n <= 0) {return 0} else if (n <= 2) {return 1;}：
1. fib(5) {
return fib(4) + fib(3);
2. fib(4) {
return fib(3) + fib(2);
3. fib(3) {
return fib(2) + fib(1);
4. fib(2) {
A= return 1;
};
5. fib(1) {
B= return 1;
};
C= return 2; // (1 + 1)
};
6. fib(2) {
D= return 1;
};
E= return 3; // (2 + 1)
};
7. fib(3) {
return fib(2) + fib(1);
8. fib(2) {
F= return 1;
};
9. fib(1) {
G= return 1;
};
H= return 2; // (1 + 1)
};
I= return 5; // (3 + 2)
};Stack Overflow用户
发布于 2012-01-13 10:51:16
步骤1)当调用fibonacci(7)时，想象一下(注意我是如何将所有n改成7的)：
function fibonacci(7) {
if (7 < 2){
return 1;
}else{
return fibonacci(7-2) + fibonacci(7-1);
}
}步骤2)由于(7 < 2)显然是假的，我们转到fibonacci(7-2) + fibonacci(7-1);，它转换为fibonacci(5) + fibonacci(6);，因为fibonacci(5)首先被调用(这次将n改为5)：
function fibonacci(5) {
if (5 < 2){
return 1;
}else{
return fibonacci(5-2) + fibonacci(5-1);
}
}步骤3)，或者当然，fibonacci(6)也会被调用，所以发生的事情是，每个人都调用fibonacci 2新的fibonacci get。
可视化：
fibonacci(7)
____|_____
| |
fibonacci(5) fibonacci(6)
____|____ ____|_____
| | | |
fib(3) fib(4) fib(4) fib(5)看到它是如何分支的了吗？它什么时候会停止呢？当n小于2时，这就是为什么你使用if (n < 2)。在这一点上，分支停止，所有内容都被添加到一起。
Stack Overflow用户
发布于 2012-01-13 10:46:07
希望下面的内容能有所帮助。呼叫：
fibonacci(3)将转到第5行并执行以下操作：
return fibonacci(1) + fibonacci(2);第一个表达式再次调用该函数并返回1(从n < 2开始)。
第二个函数再次调用该函数，转到第5行并执行：
return fibonacci(0) + fibonacci(1);两个表达式都返回1(因为这两个表达式都是n < 2 )，所以这个函数调用返回2。
所以答案是1+ 2，就是3。
https://stackoverflow.com/questions/8845154
复制相似问题
腾讯云开发者
