Javascript功能.不明白自功能内部的功能如何工作

Question

想问一下JavaScript函数.

我不明白下面的功能,我认为第4 fib(n-1)行将返回1,后者fib(n-2)将返回0,然后它们两者一起加1.

我可以知道为什么最后的结果f(10);会是55,不能理解这个.

有人可以帮我解释一下幕后发生的事情吗？

谢谢!;)

var f = function fib(n) {
    if (n === 0) return 0;
    if (n === 1) return 1;
    if (n > 1) return fib(n - 1) + fib(n - 2);      // *2
};
f(10);       // 55

参考:https://slides.com/concise/js/fullscreen#/35

Answer 1

像这样.这是一个典型的递归函数,有两个基本情况和一个递归步骤.

请记住,如果n是10,那么fib(n - 1)是fib(9),依此类推:

fib(10) = fib(9) + fib(8) = 34 + 21 = 55
fib(9)  = fib(8) + fib(7) = 21 + 13 = 34
fib(8)  = fib(7) + fib(6) = 13 +  8 = 21
fib(7)  = fib(6) + fib(5) =  8 +  5 = 13
fib(6)  = fib(5) + fib(4) =  5 +  3 =  8
fib(5)  = fib(4) + fib(3) =  3 +  2 =  5
fib(4)  = fib(3) + fib(2) =  2 +  1 =  3
fib(3)  = fib(2) + fib(1) =  1 +  1 =  2
fib(2)  = fib(1) + fib(0) =  1 +  0 =  1
fib(1)  =                              1
fib(0)  =                              0

旁注:尽管您的示例是递归函数的一个很好的例证,但它是计算斐波纳契数的一种非常低效的方法.更好的方法是使用memoization来消除大部分低效率:

var fib = (function () {
  var cache = [0, 1];
  
  return function fib(num) {
    if (!(num in cache)) { 
        cache[num] = fib(num - 1) + fib(num - 2);
    }
    return cache[num];
  };
})();

console.log(fib(10));

http://jsperf.com/fibonacci-memoization-2015-04-01