斐波那契递归函数是如何“工作”的？

我对 Javascript 还是个新手，当我读到描述函数递归的那一章时，我正在研究它。它使用了一个示例函数来求斐波那契数列的 n 个数。守则如下:

function fibonacci(n) {
if (n < 2){
return 1;
}else{
return fibonacci(n-2) + fibonacci(n-1);
}
}


console.log(fibonacci(7));
//Returns 21

我无法准确理解这个函数的作用。有人能解释一下这是怎么回事吗？我在第5行卡住了，函数在第5行调用它自己。这里发生了什么？

74597 次浏览
小开

函数正在调用自身。这只是递归函数的定义。在第5行中，它通过传递将产生一个值的参数将执行传递给自己。

为了确保递归函数不会变成无穷无尽的循环，必须存在某种 没有调用自身的条件。问题中代码的目标是执行斐波那契数列的计算。

小开

要计算 nth 斐波那契数列，关系是 F(n) = F(n-2) + F(n-1)。

如果我们在代码中实现关系，对于第 n 个数，我们使用相同的方法计算(n-2) th 和(n-1) th 数。

每个后续数字是前两个数字的和。因此，第七个数字是第六个和第五个数字的和。更一般地说，第 n 个数字是 n - 2和 n - 1的总和，只要 n > 2。由于递归函数需要一个停止条件来停止递归，这里 n < 2是条件。

f(7) = F(6) + F(5);


in turn, F(6) = F(5) + F(4)


F(5) = F(4) + F(3)...

一直持续到 n<2

F(1) returns 1
小开
最佳答案

你是在用函数本身定义一个函数。一般来说，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)所需的所有部件，这是我们最初的目标。请注意，基本情况——当 n < 2时是 return 1——使这成为可能。这就是停止递归的原因，这样我们就可以开始展开堆栈并对每个步骤返回的值求和的过程。如果没有这个步骤，我们将继续以越来越小的值调用 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)

对相同级别的缩进值进行求和，以生成前一级别缩进的结果。

小开

希望以下内容能帮上忙。呼叫:

fibonacci(3)

将到达第5行，然后做:

return fibonacci(1) + fibonacci(2);

第一个表达式再次调用函数并返回1(从 n < 2开始)。

第二个函数再次调用该函数，到达第5行并执行: 。

return fibonacci(0) + fibonacci(1);

两个表达式都返回1(因为两个表达式都是 n < 2) ，所以对函数的调用返回2。

所以答案是1 + 2，也就是3。

小开

步骤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)。在这一点上，分支停止，所有的东西被加在一起。

