斐波那契递归函数如何"起作用"?

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) 等于1
  • fibonacci(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)

将相同缩进级别的值相加以产生先前缩进级别的结果.

  • 这为我钉了它.您创建的流程正是我理解它所需要的.出色的工作. (2认同)

Jef*_*han 29

这里有很多好的答案,但我制作了这个图表,有助于更好地解释函数的结果.将返回的唯一值是1或0(对于n <2,您的示例返回1,但应返回n).

这意味着每个递归调用最终将最终返回0或1.这些最终被"缓存"在堆栈中并"携带"到原始调用中并添加到一起.

因此,如果您要为'n'的每个值绘制相同的图表,您可以手动找到答案.

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

![Fibonacci Javascript树图

这显示了控制流程,即功能的执行顺序.记住代码始终执行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)

  • 伟大的可视化!尽管我已经知道递归计算的工作原理,但我必须说,这很好地直观地表示了实际总和的计算方式。竖起大拇指! (3认同)

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)也会被调用,所以发生的事情是每个人调用fibonacci2个新的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).此时,分支停止,一切都加在一起.


Rob*_*obG 5

希望以下有所帮助.呼叫:

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.

  • 那讲得通.因此,基本上每次调用函数时,它都会向下钻取到斐波那契(0)+斐波那契(1),即1 + 2 - 实际数学运算完成.谢谢! (2认同)