通过JavaScript理解递归和记忆

在本文中，您将学习如何使用递归编程，它是什么，以及如何优化它以用于算法。我们将使用 JavaScript 作为我们选择的编程语言来理解递归的概念。

先决条件

我将使用 Big O Notation 来比较优化策略，您可以在这里上刷一下。

什么是递归？

递归是函数在自身内部调用自身的任何时候，可能会创建无限循环。如果您曾经使用过 canvas 动画，那么您已经使用过递归，因为我们使用 animate 函数在重新运行之前更新我们的动画。

在下面的示例中，我们传入一个数字，将其翻倍，然后再次将该值传递给自身。从理论上讲，这将永远持续下去，但由于计算机有限，我们通常不能进行无限递归。如果您不包含一些退出条件来停止该功能，您将收到类似 too much recursion 或 Maximum call stack size exceeded 的错误，在以下情况下，一旦超过 100：

const double = num => {
  num = num + num;
  console.log(num);

  if (num > 100) return 'Exit'; // Try removing this
  return double(num);
};

console.log(double(4));

您可能在想，“这很酷，但我不能只使用循环来完成递归可以做的任何事情吗？”。是的，但实际上没有。在处理各种搜索和排序算法或遍历比简单列表更复杂的数据结构时，递归会派上用场。正确完成后，您还可以获得更好的性能，例如 O(log n) 而所有循环都是 O(n)。

记忆

您不必长时间使用递归来意识到它很容易使您的计算机不堪重负。这是因为大多数递归函数都是 O(n^2) 甚至 O(n!)。由于每次添加新的递归层时 JavaScript 都会在调用堆栈上运行，因此必须使用大量内存和处理能力来管理这一切，尽管其中大部分是冗余的。

让我们尝试一些简单的事情，比如生成斐波那契数列。斐波那契数列是其中每个数字都是它之前的两项之和，0、1、1、2、3、5、8、12……

const fibonacci = num => {
  if (num < 2) return num;

  return fibonacci(num - 1) + fibonacci(num - 2);
};

for (let i = 0; i < 1000; i++) console.log(fibonacci(i)); // 3 minutes before page crashed...

这太可怕了。即使对于我相对不错的计算机来说，为 1,000 层相同的信息消耗资源也太多了。

相反，我们可以通过添加一个存储变量或“备忘录”来解决这个问题，它会随着堆栈的进行包含我们的值。每次我们的函数运行时，它的值都会被添加到备忘录中对应的索引中，下一层将引用它来计算我们的结果。

const fibonacci = (num, memo) => {
  memo = memo || {};

  if (memo[num]) return memo[num];
  if (num < 2) return num;

  return memo[num] = fibonacci(num - 1, memo) + fibonacci(num - 2, memo);
};

for (let i = 0; i < 1000; i++) console.log(fibonacci(i)); // 143 Milliseconds

问题

让我们尝试将其应用于另一个递归函数。这需要一个数字并输出它的阶乘，所以 3！应该返回 6，因为 3x2x1=6。

const factorial = n => {
  let num = n;

  if (n === 0) return 1;
  for (let i = 0; i < n; i++) {
    num = n * factorial(n - 1);
  };

  return num;
};

console.log(factorial(3)); // 7 Milliseconds
console.log(factorial(6)); // 8 Milliseconds
console.log(factorial(9)); // 15 Milliseconds
console.log(factorial(12)); // 11,588 Milliseconds

对我来说，任何超过 12 的东西都会导致页面崩溃，因为这个函数具有 O(n!) 的复杂性，因为堆栈中的每一层都必须处理它之前一层的复杂性。

相反，让我们尝试记忆它，看看有什么不同。

const factorial = (n, memo) => {
  memo = memo || {};

  if (memo[n]) return memo[n];
  if (n === 0) return 1;
  for (let i = 0; i < n; i++) {
    memo[n] = n * factorial(n - 1, memo);
  };

  return memo[n];
};

console.log(factorial(12));  // 4 milliseconds
console.log(factorial(120));  // 12 milliseconds
console.log(factorial(1200)); // 24 milliseconds
console.log(factorial(12000));  // 1408 milliseconds

我不了解你，但我认为这是一个令人难以置信的改进，它现在可以在 1/8 的时间内处理 10,000 倍的计算。

结束的想法

递归是您需要非常熟悉的事情之一，因为它会在您的整个编程生涯中反复出现或困扰您。将来学习遍历树和列表以及对各种数据集进行排序将是必不可少的。