javascript递归_通过JavaScript了解递归和记忆

javascript递归

In this article, you’re going to learn how to use recursive programming, what it is, and how to optimize it for use in algorithms. We’ll be using JavaScript as our programming language of choice to understand the concept of recursion.

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

先决条件 (Prerequisites)

I’ll be using Big O Notation to compare optimization strategies, which you can brush up on here.

我将使用Big O表示法来比较优化策略，您可以在此处进行优化。

什么是递归？ (What is Recursion?)

Recursion is any time a function calls itself inside itself, potentially creating a infinite loop. If you’ve ever worked with canvas animations then you’ve already used recursion since we use an animate function that updates our animation before rerunning itself.

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

In the below example, we’re passing in a number, doubling it, then passing that value to itself again. In theory, this would continue forever but because computers are limited we generally can’t have infinite recursion. You’ll get an error like too much recursion or Maximum call stack size exceeded if you don’t include some exit condition to stop the function, in the following case as soon as it’s over 100:

在下面的示例中，我们传入一个数字，将其加倍，然后将该值再次传递给自身。从理论上讲，这将永远持续下去，但是由于计算机有限，所以我们通常无法进行无限递归。如果不包括某些退出条件来停止该函数，则会出现诸如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));

You’re probably thinking, “that’s cool and all, but can’t I just use a loop for anything recursion can do?”. Well yes, but actually no. Recursion comes in handy when dealing with various searching and sorting algorithms or traversing data structures that are more complicated than simple lists. When done correctly, you can also get much better performance, like O(log n) while all loops are O(n).

您可能会想，“这很酷，但是我不能仅使用循环来执行递归操作吗？” 是的，但是实际上没有。当处理各种搜索和排序算法或遍历比简单列表更复杂的数据结构时，递归非常方便。如果正确完成，您还可以获得更好的性能，例如O(log n)，而所有循环均为O(n)。

记忆化 (Memoization)

You don’t have to play around with recursion for long to realize that it’s pretty easy to overwhelm your computer. This is because most recursive functions are O(n^2) or even O(n!). Since JavaScript runs on call stacks every time a new recursive layer is added, a lot of memory and processing power must be used to manage it all, despite most of it being redundant.

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

Let’s try something simple like generating a fibonacci sequence. A fibonacci sequence is where every digit is the sum of the two items before it, 0, 1, 1, 2, 3, 5, 8, 12…

让我们尝试一些简单的事情，例如生成斐波那契数列。斐波那契数列是每个数字是其前两个项目的总和，即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...

That’s just horrendous. Using up resources for 1,000 layers of the same information is too much even for my, relatively, decent computer.

那太可怕了。即使对于我相对来说还不错的计算机来说，用完1000层相同信息的资源也太多了。

Instead, we can work around this by adding a storage variable, or a “memo”, that will contain our values as the stack progresses. Every time our function runs, its value will be added to its corresponding index in the memo and the next layer will refer to that to calculate our result.

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

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

问题 (Problem)

Let’s try applying this to another recursive function. This takes a number and outputs its factorial, so 3! should return 6 because 3x2x1=6.

让我们尝试将其应用于另一个递归函数。这需要一个数字并输出其阶乘，所以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

For me, anything above 12 crashes the page because this function has the complexity of O(n!) as each layer in the stack has to handle the complexity of the one before it.

对我来说，任何高于12的值都会使页面崩溃，因为此函数的复杂度为O(n！)，因为堆栈中的每一层都必须处理之前的那一层的复杂性。

Instead, let’s try memoizing it and see the difference.

取而代之的是，让我们尝试记住它，并观察其中的区别。

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

I don’t know about you, but I think that’s an incredible improvement, it can now handle 10,000 times the computations in 1/8th the time.

我不了解您，但是我认为这是令人难以置信的改进，现在它可以以1/8的速度处理10,000倍的计算。

总结思想 (Closing Thoughts)

Recursion is one of those things you need to get very comfortable with because it will return repeatedly, or haunt you, throughout your programming career. It will be essential for learning to traverse trees and lists and sort various data sets in the future.

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

翻译自: https://www.digitalocean.com/community/tutorials/js-understanding-recursion

javascript递归