小开 
/*
* Steps Fibonacci recursion
* 1) 3 gets passed. (3 is printed to the screen during this call)
* 2) Fibonacci A gets decrements by 2 and recursion happens passing 1 as a param. (1 is printed to the screen during this call)
* 3) Fibonacci A hits the base case returning 1 and it "unwinds". (No recursion here)
* 4) Fibonacci B gets called, decrementing the previous value of n (3 was the previous value of n before A made the returning call) to 2. (2 is printed to the screen during this call)
* 5) Fibonacci A is called again subtracting 2 from n (2-2=0) and passes 0 as a param. (1 is printed to the screen during this call since it's converted from 0)
* 6) Fibonacci A hits the base case and "unwinds" (no recursion here)
* 7) Fibonacci B is called subtracting 1 from 2 (2 was the previous value of n before A made the returning call) and passes 1 as a param. (1 is printed to the screen during this call)
* 7) Fibonacci B now hits the base case, returning 1 and "unwinds" (no recursion here)
* 8) Fibonacci B retraces it's steps back through All previous fucntion calls and values of n (n=2 in our case) and adds [them] to the copy of n=1 stored in its local scope
* 9) Once Fibonacci B completes the "unwinding" process, it returns the calculated value to the original caller (no recursion here)


Note*
Each instance of Fibonacci recursion creates its own scope and stores the returned value in a copy of n (in our case 1).
As it the function "unwinds" it executes subsequent code that receive the value of n at that time. (all functions that call other functions "unwind" back through previous calls once they return)


In the last call of our Fibonacci example, Fibonacci B receives the value of n=2 as Fibonaccci A "unwinds" since that was the last value before it made the returning call.
Once Fibonacci B reached the base case and "unwound", it retraced its steps back through all previous values of n (in our case just n=2) and added [them] to its local copy of n=1.


* The result when passing the number 3 is:
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);

}

小开

这里有许多很好的答案，但是我做了这个图，它有助于更好地解释函数的结果。将返回的值只有1或0(您的示例对于 n < 2返回1，但应该返回 n)。

这意味着每个递归调用最终将返回0或1。这些最终被“缓存”在堆栈中，并“上传”到原始调用中，然后添加到一起。

因此，如果你要为 n 的每个值绘制相同的图表，你可以手动找到答案。

这个图粗略地说明了如何为 fib (5)返回每个函数。

![Fibonacci Javascript Tree Diagram

这显示了控制流，即函数的执行顺序。请记住，代码总是在左-> 右和顶-> 底部执行。因此，无论何时调用新函数，都会暂停该函数，然后发生下一次调用。

下面说明了基于原始文章的实际控制流。请注意，为了简化，基本条件是 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)
};
小开

这两个函数给了我一个关于递归的更清晰的解释(从这个 博客文章) :

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);
}


// Get the 10th fibbonacci number (when excluding the 0)
console.log(fibDriver(10))
小开

基于 ES6的递归函数斐波那契算法

const fibonacci = ( n, k = 1, fib2 = 0, fib1 = 1 ) => {
return k === n ?
(() => { return fib1; })()
:
(() => {
k++;
return fibonacci(n, k, fib1, fib1 + fib2);
})();
}
console.info(' fibonacci ' + 11 + ' = ' + fibonacci(11));
小开

听着，撒谎是

T (n) = t (n-1) + n;

如果 n = 0那么1

所以让我们看看递归是如何工作的，我只是用 n-1代替 t(n)中的 n，依此类推。它看起来:

T (n-1) = t (n-2) + n + 1;

T (n-1) = t (n-3) + n + 1 + n;

T (n-1) = t (n-4) + n + 1 + n + 2 + n;

.

.

.

T (n) = t (n-k) + ... + (n-k-3) + (n-k-2) + (n-k-1) + n;

我们知道如果 t(0)=(n-k)等于 1那么 n-k=0所以 n=k我们用 n代替 k:

T (n) = t (n-n) + ... + (n-n + 3) + (n-n + 2) + (n-n + 1) + n;

如果我们省略 n-n，那么:

T (n) = t (0) + ... + 3 + 2 + 1 + (n-1) + n;

所以 3+2+1+(n-1)+n是自然数，它计算为 Σ3+2+1+(n-1)+n = n(n+1)/2 => n²+n/2

结果为: O(1 + n²) = O(n²)

这是理解递归关系的最好方法

小开

在 JS/ES6中使用递归共享一个简单的 fib 代码。

function fib(n, first = 1, second = 1) {
if (n <= 2) return 1;
[first, second] = [second, first + second];
return (n - 2 === 1) ? second : fib(n - 1, first, second);
}


console.log(fib(10));
小开

情况会是这样的:

7-2 = 5—— > fibonacci (5)
7-1 = 6—— > 斐波那契(6)

就像在实现中给定的，左边总是减少

2和 右手减少了 1，所以它会以这种方式级联，直到它到达 1，一旦它到达 1，它将把它加到右手函数 1 + fibonacci(n-1);的输出，这也将总是停留在 1的每个实现:

if (n < 2){
return 1;
}

最终，它们都会在内存中有 1，并开始从左到右将它们相加... ... 考虑下面的级联表示，将底部的所有 1相加将使其成为 21。

左边总是 n - 2 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 总是 n - 1 _ _ _ _ _ _ _ _ _ _ _ _ _ else n = 1

                                        7
                   

5                              6
3          4                  4              5
1    2    2     3            2     3      3        4
1     1 1  1 1  1   2         1 1  1  2   1  2    2    3
1 1               1 1    1 1  1 1  1  2
1 1


1+    1+1+ 1+1 1+  1+1+       1+1+ 1+1+1+ 1+1+1+ 1+1+ 1+1+1 = 21

斐波那契数列的第7位是21，我们可以用数组来测试它:

const fibArray = [1, 1, 2, 3, 5, 8, 13, 21]
console.log(fibArray[7]) //-> 21

提交答案