JS 递归梳理

原文地址

有输入没有输出 === 白学，本文记录学习 JS 递归 -> 递归优化手段 -> 尾递归的 trampoline 实践过程。

递归与迭代

尤记得几年前第一次学习递归时被绕晕之后的总结：递归简言之就是自己调用自己，递出去再归回来。其实就是 2 个特征：

• 自己调用自己的函数
• 必须要有终止条件以退出这个循环调用

之后接触到图灵完备的概念，了解到编程语言的设计符合图灵完备就可以映射现实，解决一切可计算的问题。简单来说一门图灵完备语言的本质只要具备顺序执行、分支、循环这几个特性即可，才恍然大悟递归与迭代其实在一定程度上是等效的。

纯函数式语言中是没有循环语句的，而 JS 博采众长，借鉴了不同语言的特性，所以同时存在递归与循环语句两种特性。 图灵完备性无法解决不可计算的问题，如停机问题：不能判断死循环（这就是为什么死循环会卡死的原因）。 由于递归中循环调用会不停压栈，JS 引擎对最大调用栈作限制也是为了预防不可计算性问题吧。

斐波那契数列

循环语句

const fibonacci = n => {
  if (n === 0 || n === 1) return n
  let i = 1,
    current,
    previous,
    next
  while (i < n) {
    previous = current || 0
    current = next || 1 
    next = current + previous
    i++
  }
  return next
}

递归

const fibonacci = n => {
  if (n === 0 || n === 1) return n
  return fibonacci(n - 1) + fibonacci(n - 2)
}

很明显递归的写法简洁很多，但是存在调用栈过深的问题， fibonacci(100000) 直接报错栈溢出，于是出现了尾递归优化的方案。

尾递归

尾调用

尾调用是在 return 关键字处的函数调用，即尾部调用，形如以下：

const foo = () => {
  // do something 
}
const fn = () => {
  // do something
  return foo()       // line 6
}
const result = fn()  // line 8

代码执行不同阶段的调用栈状况如下：

当执行至 line 6 时，函数 fn 的主逻辑已经完毕，fn 执行上下文唯一的作用就是记录出栈时要回到的位置：line 8，完全可以优化掉这一层，如下：

尾递归

尾递归就是使用尾调用的递归了，作用是优化掉过深的调用栈，改写斐波那契数列为尾递归：

const fibonacci = (n, item0 = 0, item1 = 1) => {
  if (n === 0) return 0
  if (n === 1) return item1
  return fibonacci(n - 1, item1, item0 + item1)
}

斐波那契数列尾递归分析：斐波那契数列第 n 项的值为前两项之和，反过来想，我只要从第 0 项经过 n 次迭代就能得出第 n 项的值。参数一为数列中的第几项，参数二与参数三为连续的两项（从第 0 第 1 项开始），每一次尾调用迭代一次连续的两项，以求第 5 项为例图示：

递归 -> 尾递归思路：想办法把函数的执行逻辑通过参数传递给下一次调用，对于不同的逻辑得思考如何抽象，抽象能力需要大量练习。 由于：

JS 引擎如果不对尾调用优化，难道就没办法愉快地使用尾递归了么？不，还有办法。

Trampoline

Trampoline（蹦床？）可以自动消费经过尾递归改造的函数，目的就是为了消除过多的调用栈，如下：

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

const fibonacci = (n, item0 = 0, item1 = 1) => {
  if (n === 0) return 0
  if (n === 1) {
    debugger
    return item1
  }
  return () => fibonacci(n - 1, item1, item0 + item1) // 尾递归此处包一层函数再返回
}

const f = trampoline(fibonacci)

console.log(f(1000000)) // 不会报错栈溢出

总结

可以使用 trampoline 包装尾递归优化栈溢出问题，但有些逻辑把递归改造为尾递归可能要思虑良久。

循环与递归一定程度上是等效的，只是分别适用于不同的场景，有选择的使用，能愉快地编码就行了。

参考

Javascript中的尾递归及其优化

什么是图灵完备

尾调用优化