关于递归及优化

[heycn]

递归例子

阶乘

j = n => n === 1 ? 1 : n * j(n-1)

斐波那契数列

fib = n =>
  n === 0 ? 0 :
  n === 1 ? 1 :
  fib(n-1) + fib(n-2)

注意：每次进入函数需要往 调用栈 里「压栈」，调用栈 用来记录「回到哪」，如果需要记录得过多，就会「爆栈」。

所以，需要降低「压栈」或者计算次数，以下是优化方案

优化手段

尾递归优化

使用迭代代替递归

fib = n => fib_inner()

fib_inner = (start, end, prev1, prev2) =>
  start === end ? prev1 + prev2
    : fib_inner(start+1, end, prev1+prev2, prev1)

这就是「尾递归」

为什么尾递归可以优化？因为不用「压栈」了，「压栈」的目的是为了记录回到哪，那如果我不回来，那我就不需要「压栈」了。

注意：但是！JS 有 Bug，就算你不压栈，它还是会把一些不相关的操作压进去（例如环境），所以，JS 不存在「尾递归优化」！
所以，以上代码，依然会「压栈」，虽然会快一些，但是没有什么区别。

改写成循环

所有的递归都可以改写成循环

fib_loop = n => {
  let array = [0, 1]
  for(let i = 0; i <= n-2; i++) {
    array[i+2] = array[i+1] + array[i]
  }
  return array[array.length-1]
}

以上代码把结果都记录在数组里面，那么就不需要重复的计算某些值了。

以下是 ChatGPT 对以上代码的解释：

以上代码是一个计算斐波那契数列第 n 项的函数，采用了循环方式来计算。具体解释如下：

1. `fib_loop = n => {...}`：定义一个名为 `fib_loop` 的函数，它接受一个参数 `n`，使用箭头函数方式定义。
2. `let array = [0, 1]`：初始化一个数组 `array`，它包含斐波那契数列的初始两个元素。
3. `for(let i = 0; i <= n-2; i++) {...}`：循环遍历 `array` 数组，从第3项开始依次计算出斐波那契数列的每一项，直到计算出第n项。
4. `array[i+2] = array[i+1] + array[i]`：计算斐波那契数列的每一项，并存储在 `array` 数组中。
5. `return array[array.length-1]`：返回 `array` 数组的最后一项，也就是斐波那契数列的第 n 项。

递归好像没什么用？

使用循环就能解决，这样看起来递归很无用呀？是的，有时候递归就是这样。

因为 JS 在递归方面就没有提供很好的工具，所以在 JS 中写递归会让你的同事看不懂，并且性能又差，那怎么办呢？

使用「记忆化」 —— 这是一个很好的解决办法。

记忆化

如果我曾经算过了，那就不要算了

可以减少重复计算，大大减低压栈次数

以下是 Lodash 记忆化函数的实现：lodash/memoize.js