递归优化

函数式编程
3.1k words

递归的本质与风险

递归是函数调用自身的过程，由”递”（向下调用）和”归”（返回结果）两个阶段组成。虽然递归代码优雅简洁，但也带来了栈溢出的风险，尤其是在处理较大输入时。

🌰 示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 *  factorial 是一个阶乘算法
 */
function factorial(n) {
  if (n === 1) {
    // 当 n 等于 1 时，递归要开始出栈了。 打印当前的调用栈信息
    console.trace()
    return 1 // 归
  }

  // 函数自己调用自己
  return n * factorial(n - 1) // 递
}

/** 传入的数字有多个即会调用自己多少次 */
factorial(3) // 6 => 1 * 2 * 3
factorial(4) // 24 => 1 * 2 * 3 * 4

这个实现中，每次递归调用都需要保存在调用栈中等待子调用完成，当 n 很大时就会导致栈溢出。

优化方法

1. 尾递归优化

关键区别：普通递归返回时需要进行额外计算(n \* factorial(n-1))，而尾递归直接返回下一次递归的结果，编译器可以复用当前栈帧。

注意： 在 JavaScript 中，只有特定环境（如 Safari）支持尾调用优化(TCO)，其他环境仍可能栈溢出。

1
2
3
4
5
6
7
function factorial(n, total = 1) {
  if (n === 1) {
    return total
  }
  // 最后一步直接返回 factorial 的执行结果，无需等待其他操作
  return factorial(n - 1, n * total)
}

2. 循环替代

1
2
3
4
5
6
7
function factorial(n) {
  let result = 1
  for (let i = 1; i <= n; i++) {
    result *= i
  }
  return result
}

将递归转换为循环是最彻底的解决方案

3. 蹦床函数(Trampoline)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function factorial(n, total = 1) {
  if (n === 1) return total
  // 返回一个新的函数而不是立即执行
  return () => factorial(n - 1, n * total)
}

function trampoline(f) {
  let result = f()
  while (typeof result === 'function') {
    result = result()
  }
  return result
}

// 使用方式
const result = trampoline(() => factorial(10000, 1))

蹦床技术通过返回函数而非直接递归调用，将递归转换为迭代，有效避免栈溢出。

4. 记忆化(Memoization)

记忆化是一种优化技术，通过缓存函数调用结果来避免重复计算。这在递归中尤其有效，比如斐波那契数列计算。

未优化版本
1
2
3
4
5
6
7
8
9
10
function fibonacci(n) {
  if (n <= 1) return n
  return fibonacci(n - 1) + fibonacci(n - 2)
}

// 计算 fibonacci(40) 会非常慢
console.time('未优化')
console.log(fibonacci(40))
console.timeEnd('未优化')
// 可能需要几秒甚至更长时间

这个实现存在大量重复计算。例如，计算fibonacci(5)时，fibonacci(3)被计算两次，fibonacci(2)被计算三次。

优化版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function fibonacciWithMemo(n, memo = {}) {
  // 检查结果是否已经计算过
  if (memo[n] !== undefined) return memo[n]

  // 基础情况
  if (n <= 1) return n

  // 计算结果并存入缓存
  memo[n] = fibonacciWithMemo(n - 1, memo) + fibonacciWithMemo(n - 2, memo)
  return memo[n]
}

// 性能对比
console.time('记忆化')
console.log(fibonacciWithMemo(40))
console.timeEnd('记忆化')
// 应该非常快，几毫秒内完成
使用闭包实现记忆化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function memoizedFibonacci() {
  const cache = {}

  return function fib(n) {
    if (n in cache) {
      return cache[n]
    }

    let result
    if (n <= 1) {
      result = n
    } else {
      result = fib(n - 1) + fib(n - 2)
    }

    cache[n] = result
    return result
  }
}

const fib = memoizedFibonacci()
console.time('闭包记忆化')
console.log(fib(40))
console.timeEnd('闭包记忆化')
通用记忆化函数

可以创建一个通用的记忆化函数，用于优化任何纯函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function memoize(fn) {
  const cache = {}

  return function (...args) {
    const key = JSON.stringify(args)

    if (key in cache) {
      return cache[key]
    }

    const result = fn.apply(this, args)
    cache[key] = result
    return result
  }
}

// 使用通用记忆化函数优化斐波那契
function rawFibonacci(n) {
  if (n <= 1) return n
  return rawFibonacci(n - 1) + rawFibonacci(n - 2)
}

const memoizedFib = memoize(rawFibonacci)
console.time('通用记忆化')
console.log(memoizedFib(40))
console.timeEnd('通用记忆化')

记忆化的缺点是增加了空间复杂度，但对于重复计算特别多的递归函数，性能提升非常显著。在实际应用中，可以根据具体情况选择是否使用记忆化，或者结合其他优化技术一起使用

总结与建议

  1. 尾递归优化：当递归是函数的最后一个操作，且没有依赖递归返回值的其他计算时最有效
  2. 循环替代：简单直接，适用于大多数递归场景
  3. 蹦床函数：在不支持尾调用优化的环境中模拟尾递归优化效果
  4. 记忆化(Memoization)：对于有大量重复计算的递归（如斐波那契），可以加入缓存

最后，选择哪种优化策略应基于具体场景、性能需求和代码可读性的平衡考量。

Comments