ope*_*pes 59 recursion fibonacci
当我来到一个描述函数递归的章节时,我是Javascript的新手并正在阅读它.它使用示例函数来查找第n个Fibonacci序列.代码如下:
function fibonacci(n) {
if (n < 2){
return 1;
}else{
return fibonacci(n-2) + fibonacci(n-1);
}
}
console.log(fibonacci(7));
//Returns 21
Run Code Online (Sandbox Code Playgroud)
我无法准确掌握这个功能正在做什么.有人能解释一下这里发生了什么吗?我被困在第5行,函数调用自己.这里发生了什么事?
Way*_*ett 89
你根据自己定义了一个函数.一般来说,fibonnaci(n) = fibonnaci(n - 2) + fibonnaci(n - 1)
.我们只是在代码中表示这种关系.因此,fibonnaci(7)
我们可以观察到:
fibonacci(7)
等于fibonacci(6)
+fibonacci(5)
fibonacci(6)
等于fibonacci(5)
+fibonacci(4)
fibonacci(5)
等于fibonacci(4)
+fibonacci(3)
fibonacci(4)
等于fibonacci(3)
+fibonacci(2)
fibonacci(3)
等于fibonacci(2)
+fibonacci(1)
fibonacci(2)
等于fibonacci(1)
+fibonacci(0)
fibonacci(1)
等于1fibonacci(0)
等于1我们现在拥有评估所需的所有部件fibonacci(7)
,这是我们最初的目标.请注意,基本情况 - return 1
何时n < 2
- 是使这成为可能的原因.这就是停止递归的原因,这样我们就可以开始展开堆栈的过程,并总结我们在每一步返回的值.如果没有这一步,我们将继续调用fibonacci
越来越小的值,直到程序最终崩溃.
添加一些说明这一点的日志语句可能会有所帮助:
function fibonacci(n, c) {
var indent = "";
for (var i = 0; i < c; i++) {
indent += " ";
}
console.log(indent + "fibonacci(" + n + ")");
if (n < 2) {
return 1;
} else {
return fibonacci(n - 2, c + 4) + fibonacci(n - 1, c + 4);
}
}
console.log(fibonacci(7, 0));
Run Code Online (Sandbox Code Playgroud)
输出:
fibonacci(7)
fibonacci(5)
fibonacci(3)
fibonacci(1)
fibonacci(2)
fibonacci(0)
fibonacci(1)
fibonacci(4)
fibonacci(2)
fibonacci(0)
fibonacci(1)
fibonacci(3)
fibonacci(1)
fibonacci(2)
fibonacci(0)
fibonacci(1)
fibonacci(6)
fibonacci(4)
fibonacci(2)
fibonacci(0)
fibonacci(1)
fibonacci(3)
fibonacci(1)
fibonacci(2)
fibonacci(0)
fibonacci(1)
fibonacci(5)
fibonacci(3)
fibonacci(1)
fibonacci(2)
fibonacci(0)
fibonacci(1)
fibonacci(4)
fibonacci(2)
fibonacci(0)
fibonacci(1)
fibonacci(3)
fibonacci(1)
fibonacci(2)
fibonacci(0)
fibonacci(1)
Run Code Online (Sandbox Code Playgroud)
将相同缩进级别的值相加以产生先前缩进级别的结果.
Jef*_*han 29
这里有很多好的答案,但我制作了这个图表,有助于更好地解释函数的结果.将返回的唯一值是1或0(对于n <2,您的示例返回1,但应返回n).
这意味着每个递归调用最终将最终返回0或1.这些最终被"缓存"在堆栈中并"携带"到原始调用中并添加到一起.
因此,如果您要为'n'的每个值绘制相同的图表,您可以手动找到答案.
该图粗略地说明了如何为fib(5)返回每个函数.
这显示了控制流程,即功能的执行顺序.记住代码始终执行left-> right和top-> bottom.因此,无论何时调用新函数,它都会暂停,然后发生下一次调用.
以下说明了基于原始帖子的实际控制流程.请注意,基本条件是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)
};
Run Code Online (Sandbox Code Playgroud)
Jes*_*ood 20
步骤1)当fibonacci(7)
被调用时想象以下(注意我如何将所有n改为7):
function fibonacci(7) {
if (7 < 2){
return 1;
}else{
return fibonacci(7-2) + fibonacci(7-1);
}
}
Run Code Online (Sandbox Code Playgroud)
步骤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);
}
}
Run Code Online (Sandbox Code Playgroud)
步骤3)并且当然fibonacci(6)
也会被调用,所以发生的事情是每个人调用fibonacci
2个新的fibonacci
调用.
可视化:
fibonacci(7)
____|_____
| |
fibonacci(5) fibonacci(6)
____|____ ____|_____
| | | |
fib(3) fib(4) fib(4) fib(5)
Run Code Online (Sandbox Code Playgroud)
看看它如何分支?什么时候停止?当n
变得小于2时,这就是你拥有的原因if (n < 2)
.此时,分支停止,一切都加在一起.
希望以下有所帮助.呼叫:
fibonacci(3)
Run Code Online (Sandbox Code Playgroud)
将到达第5行并执行:
return fibonacci(1) + fibonacci(2);
Run Code Online (Sandbox Code Playgroud)
第一个表达式再次调用该函数并返回1(从n < 2
).
第二个再次调用该函数,到达第5行并执行:
return fibonacci(0) + fibonacci(1);
Run Code Online (Sandbox Code Playgroud)
两个表达式都返回1(因为n < 2
两者都有),所以这个函数调用返回2.
所以答案是1 + 2,即3.