Recursion and Stack

JavaScript Recursion and Stack （JavaScript递归和堆栈）

Recursion is the process in the framework of which a function calls itself, either directly or indirectly. It is especially handy in situations when there is a necessity to split a single task into several simple ones. （递归是函数在其中直接或间接调用自身的过程。在需要将单个任务分成几个简单任务的情况下，它尤其方便。）

Above all, with the help of recursion, you can write quite elegant codes. （最重要的是，借助递归，您可以编写相当优雅的代码。）

To understand better what recursion is, you need to start with something simple. Write a function factorial(n), in Math, a non-negative integer’s factorial is the product of all positive integer less than or equal to it. n! denotes the factorial of the integer:

factorial(1) = 1 （factorial (1) = 1）

factorial(2) = 2 （factorial (2) = 2）

factorial(3) = 6 （factorial (3) = 6）

factorial(4) = 24 （factorial (4) = 24）

You can implement it in two ways. （您可以通过两种方式实现它。）

function factorial(n) {
 let result = 1;
 for (let i = n; i > 1; i--) {
   result *= i;
 }
 console.log(result);
}
factorial(5);

Note that, as a rule, the recursive solution is shorter than the iterative one. If we rewrite the same and use the conditional operator ? instead of if for making factorial(n) compact but still readable, it can look like this:

function factorial(n) {
 return ((n <= 1) ? 1 : (n * factorial(n - 1)));
}
console.log(factorial(5));

JavaScript engine limits the maximum depth of recursion. It, usually, should be 10000, but some engines might allow more. （JavaScript引擎限制最大递归深度。它通常应该是10000 ，但有些引擎可能允许更多。）

The Execution Context and Stack

The Execution Context and Stack （执行上下文和堆栈）

The execution context can be described as an internal data structure containing details about the execution of a function, in which the control flow is now, the current variables, the value of this and other internal details. （执行上下文可以描述为包含有关函数执行的详细信息的内部数据结构，其中控制流现在、当前变量、this的值和其他内部详细信息。）

One call of a function has one execution context connected with it. （函数的一个调用有一个与之关联的执行上下文。）

When a nested call is made by a function, the following occurs:

A pause of the current function. （-当前函数的暂停。）
The execution context linked with it is remembered in a unique data structure known as execution context stack. （-与其链接的执行上下文被记忆在一个称为执行上下文堆栈的独特数据结构中。）
Execution of the nested call. （-执行嵌套调用。）
After it finishes, the previous execution context is recovered from the stack. The external function is resumed from where it was interrupted. （-完成后，从堆栈中恢复先前的执行上下文。外部函数从中断的地方恢复。）

During the factorial(4), happens the following:

At the start of it, the execution context stores n = 4 variable. The execution flow is at the function’s line 1. （在开始时，执行上下文存储n = 4个变量。执行流程位于函数的第1行。）

It looks like this:

Context: { n: 4, at line 1 } factorial(4)

The n <= 1, n is 1, and the flow will go on into the second
branch of if. （if的分支。）

Here is an example:

function factorial(n) {
 if (n <= 1) {
   return 1;
 } else {
   return n * factorial(n - 1);
 }
}
console.log(factorial(4));

As the variables are the same, but the line is changed, the context looks like this:

Context: { n: 4, at line 5 } factorial(4)

For calculating n * factorial(n - 1), it is necessary to implement a subcall of the factorial with new factorial(3) arguments. （为了计算n *阶乘（ n - 1 ），有必要使用新的阶乘（ 3 ）参数实现阶乘的子调用。）

factorial(3)

For doing a nested call, JavaScript remembers the present execution context in the execution context stack. （对于执行嵌套调用， JavaScript会记住执行上下文堆栈中的当前执行上下文。）

The factorial function is called. For all the functions, the process is as follows:

The present context is remembered on the stack top. （-堆栈顶部会记住当前上下文。）
For the subcall, a new context is created. （-对于子调用，将创建一个新上下文。）
When the subcall ends, the old context is popped from the stack. Its execution goes on. （-当子调用结束时，旧的上下文将从堆栈中弹出。它的执行还在继续。）

