递归

• 递归调用
• 递归弊端
• 尾调用
• 尾递归
• 蹦床优化（Trampoline）
• BMW WARNING

递归调用

递归是一种不使用 for 或者 while 等编程语言预置 API 而实现循环调用的一种编程技巧。
通常实现为函数调用自身。

递归问题的特点为
后续问题为原始问题的简单子问题，可以统一为一个方程求解。
问题需要一个出口。

即其实现的关键是找到

• 递归方程
• 递归结束条件

一个简单的正整数求和函数用递归实现如下

const sum = (n) => {
  if (n <= 1) return n
  return sum(n - 1) + n
}

斐波那契数列递归实现如下

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

递归弊端

如 JS 等大多数语言，递归嵌套调用时，会保持跟踪函数执行上下文栈，最外层函数最后执行完成后才会销毁。
在调用sum(10)通过 Chrome 控制台可以看到执行到 n=5 时调用栈如下

这些最底层调用栈最后释放。
当递归过深时通常会导致栈溢出。

Uncaught RangeError: Maximum call stack size exceeded

解决方式通常为尾调用优化和蹦床函数。

尾调用

尾调用是指函数执行结束那一步调用的是下一个函数。
最后一步涉及计算或其他操作都不是尾调用。

function a() {
  function b() {}
  return b()
}

尾调用所做的优化在于用尾调用函数的执行上下文栈接替父函数执行上下文栈释放空间，这样函数栈不会累积。
尾调用需要在 ES6 下的严格模式开启。
目前只有 Safari 默认支持尾调用优化，其他浏览器默认不开启或不支持。
尾调用会导致调用栈不连续难以跟踪问题出现位置。

尾调用优化的条件就是确定外部栈帧没有必要存在，当外部执行上下文中包含尾调用函数执行所需要的变量时（即形成闭包），尾调用优化无法实现。
如下是《JavaScript 高级程序第四版》无法使用尾调用优化示例

function outer() {
  let a = 1
  function inner() {
    return a
  }
  return inner()
}

尾递归

尾递归是尾调用的一种特例。
尾递归是指函数执行结束那一步调用自身，即尾调用函数自身。

正整数求和函数的尾递归实现

const sum = (n, ret = 1) => {
  if (n <= 1) return ret
  return sum(n - 1, ret + n)
}

斐波那契数列的尾递归实现

function fibonacci(n, pre = 1, ret = 1) {
  if (n <= 2) {
    return ret
  }

  return fibonacci(n - 1, ret, ret + pre)
}

将递归转化为尾递归的技巧是把累积的值通过参数保存并传递。

尾递归增加了函数参数，通常增加的参数初始值固定。
可以通过 ES6 默认参数赋值解决。
另外可以使用偏函数和函数柯里化来解决。

偏函数简单实现版本

function fib(pre, ret, n) {
  if (n <= 2) {
    return ret
  }

  return fib(ret, ret + pre, n - 1)
}

const fibonacci = fib.bind(null, 1, 1)

使用封装的 partial 偏函数

function partial(fn, ...args) {
  return (...params) => fn(...args, ...params)
}
const fibonacci = partial(fib, 1, 1)

这里的偏函数需要改变原先实现 fibonacci 函数的顺序，可使用”_“版本来保留原先顺序。

蹦床优化（Trampoline）

递归蹦床优化的思路是将每次递归的函数放在循环中依次执行。
由于循环中需要执行函数，蹦床优化在尾递归(除开该递归边界)上改造。
sum 函数的蹦床优化

const sum = (n) => {
  const sumStep = (n, ret = 1) => {
    if (n <= 1) return ret
    return () => sumStep(n - 1, n + ret)
  }
  let ret = sumStep(n)
  while (typeof ret === 'function') {
    ret = ret()
  }
  return ret
}

封装蹦床函数

function trampoline(fn) {
  while (typeof fn === 'function') {
    fn = fn()
  }
  return fn
}

封装完成后需要把原递归函数尾调用改为返回不立即执行的匿名函数

const sum = (n, ret = 1) => {
  if (n <= 1) return ret
  return () => sum(n - 1, n + ret)
}

function fibonacci(n, pre = 1, ret = 1) {
  if (n <= 2) {
    return ret
  }

  return () => fibonacci(n - 1, ret, ret + pre)
}
trampoline(sum(100))
trampoline(fibonacci(10))

BMW WARNING

• Bulletin

本文首发于 skyline.show 欢迎访问，
文章实时更新，如果有什么错误或不严谨之处望请指出，十分感谢。
如果你觉得有用，欢迎到Github仓库点亮⭐️

I am a bucolic migant worker but I never walk backwards.

• Material

参考资料如下列出，部分引用可能遗漏或不可考，侵删。

• Warrant

本文作者： Skyline(lty)

文章链接：http://www.skyline.show/递归.html

授权声明： 本博客所有文章除特别声明外， 均采用 CC BY - NC - SA 3.0 协议。 转载请注明出处！