[JavaScript] 尾调用优化 Tail Call Optimization

[andy2046]

介绍

现在函数式编程越来越流行，有时我们会选择用recursion递归来写逻辑，这样代码容易懂而且也可以避免一些side-effects副作用，但是， 但是，JavaScript并不支持尾递归调用

举个栗子🌰，下面👇代码会出错

var sum = function(x, y) {
  if (y > 0) {
    return sum(x + 1, y - 1)
  } else {
    return x
  }
}

sum(1, 100000) // RangeError: Maximum call stack size exceeded

var factorial = function (n) {
  function recur (n, acc) {
    if (n === 0) {
      return acc
    } else {
      return recur(n-1, n*acc)
    }
  }
  return recur(n, 1)
}

factorial(100000) // RangeError: Maximum call stack size exceeded

从上图可以看出来，每次调用都会依赖上一次调用的结果，所以会一直新建stack直到溢出，因为调用的最后一步不是直接返回调用结果而是计算再返回

解决方案一

我们可以定义一个函数trampoline，它接受一个函数func作为参数，每次调用func都会返回一个新的函数，我们循环调用直到返回的结果不是函数

但是这个方案的不足在于，入侵性比较强，你需要更改原来的函数，让它返回一个binded函数，bind会耗时又耗内存，因为每次都bind出来一个新的函数

var trampoline = function (func, arg) {
  var value = func(arg)
  while (typeof value === 'function') {
    value = value()
  }
  return value
}

function factorial (n) {
  function recur (n, acc) {
    if (n === 0) {
      return acc
    } else {
      return recur.bind(null, n-1, n*acc)
    }
  }
  return function () {
    return recur.bind(null, n, 1)
  }
}

console.log( trampoline(factorial(100000)) )
// => Infinity

解决方案二

这个解决方案是利用数组来保存每次调用的参数，第一次调用时，active是false，所以我们保存参数到数组中，并且进入到while循环，再次调用时active是true，所以每次都只是保存参数到数组中并返回，直到函数停止调用自身，参数没有保存到数组，从而返回最后的结果给value

该方案入侵性小，不需要改变原函数，但是性能方面，相比非递归的循环，慢了不少

var tco = function (f) {
  var value
  var active = false
  var accumulated = []

  return function accumulator () {
    accumulated.push(arguments)
    if (!active) {
      active = true
      while (accumulated.length) {
        value = f.apply(this, accumulated.shift())
      }
      active = false
      return value
    }
  }
}

const sum = tco(function(x, y) {
  if (y > 0) {
    return sum(x + 1, y - 1)
  } else {
    return x
  }
})

console.log( sum(1, 100000) ) // => 100001

结论

在JavaScript完全支持尾递归调用之前，上面的方案可以临时使用

发布了一个lib tco-node方便大家使用，星星✨是对我最大的鼓励