尾调用

尾调用Tail Call是函数式编程的一个重要概念就是指某个函数的最后一步是调用另一个函数。

function f(x){
  return g(x);
}

以下情况都不属于尾调用。

// 情况一
function f(x){
  let y = g(x);
  return y;
}
// 情况二
function f(x){
  return g(x) + 1;
}
// 情况三
function f(x){
  g(x);
}

上面代码中情况一是调用函数g之后还有赋值操作所以不属于尾调用即使语义完全一样。情况二也属于调用后还有操作即使写在一行内。情况三等同于下面的代码。

function f(x){
  g(x);
  return undefined;
}

尾调用优化

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

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

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

function addOne(a){
  var one = 1;
  function inner(b){
    return b + one;
  }
  return inner(a);
}

上面的函数不会进行尾调用优化因为内层函数inner用到了外层函数addOne的内部变量one。

ES6 的尾调用优化只在严格模式下开启正常模式是无效的。这是因为在正常模式下函数内部有两个变量func.arguments和func.caller可以跟踪函数的调用栈。

尾递归

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

function factorial(n, total) {
  if (n === 1) return total;
  return factorial(n - 1, n * total);
}
factorial(5, 1) // 120

递归函数的改写

尾递归的实现往往需要改写递归函数确保最后一步只调用自身。就是把所有用到的内部变量改写成函数的参数。比如上面的例子为什么计算5的阶乘需要传入两个参数5和1

两个方法可以解决这个问题。方法一是在尾递归函数之外再提供一个正常形式的函数。

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

函数式编程有一个概念叫做柯里化currying意思是将多参数的函数转换成单参数的形式。这里也可以使用柯里化。

第二种方法就简单多了就是采用 ES6 的函数默认值。