首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >斐波那契递归函数是如何“工作”的?

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

Stack Overflow用户
提问于 2012-01-13 10:25:36
回答 7查看 65.7K关注 0票数 71

我是Javascript的新手,当我读到描述函数递归的一章时,我正在阅读它。它使用了一个示例函数来查找Fibonacci序列的第n个数字。代码如下:

代码语言:javascript
复制
function fibonacci(n) {
    if (n < 2){
        return 1;
    }else{
        return fibonacci(n-2) + fibonacci(n-1);
    }
}

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

我很难理解这个函数到底在做什么。有人能解释一下这是怎么回事吗?我被卡在第五行了,在那里函数调用自己。这是怎么回事?

EN

回答 7

Stack Overflow用户

发布于 2015-12-01 05:14:30

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

这意味着每个递归调用最终将返回0或1,它们最终被“缓存”在堆栈中,并被“携带”到原始调用中,然后相加在一起。

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

此图大致说明了如何为fib(5)返回每个函数。

这显示了控制流,即函数的执行顺序。请记住,代码总是在左侧->右侧和顶部->底部执行。因此,每当新函数被调用时,它就会暂停,然后下一次调用就会发生。

下面说明了基于你的原始帖子的实际控制流程。请注意,为简化起见,基本条件为if (n <= 0) {return 0} else if (n <= 2) {return 1;}

代码语言:javascript
复制
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)
   };
票数 36
EN

Stack Overflow用户

发布于 2012-01-13 10:51:16

步骤1)当调用fibonacci(7)时,想象一下(注意我是如何将所有n改成7的):

代码语言:javascript
复制
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):

代码语言:javascript
复制
function fibonacci(5) {
    if (5 < 2){
        return 1;
    }else{
        return fibonacci(5-2) + fibonacci(5-1);
    }
}

步骤3),或者当然,fibonacci(6)也会被调用,所以发生的事情是,每个人都调用fibonacci 2新的fibonacci get。

可视化:

代码语言:javascript
复制
      fibonacci(7)
      ____|_____
     |          |
fibonacci(5)  fibonacci(6)
____|____     ____|_____
|        |    |         |
fib(3)  fib(4) fib(4)   fib(5)

看到它是如何分支的了吗?它什么时候会停止呢?当n小于2时,这就是为什么你使用if (n < 2)。在这一点上,分支停止,所有内容都被添加到一起。

票数 23
EN

Stack Overflow用户

发布于 2012-01-13 10:46:07

希望下面的内容能有所帮助。呼叫:

代码语言:javascript
复制
fibonacci(3)

将转到第5行并执行以下操作:

代码语言:javascript
复制
return fibonacci(1) + fibonacci(2);

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

第二个函数再次调用该函数,转到第5行并执行:

代码语言:javascript
复制
return fibonacci(0) + fibonacci(1);

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

所以答案是1+ 2,就是3。

票数 7
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/8845154

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档