javascript:理解斐波那契递归语句的流程

Question

我最终想要掌握动态编程的诀窍，但在此之前，我很难理解动态编程的流程。我理解递归，但我在理解这个流程时遇到了问题：

​

function fib(n) {
  if (n == 0) return 0;
  if (n == 1) return 1;
  return fib(n - 1) + fib(n - 2);
}
console.log(fib(3));

​

如果我有一个3的小整数，它没有通过这两个条件，所以它命中return fib(n-1)+fib(n-2);，所以据我所知，它将通过第一个条件的第一部分：fib(n-1) (3-1 =2)…2不满足这些条件中的任何一个，所以它运行fib(n-1) (2-1 = 1)。1确实满足了其中的一个条件，所以它returns 1并打破了它的一部分。

现在进入下一部分：fib(n-2)。(3-2 = 1)。1确实满足了其中一个条件，所以它是returns 1的。那么，这不就是返回1 + 1吗？

我不确定在我的理解中我错在哪里。

Answer 1

您认为fib(3)应该返回2是正确的，因为2是斐波那契数列中的第三个数字(从0开始)

它有助于将其写为tree：

       fib(3)
      /     \
    fib(2)   fib(1)
   /     \     \
 fib(1) fib(0)  1
 /        \  
1          0

在上面，你可以看到在返回上一层结果之前，每个递归调用是如何一直到0或1的。

Answer 2

我最喜欢的方法之一是从基本情况开始，然后向后返回：

fib(0); // => 0
fib(1); // => 1

然后我们来看看默认的情况：

fib(2); // == fib(1) + fib(0) == 1 + 0 ==> 1
fib(3); // == fib(2) + fib(1) == 1 + 1 ==> 2
fib(4); // == fib(3) + fib(2) == 2 + 1 ==> 3

这比先找出fib(4)要容易得多，因为你需要嵌套。看一下这个函数，就很容易知道要尝试什么。

还要知道，对同一函数的调用不会得到任何特殊处理。它会一直运行，直到返回一个值，并且它的参数和局部变量是调用的局部变量，所以每个fib调用都有它自己的n，它会等待两个调用返回并对结果求和。