斐波那契recursion函数如何“工作”？
我是Javascript的新手，在阅读描述函数recursion的章节时，正在阅读。 它使用一个示例函数来查找斐波纳契数列的第n个数字。 代码如下：
function fibonacci(n) { if (n < 2){ return 1; }else{ return fibonacci(n-2) + fibonacci(n-1); } } console.log(fibonacci(7)); //Returns 21 我无法精确地掌握这个函数在做什么。 有人可以解释这里发生了什么？ 我卡在第五行，函数调用自己。 这里发生了什么？
你自己定义一个函数。 一般来说， 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)等于1 -
fibonacci(0)等于1
我们现在有评估fibonacci(7)所需的所有部分fibonacci(7) ，这是我们最初的目标。 请注意， 基本情况 – 当n < 2时return 1 ，这是可能的。 这是什么停止recursion，以便我们可以开始展开堆栈和汇总我们在每一步返回的值的过程。 如果没有这一步，我们会继续调用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));
输出：
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)
将相同级别的缩进值相加，以产生前一级缩进的结果。
步骤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被称为。
可视化：
fibonacci(7) ____|_____ | | fibonacci(5) fibonacci(6) ____|____ ____|_____ | | | | fib(3) fib(4) fib(4) fib(5)
看看它如何分支？ 什么时候停止？ 当n变成小于2时，这就是为什么if (n < 2) 。 在这一点上，分支停止，所有东西都加在一起。
这里有很多很好的答案，但是我做了这个图来帮助更好地解释函数的结果。 唯一将会返回的值是1或0（你的例子对于n <2返回1，但是应该返回n）。
这意味着每个recursion调用最终都会返回一个0或1.这些结果被“caching”在堆栈中，并被“提升”到原始的调用中，并被添加到一起。
因此，如果您要为每个“n”的值绘制相同的图表，则可以手动查找答案。
这个图粗略地说明了每个函数是如何返回fib（5）的。
这显示了控制stream程，即function的执行顺序。 记住代码总是执行左 – >右和顶部 – >底部。 所以每当一个新的函数被调用，它就会暂停，然后下一个调用就会发生。
以下举例说明基于原始post的实际控制stream程。 请注意基本条件是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) };
希望以下帮助。 呼叫：
fibonacci(3)
将达到第5行，并做：
return fibonacci(1) + fibonacci(2);
第一个expression式再次调用函数并返回1（因为n < 2 ）。
第二个再次调用函数，到第五行，然后：
return fibonacci(0) + fibonacci(1);
两个expression式都返回1（因为两个都是n < 2 ），所以这个函数调用返回2。
所以答案是1 + 2，这是3。
我认为这两个函数给了我一个更清晰的recursion（从这个博客文章 ）：
function fibDriver(n) { return n === 0 ? 0 : fib(0, 1, n); } function fib(a, b, n) { return n === 1 ? b : fib(b, a + b, n-1); }
该函数正在调用自己。 这只是一个recursion函数的定义。 在第五行中，通过传递参数来传递执行到自身。
为了确保recursion函数不会变成一个无限循环，必须有某种不会调用自身的条件。 你的代码在这个问题的目标是执行一个斐波那契数列的计算。
要计算第n个斐波纳契数，关系式为F（n）= F（n-2）+ F（n-1）。
如果我们在代码中实现关系，则对于第n个数字，我们使用相同的方法计算第（n-2）和第（n-1）个数字。
每个后续数字是前两个数字的总和。 因此，第七个数字是第六个和第五个数字的总和。 更一般地说，第n个数字是n-2和n-1的总和，只要n> 2。由于recursion函数需要一个停止条件来停止recursion，这里n <2是条件。
f（7）= F（6）+ F（5）;
反过来，F（6）= F（5）+ F（4）
F（5）= F（4）+ F（3）…继续，直到n <2
F（1）返回1
/ *
*步骤斐波纳契recursion
* 1）3通过。 （在这个通话过程中3被打印到屏幕上）
* 2）斐波那契A减2，recursion发生1作为参数。 （在此呼叫期间，1被打印到屏幕上）
* 3）斐波那契A点击返回1的基本情况，并“展开”。 （这里没有recursion）
* 4）Fibonacci B被调用，将n的前一个值（3是A返callback用之前n的前一个值）递减为2（在此调用期间将2打印到屏幕上）
* 5）再次调用Fibonacci A从n（2-2 = 0）中减去2，并传递0作为参数。 （在此调用期间，由于它从0转换而被打印到屏幕上）
* 6）Fibonacci A击中基本情况并“展开”（这里没有recursion）
* 7）Fibonacci B被称为从2中减去1（2是在A返callback用之前n的前一个值），并将1作为parameter passing。 （在此呼叫期间，1被打印到屏幕上）
* 7）斐波纳契B现在触及基本情况，返回1并“展开”（这里没有recursion）
* 8）Fibonacci B回溯所有先前的函数调用和n的值（在我们的例子中n = 2），并将其添加到存储在其本地范围中的n = 1的副本中
* 9）一旦Fibonacci B完成“展开”过程，它将计算出的值返回给原始调用者（这里没有recursion）
注意*
斐波那契recursion的每个实例都创build了自己的作用域，并将返回的值存储在n的副本中（在我们的案例1中）。
由于函数“展开”，它将执行随后接收n值的代码。 （所有调用其他函数的函数一旦返回，就通过以前的调用退回）
在我们斐波那契例子的最后一次调用中，斐波纳契B接收到n = 2的值，因为这是退callback用之前的最后一个值，因为斐波那契A“展开”。
一旦斐波纳契B到达基本情况并“解开”，它就回溯到以前的所有n值（在本例中只有n = 2），并将其添加到n = 1的本地副本中。
*通过数字3时的结果是：
3
1
2
1
1
（3）
* /
var div = document.getElementById('fib'); function fib( n, c ) { var indent = ""; for (var i = 0; i < c; i++) { indent += " "; } var v = n===0 ? 1 : n var el = document.createElement('div'), text = indent + "fibonacci(" + v + ")"; el.innerHTML = text; div.appendChild(el); if(n<2){ return 1; } return fib(n-2, c + 4) + fib(n-1, c + 4);
}
