代码解剖 - 优化递归函数

递归函数

递归是一种编程技术，通过将问题分解为相同问题的较小实例并计算每个实例的解决方案来计算最终解决方案。最常见的实现方式是调用自身的函数，每次减小问题的规模，直到达到一个解决方案要么很容易计算，要么已经知道的问题实例。让我们看一个非常著名的例子，使用递归在JavaScript中实现计算斐波那契数列的第n项：

const fibonacciNumber = n =>
  n < 2 ? fibonacciNumber(n - 1) + fibonacciNumber(n - 2) : n;

为了更好地理解递归，让我们在每个return之前添加一个console.log()调用，并弄清楚到底发生了什么：

const fibonacciNumber = n => {
  console.log(`[CALLED] fibonacciNumber(${n})`);
  const r = n >= 2 ? fibonacciNumber(n - 1) + fibonacciNumber(n - 2) : n;
  console.log(`[RETURN] ${r} for n=${n}`);
  return r;
}

fibonacciNumber(4);
// [CALLED] fibonacciNumber(4)
// [CALLED] fibonacciNumber(3)
// [CALLED] fibonacciNumber(2)
// [CALLED] fibonacciNumber(1)
// [RETURN] 1 for n=1
// [CALLED] fibonacciNumber(0)
// [RETURN] 0 for n=0
// [RETURN] 1 for n=2
// [CALLED] fibonacciNumber(1)
// [RETURN] 1 for n=1
// [RETURN] 2 for n=3
// [CALLED] fibonacciNumber(2)
// [CALLED] fibonacciNumber(1)
// [RETURN] 1 for n=1
// [CALLED] fibonacciNumber(0)
// [RETURN] 0 for n=0
// [RETURN] 1 for n=2
// [RETURN] 3 for n=4

正如你所见，对于每个n的值，fibonacciNumber将被调用两次，一次是n - 1，一次是n - 2，并且这将继续，直到它被调用为1或0为止。虽然这种写法简单易懂，但效率低下，因为它需要计算相同的值超过一次。

计算记忆化

解决这个问题的方法，也是加速递归函数的第一个技巧，是使用记忆化。我们之前已经发布了一篇关于记忆化的精彩博文，所以一定要去看一下，了解更多关于这个主题的内容。下面是我们使用记忆化的fibonacciNumber函数：

const fibonacciCache = new Map();

const fibonacciNumber = n => {
  console.log(`[调用] fibonacciNumber(${n})`);
  const cacheKey = `${n}`;
  let r;
  if(fibonacciCache.has(cacheKey)) {
    r = fibonacciCache.get(cacheKey);
    console.log(`[缓存] ${n} 的缓存命中: ${r}`);
  }
  else {
    r = n >= 2 ? fibonacciNumber(n - 1) + fibonacciNumber(n - 2) : n;
    fibonacciCache.set(cacheKey, r);
    console.log(`[计算] 计算并存储 ${n} 的值: ${r}`);
  }
  return r;
}

fibonacciNumber(4);
// [调用] fibonacciNumber(4)
// [调用] fibonacciNumber(3)
// [调用] fibonacciNumber(2)
// [调用] fibonacciNumber(1)
// [计算] 计算并存储 1 的值: 1
// [调用] fibonacciNumber(0)
// [计算] 计算并存储 0 的值: 0
// [计算] 计算并存储 2 的值: 1
// [调用] fibonacciNumber(1)
// [缓存] 1 的缓存命中: 1
// [计算] 计算并存储 3 的值: 2
// [调用] fibonacciNumber(2)
// [缓存] 2 的缓存命中: 1
// [计算] 计算并存储 4 的值: 3

如上例所示，每个 n 的值只计算一次。尽管斐波那契数列不需要进行任何昂贵的计算，但对于更加计算密集的问题，这可能会产生巨大的差异。在 n 的值较大且计算次数显著增加时，这种差异将更加明显。

使用迭代

第二个也是最后一个技巧源于递归编程的定义。如果我们可以解决一个较小问题的实例，并将其用于解决一个较大问题的实例，那么我们应该可以从较小问题迭代到较大问题，而不是递归。下面是我们的 fibonacciNumber 函数的迭代实现：

const fibonacciNumber = n => {
  let r = 0, l = 1, s = 0;
  for(let i = 0; i < n; i++) {
    r = l;
    l = s;
    s = r + l;
    console.log(`[计算] i = ${i}: r = ${r}, l = ${l}, s = ${s}`);
  }
  return s;
}

fibonacciNumber(4);
// [计算] i = 0: r = 1, l = 0, s = 1
// [计算] i = 1: r = 0, l = 1, s = 1
// [计算] i = 2: r = 1, l = 1, s = 2
// [计算] i = 3: r = 1, l = 2, s = 3

上面的迭代解决方案与记忆化解决方案进行了相同的计算，但由于两个关键原因，它的性能更好。首先，没有缓存，这会占用内存空间，使后一种实现需要更少的资源。同样地，由于没有递归调用或缓存命中的检查，代码执行性能更好，需要更少的资源。

然而，您必须牢记您递归代码的实际用例，并非常小心地进行优化。如果递归函数多次使用不同的参数进行调用，记忆化可以是一种更强大的工具，因为其缓存在调用之间保持不变，而迭代对于较少使用的递归计算可能更快。始终注意您的代码，并针对您知道或预计的常见情况进行优化。