尾递归及蹦床函数

尾递归

• 递归只出现在函数体最后
• 递归返回值不属于表达式一部分 / 最后有仅且只有递归

求和

求 1 到 n 的和，函数调用栈的情况如上图所示

• 尾递归会覆盖当前栈的记录，而不创新新记录，避免栈溢出

递归版

function sum (n) {
  if (n === 1) return 1
  return n + sum(n - 1)
}

尾递归版

function sumWithTailRecursion (n, prevSum = 0) {
  if (n === 1) return prevSum + 1
  return sumWithTailRecursion(n - 1, prevSum + n)
}

迭代版

尾递归函数可以被改写成迭代形式

function sumWithIteration(n) {
  let prevSum = 0
  while (n >= 1) {
    prevSum += n
    n--
  }
  return prevSum
}

蹦床函数

通用尾递归转换迭代函数

const trampoline = f => (...args) => {
  const result = f(...args)
  while (typeof result === 'function') result = result()
  return result
}

用蹦床函数改写递归

const sumWithIteration = trampoline(sumWiteRecursion)

尾递归支持的情况

• ES 2015 规范中说明，为了保证函数的调用上下文始终可见，仅在严格模式开启自动尾递归优化。规范说明原文
• 除了iOS环境外，尾递归的自动和手动开启在大多数 JavaScript 运行环境都不被不支持。支持情况图表