递归执行上下文和堆栈

递归执行上下文和堆栈

我们接着昨天的递归继续讲述关于递归的执行上下文，以及堆栈。

现在，让我们检查一下递归调用是如何工作的。为此，我们将深入研究功能。

有关正在运行的功能的执行过程的信息存储在其执行上下文中。

执行上下文是一个内部数据结构，它包含关于函数执行的详细信息:控制流现在的位置、当前变量、该变量的值(我们在这里不使用它)和很少的其他内部细节

一个函数调用只有一个与之相关的执行上下文。

当一个函数进行嵌套调用时，会发生以下情况:

当前函数暂停。

与它相关的执行上下文被保存在一个特殊的数据结构中，称为执行上下文堆栈。

执行嵌套调用。

在它结束后，从堆栈中检索旧的执行上下文，外部函数从停止的地方恢复。

让我们看看pow(2,3)调用过程中发生了什么。

pow(2, 3)

在调用pow(2,3)的开始，执行上下文将存储变量:x = 2, n = 3，执行流在函数的第1行。

我们可以把它概括为:

这时函数开始执行，如果 是假的，所以流继续进入if的第二个分支:

变量是相同的，但是换行了，所以上下文现在是:

计算x * power (x, n - 1)，我们需要用新的参数power(2,2)对power进行子调用。

pow(2, 2)

执行嵌套调用时，JavaScript会在执行上下文栈中记住当前的执行上下文。

我们称这个函数为pow，但这完全不重要。所有函数的过程都是一样的:

当前上下文被“记住”在堆栈的顶部。

为子调用创建新的上下文。

当子调用完成时——前一个上下文从堆栈中弹出，并继续执行。

下面是我们进入子调用pow(2,2)时的上下文堆栈:

新的当前执行上下文位于顶部(和粗体)，前面记住的上下文位于下面。

当我们完成子调用时，很容易恢复前面的上下文，因为它保留了两个变量和它停止的代码的确切位置。

pow(2, 1

过程重复:在第5行进行新的子调用，现在参数x=2, n=1。

一个新的执行上下文被创建，之前的执行上下文被压入栈顶:

现在有2个旧的上下文，1个正在运行pow(2,1)。

The exit

在执行pow(2,1)时，与之前不同，条件n == 1是真实的，因此if的第一个分支工作:

没有更多的嵌套调用,因此函数完成,返回2。

当函数结束时，不再需要它的执行上下文，因此它被从内存中删除。前一个被从栈顶恢复:

pow(2,2)的执行重新开始。它有子调用pow(2,1)的结果，所以它也可以完成x * pow(x, n - 1)的求值，返回4。

然后恢复之前的上下文:

当它完成时，我们得到pow(2,3) = 8的结果。

在这种情况下，递归深度是:3。

从上面的例子中可以看出，递归深度等于堆栈中上下文的最大数量。

注意内存要求。上下文需要内存。在我们的例子中，n的幂实际上需要n个上下文的内存，对于所有n的较小值。

基于循环的算法更节省内存: