JS 递归梳理

我心飞翔 分类:javascript

原文地址

有输入没有输出 === 白学,本文记录学习 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
 

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

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

image.png

尾递归

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

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 项为例图示:

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

  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中的尾递归及其优化

什么是图灵完备

尾调用优化

回复

我来回复
  • 暂无回复内容