Javascript 函数。不明白 self-function 内部的函数是如何工作的

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