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

Question

当我读到描述函数递归的一章时，我是 Javascript 的新手，正在阅读它。它使用示例函数来查找斐波那契数列的第 n 个数字。代码如下：

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

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

我无法准确理解这个函数正在做什么。有人能解释一下这是怎么回事吗？我被困在第五行，函数调用自身。这里发生了什么事？

Answer 1

您正在根据自身定义一个函数。一般来说，斐波纳奇(n) = 斐波纳奇(n - 2) + 斐波纳奇(n - 1)。我们只是用代码来表示这种关系。因此，对于 fibonacci(7) 我们可以观察到：

• fibonacci(7) 等于 fibonacci(6) + fibonacci(5 )
• 斐波那契(6) 等于斐波那契(5) + 斐波那契(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 <<时，返回 1 2——这就是让这一切成为可能的原因。这就是停止递归的原因，以便我们可以开始展开堆栈并对每一步返回的值求和的过程。如果没有这一步，我们将继续对越来越小的值调用斐波那契，直到程序最终崩溃。

添加一些日志记录语句来说明这一点可能会有所帮助：

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)

将同一缩进级别的值相加，以生成上一缩进级别的结果。

Answer 2

这里有很多很好的答案，但我制作了这个图表，它有助于更​​好地解释该函数的结果。唯一返回的值是 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)
   };

Answer 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) 也会被调用，因此发生的事情是每个人都调用斐波那契 2 个新的斐波那契被调用。

可视化：

      fibonacci(7)
      ____|_____
     |          |
fibonacci(5)  fibonacci(6)
____|____     ____|_____
|        |    |         |
fib(3)  fib(4) fib(4)   fib(5)

看看它是如何分支的？什么时候才会停止呢？当n变得小于2时，这就是为什么你有if (n < 2)。在那一点上，分支停止，所有内容都加在一起。

Answer 4

希望以下内容有所帮助。 Calling:

fibonacci(3)

将到达第 5 行并执行：

return fibonacci(1) + fibonacci(2);

第一个表达式再次调用该函数并返回 1（因为 n <2）。

第二个函数再次调用该函数，到达第 5 行并执行以下操作：

return fibonacci(0) + fibonacci(1);

两个表达式都返回 1（因为两者的 n < 2），因此对该函数的调用返回 2。

因此答案是 1 + 2，即 3。

Answer 5

这两个函数给了我对递归的更清晰的解释（来自此 博客文章）：

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

Answer 6

函数正在调用自身。这就是递归函数的简单定义。在第 5 行中，它通过传递将产生一个值的参数来将执行转移到自身。

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

Answer 7

 
   /*
* 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);

}

Answer 8

要计算第 n 个斐波那契数，其关系为 F(n) = F(n-2) + F(n-1)。

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

每个后续数字都是前两个数字的总和。因此，第七个数是第六个和第五个数的和。更一般地，第 n 个数字是 n - 2 和 n - 1 之和，只要 n > 1。 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

Answer 9

它会像这样：

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

就像实现中给出的那样，左侧始终会减少

2 并且
右手减少1，所以它会以这种方式级联，直到碰到1，一旦碰到1，就会将其添加到右手函数 1 + fibonacci(n-1); 的输出，根据实现，它也将始终停止在 1 处：

if (n < 2){
  return 1;
}

最终它们都会结束内存中有 1 并从左侧开始将它们相加向右...考虑下面的级联表示，将底部的所有 1 加起来将得到 21。

如果 n > 2______________总是向左 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

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

Answer 11

看，小谎是

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

如果 n = 0 则 1

那么让我们看看递归是如何工作的，我只需将 t(n) 中的 n 替换为 n-1 等等。它看起来：

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(nk)+ ... + (nk-3) + (nk-2)+ (nk-1)+ n ;

我们知道如果 t(0)=(nk) 等于 1 那么 nk=0 所以 n=k我们用 n 替换 k：

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

如果我们省略 nn 则：

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

fib 的结果是：O(1 + n²) = O(n²)

这是理解递归关系的最佳方式

Answer 12

使用递归在 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));

Answer 13

我以更简洁的方式编写了相同的代码。

const prompt = require("prompt-sync")();

function Fibonacci(count, num_1 = 0, num_2 = 1) {
    if (count == 0) {
        return;
    }
    console.log(num_1);
    fibonacci(--count, num_2, num_1 + num_2)
}
const iteration = parseInt(prompt("Enter Count: "))
Fibonacci(iteration);

一探究竟。

Answer 14

我发现可视化调用堆栈很有帮助。不确定这是否正是递归函数执行的调用堆栈的样子（可能不是），但它是一个粗略的想法，可以帮助我更清楚地理解该过程。例如，加号不会像这样在堆栈上，而是在调用站点进行评估（如果我错了，请纠正我）。不确定加法实际上是如何根据调用堆栈计算的。这是一个调用堆栈可视化图，帮助我在完整的函数执行流程方面澄清了很多事情，并且还包含树形图，

这里是一个 exalidraw 链接，可以使缩放更加清晰

递归斐波那契调用堆栈

欢迎任何有关改进此问题的反馈，谢谢:)