尾调用: 阶乘factorial、 斐波那契fibonacci

函数调用会在内存形成一个“调用记录”，又称“调用帧”（call frame），保存调用位置和内部变量等信息。如果在函数A的内部调用函数B，那么在A的调用帧上方，还会形成一个B的调用帧。等到B运行结束，将结果返回到A，B的调用帧才会消失。如果函数B内部还调用函数C，那就还有一个C的调用帧，以此类推。所有的调用帧，就形成一个“调用栈”（call stack）。

尾调用由于是函数的最后一步操作，所以不需要保留外层函数的调用帧，因为调用位置、内部变量等信息都不会再用到了，只要直接用内层函数的调用帧，取代外层函数的调用帧就可以了。

“尾调用优化”（Tail call optimization），即只保留内层函数的调用帧。如果所有函数都是尾调用，那么完全可以做到每次执行时，调用帧只有一项，这将大大节省内存。这就是“尾调用优化”的意义。

注意，只有不再用到外层函数的内部变量，内层函数的调用帧才会取代外层函数的调用帧，否则就无法进行“尾调用优化”。

函数调用自身，称为递归。如果尾调用自身，就称为尾递归。

递归非常耗费内存，因为需要同时保存成千上百个调用帧，很容易发生“栈溢出”错误（stack overflow）。但对于尾递归来说，由于只存在一个调用帧，所以永远不会发生“栈溢出”错误。

递归 factorial

function factorial(n) {
  if (n === 1) return 1;
  return n * factorial(n - 1);
}

factorial(5)

尾递归 factorial

function tailFactorial(n, total=1) {
  if (n === 1) { return total; }

 return tailFactorial(n-1, n*total);
}

tailFactorial(5)

递归 fibonacci

function fibonacci(n) {
  if (n <=1) { return 1; }

  return fibonacci(n-1) + fibonacci(n-2);
}

fibonacci(10)

尾递归 fibonacci

function tailFibo(n, ac1=1, ac2=1) {
  if (n<=1) { return 1 }
  return tailFibo(n-1, ac2, ac1+ac2)
}

tailFibo(10)

尾递归不用保存外部调用的调用栈，复杂度始终为 O(1)

对于阶乘，参数 n 表示阶乘的次数，也就是阶乘到 n 这个数为止。这个地方的 n 有多个层次的用途。

• 从 n 开始相乘， n 参与了乘法运算
• n 是相乘次数的控制变量，每次会减 1，直到 n 的值自减到值为 1 就终止运算，返回计算值
• 相乘时，从大往小乘

对于斐波那契fibonacci， 参数 n 表示相加的次数， 两个初始变量的默认值都是 1。
n 并没有当参数参与到加法运算中，只是当做相加次数的控制变量
相加时，从 1 开始，从小往大加

科里化 currying

  function currying(fn, n) {
    return function (m) {
      console.log('lam', fn, m, n)
      return fn.call(this, m, n);
    };
  }

  function tailFactorial(n, total) {
    if (n === 1) return total;
    return tailFactorial(n - 1, n * total);
  }

  const factorial = currying(tailFactorial, 1);

函数的扩展