Below you can see the context stack at the time you enter the subcall factorial(3):

Context: { n: 3, at line 1 } factorial(3)
Context: { n: 4, at line 5 } factorial(4)

factorial(2)

Then you can see the context stack at the time you enter the subcall factorial(2):

Context: { n: 2, at line 1 } factorial(2)
Context: { n: 3, at line 5 } factorial(3)
Context: { n: 4, at line 5 } factorial(4)

When finishing the subcall- it is easier to restore the old context, as it keeps variables, as well as the precise place where it stopped. （完成子调用时，更容易恢复旧的上下文，因为它保留了变量以及停止的确切位置。）

factorial(1)

A new subcall is implemented in line 5. The arguments are n=1. （在第5行中实现了一个新的子调用。参数为n = 1。）

As a rule, a new execution context is made, and the previous execution is pushed on top of the stack, like this:

Context: { n: 1, at line 1 } factorial(1)
Context: { n: 2, at line 5 } factorial(2)
Context: { n: 3, at line 5 } factorial(3)
Context: { n: 4, at line 5 } factorial(4)

You can notice 3 previous contexts and 1 currently running for factorial(1). （您可以注意到3个以前的上下文和1个当前正在运行的阶乘（ 1 ）。）

The Exit

The Exit （出口）

In the process of factorial(1) execution, unlike in the previous situations, n <= 1 is truthy, and the first if branch works. It looks like this:

function factorial(n) {
 if (n <= 1) {
   return 1;
 } else {
   return n * factorial(n - 1);
 }
}

As no nested calls exist, the function ends, returning 1. （由于不存在嵌套调用，函数结束，返回1。）

The execution context is not necessary anymore, as the function ends. Therefore, it is deleted from the memory. The previous one is restored:

Context: {n: 4, at line 5 } factorial( 4)

After its end, you can have a result of factorial(4) = 24. （结束后，可以得到阶乘(4) = 24的结果。）

It is essential to follow the memory requirements. For example, a loop-based algorithm can save memory. （遵循内存要求至关重要。例如，基于循环的算法可以节省内存。）

Let’s check out the following example:

function factorial(n) {
 let result = 1;
 for (let i = n; i > 1; i--) {
   result *= i;
 }
 return result;
}
console.log(factorial(4));

Note that you can rewrite any recursion as a loop. The loop option might be made much more effective. （请注意，您可以将任何递归重写为循环。循环选项可能会更有效。）

Recursive Structures

Recursive Structures （递归结构）

A recursive data structure can be described as a structure replicating itself into parts. Let’s consider the following case: In an HTML-document, an HTML-tag may contain a list of HTML-comments, text parts, other HTML-tags. It’s a recursive definition. Now, let’s examine another recursive structure, called “Linked list.” It can even become a better alternative for arrays.

Here is an example:

let list = {
 value: "a",
 next: {
   value: "b",
   next: {
     value: "c",
     next: {
       value: "d",
       next: null
     }
   }
 }
};
console.log(list);

The alternative code is as follows:

let list = {
 value: "a"
};
list.next = {
 value: "b"
};
list.next.next = {
 value: "c"
};
list.next.next.next = {
 value: "d"
};
list.next.next.next.next = null;
console.log(list);

Summary

Summary （概要）

Recursion is a programming pattern used for calling a function itself. You can use recursive functions for solving tasks in quite elegant ways. Its arguments make the tasks simpler. （递归是一种用于调用函数本身的编程模式。您可以使用递归函数以非常优雅的方式解决任务。它的论点使任务更简单。）

请遵守《互联网环境法规》文明发言，欢迎讨论问题

Recursion and Stack

The Execution Context and Stack

factorial(3)

factorial(2)

factorial(1)

The Exit

Recursive Structures

Summary

人工客服

工单服务

投诉建议

Recursion and Stack

The Execution Context and Stack #

factorial(3) #

factorial(2) #

factorial(1) #

The Exit #

Recursive Structures #

Summary #

人工客服

工单服务

投诉建议

The Execution Context and Stack

factorial(3)

factorial(2)

factorial(1)

The Exit

Recursive Structures

Summary