递归执行上下文和堆栈
共 1973字，需浏览 4分钟
·
2021-02-04 21:58
递归执行上下文和堆栈
我们接着昨天的递归继续讲述关于递归的执行上下文，以及堆栈。
现在，让我们检查一下递归调用是如何工作的。为此，我们将深入研究功能。
有关正在运行的功能的执行过程的信息存储在其执行上下文中。
执行上下文是一个内部数据结构，它包含关于函数执行的详细信息:控制流现在的位置、当前变量、该变量的值(我们在这里不使用它)和很少的其他内部细节
一个函数调用只有一个与之相关的执行上下文。
当一个函数进行嵌套调用时，会发生以下情况:
当前函数暂停。 与它相关的执行上下文被保存在一个特殊的数据结构中，称为执行上下文堆栈。 执行嵌套调用。 在它结束后，从堆栈中检索旧的执行上下文，外部函数从停止的地方恢复。
让我们看看pow(2,3)调用过程中发生了什么。
pow(2, 3)
在调用pow(2,3)的开始，执行上下文将存储变量:x = 2, n = 3，执行流在函数的第1行。
我们可以把它概括为:
Context: { x: 2, n: 3, at line 1 } call: pow(2, 3)
这时函数开始执行，如果 n == 1 是假的，所以流继续进入if的第二个分支:
function pow(x, n) {
if (n == 1) {
return x;
} else {
return x * pow(x, n - 1);
}
}
alert( pow(2, 3) );
变量是相同的，但是换行了，所以上下文现在是:
Context: { x: 2, n: 3, at line 5 } call: pow(2, 3)
计算x * power (x, n - 1)，我们需要用新的参数power(2,2)对power进行子调用。
pow(2, 2)
执行嵌套调用时，JavaScript会在执行上下文栈中记住当前的执行上下文。
我们称这个函数为pow，但这完全不重要。所有函数的过程都是一样的:
当前上下文被“记住”在堆栈的顶部。
为子调用创建新的上下文。
当子调用完成时——前一个上下文从堆栈中弹出，并继续执行。
下面是我们进入子调用pow(2,2)时的上下文堆栈:
Context: { x: 2, n: 2, at line 1 } call: pow(2, 2)
Context: { x: 2, n: 3, at line 5 } call: pow(2, 3)
新的当前执行上下文位于顶部(和粗体)，前面记住的上下文位于下面。
当我们完成子调用时，很容易恢复前面的上下文，因为它保留了两个变量和它停止的代码的确切位置。
pow(2, 1
过程重复:在第5行进行新的子调用，现在参数x=2, n=1。
一个新的执行上下文被创建，之前的执行上下文被压入栈顶:
Context: { x: 2, n: 1, at line 1 } call: pow(2, 1)
Context: { x: 2, n: 2, at line 5 } call: pow(2, 2)
现在有2个旧的上下文，1个正在运行pow(2,1)。
The exit
在执行pow(2,1)时，与之前不同，条件n == 1是真实的，因此if的第一个分支工作:
function pow(x, n) {
if (n == 1) {
return x;
} else {
return x * pow(x, n - 1);
}
}
没有更多的嵌套调用,因此函数完成,返回2。
当函数结束时，不再需要它的执行上下文，因此它被从内存中删除。前一个被从栈顶恢复:
Context: { x: 2, n: 2, at line 5 } call: pow(2, 2)
Context: { x: 2, n: 3, at line 5 } call: pow(2, 3)
pow(2,2)的执行重新开始。它有子调用pow(2,1)的结果，所以它也可以完成x * pow(x, n - 1)的求值，返回4。
然后恢复之前的上下文:
Context: { x: 2, n: 3, at line 5 } call: pow(2, 3)
当它完成时，我们得到pow(2,3) = 8的结果。
在这种情况下，递归深度是:3。
从上面的例子中可以看出，递归深度等于堆栈中上下文的最大数量。
注意内存要求。上下文需要内存。在我们的例子中，n的幂实际上需要n个上下文的内存，对于所有n的较小值。
基于循环的算法更节省内存:
function pow(x, n) {
let result = 1;
for (let i = 0; i < n; i++) {
result *= x;
}
return result;
}