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

递归与迭代

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

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

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

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

斐波那契数列

循环语句

  1. const fibonacci = n => {
  2.   if (n === 0 || n === 1) return n
  3.   let i = 1,
  4.     current,
  5.     previous,
  6.     next
  7.     while (i < n) {
  8.     previous = current || 0
  9.     current = next || 1 
  10.     next = current + previous
  11.     i++
  12.   }
  13.   return next
  14. }

递归

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

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

尾递归

尾调用

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

  1. const foo = () => {
  2.     // do something 
  3. }
  4. const fn = () => {
  5.   // do something
  6.   return foo()       // line 6
  7. }
  8. 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 项为例图示：
递归 -> 尾递归思路：想办法把函数的执行逻辑通过参数传递给下一次调用，对于不同的逻辑得思考如何抽象，抽象能力需要大量练习。
由于：

  1. 虽然在 Node6、Node7 中可以使用命令行参数 --harmony-tailcalls 开启尾递归优化功能。但是这个特性已经被 V8 移除了，对应的 Node8 之后的版本都已经没有了尾递归优化功能。
  2. 在 Chrome 之前的某些版本确实可以通过 chrome://flags/#enable-javascript-harmony 开启，但是也已经被移除了。

因为尾递归优化会破坏函数的调用栈信息，TC39 也正在寻找新的 js 语法来显式指明需要使用尾递归优化。tc39/proposal-ptc-syntax

据 justjavac 测试结果，Firefox、Chrome、Node.js 都不支持，其他引擎没有测试，我猜应该也都已经去掉了对尾递归优化的支持。

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中的尾递归及其优化
什么是图灵完备
尾调用优化