递归优化

🌰 示例

递 和 归 是两个动作

/**
 *  factorial 是一个阶乘算法
 */
function factorial(n) {
  if (n === 1) {
    // 当 n 等于 1 时，递归要开始出栈了。 打印当前的调用栈信息
    console.trace()
    return 1 // 归
  }

  // 函数自己调用自己
  return n * factorial(n - 1) // 递
}

/** 传入的数字有多个即会调用自己多少次 */
factorial(3) // 6 => 1 * 2 * 3
factorial(4) // 24 => 1 * 2 * 3 * 4

🍐 factorial(4) 的栈信息

使用 console.trace() 发现当 n = 1时， 栈里有 4次 的函数调用。

给一个足够大的数字会发生爆栈

尾递归、尾调用 PTC

• 尾调用即为函数取个别名，互相调用。这样互相出栈进栈，可以减低爆栈的风险
• 尾递归则是在函数最后一步操作调用本身

为什么不是尾递归

在示例中 factorial 确实是在最后一行 return 调用自己，为什么不能称之为尾递归

function factorial(n) {
  if (n === 1) {
    return 1
  }

  // 最后一步执行的是 n * [factorial的执行结果]
  return n * factorial(n - 1)
}

修改成尾递归

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

  // 最后一步直接返回 factorial的执行结果
  return factorial(n - 1, n * (n - 1))
}

while 循环

递归本质上还是循环，直接用 while 拉平即可

let start = 10
let count = 1
while (start > 1) {
  count *= start--
}
console.log(count)

蹦床函数

function sum(n, toal = 0) {
  if (n === 0) return toal

  // 返回一个新的函数
  return sum.bind(null, n - 1, n + toal)
}

// 蹦床函数， 如果发现是函数则一直执行下去
function trampoline(f) {
  while (f instanceof Function) {
    f = f()
  }
  return f
}