在本文中，您将学习如何使用递归编程，它是什么，以及如何优化它以用于算法。 我们将使用 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 倍的计算。
结束的想法
递归是您需要非常熟悉的事情之一，因为它会在您的整个编程生涯中反复出现或困扰您。 将来学习遍历树和列表以及对各种数据集进行排序将是必不可少的。
