遞歸執(zhí)行上下文和堆棧
遞歸執(zhí)行上下文和堆棧
我們接著昨天的遞歸繼續(xù)講述關(guān)于遞歸的執(zhí)行上下文，以及堆棧。
現(xiàn)在，讓我們檢查一下遞歸調(diào)用是如何工作的。為此，我們將深入研究功能。
有關(guān)正在運(yùn)行的功能的執(zhí)行過(guò)程的信息存儲(chǔ)在其執(zhí)行上下文中。
執(zhí)行上下文是一個(gè)內(nèi)部數(shù)據(jù)結(jié)構(gòu)，它包含關(guān)于函數(shù)執(zhí)行的詳細(xì)信息:控制流現(xiàn)在的位置、當(dāng)前變量、該變量的值(我們?cè)谶@里不使用它)和很少的其他內(nèi)部細(xì)節(jié)
一個(gè)函數(shù)調(diào)用只有一個(gè)與之相關(guān)的執(zhí)行上下文。
當(dāng)一個(gè)函數(shù)進(jìn)行嵌套調(diào)用時(shí)，會(huì)發(fā)生以下情況:
當(dāng)前函數(shù)暫停。 與它相關(guān)的執(zhí)行上下文被保存在一個(gè)特殊的數(shù)據(jù)結(jié)構(gòu)中，稱為執(zhí)行上下文堆棧。 執(zhí)行嵌套調(diào)用。 在它結(jié)束后，從堆棧中檢索舊的執(zhí)行上下文，外部函數(shù)從停止的地方恢復(fù)。
讓我們看看pow(2,3)調(diào)用過(guò)程中發(fā)生了什么。
pow(2, 3)
在調(diào)用pow(2,3)的開始，執(zhí)行上下文將存儲(chǔ)變量:x = 2, n = 3，執(zhí)行流在函數(shù)的第1行。
我們可以把它概括為:
Context:?{?x:?2,?n:?3,?at?line?1?}?call:?pow(2,?3)
這時(shí)函數(shù)開始執(zhí)行，如果 n == 1 是假的，所以流繼續(xù)進(jìn)入if的第二個(gè)分支:
function?pow(x,?n)?{
??if?(n?==?1)?{
????return?x;
??}?else?{
????return?x?*?pow(x,?n?-?1);
??}
}
alert(?pow(2,?3)?);
變量是相同的，但是換行了，所以上下文現(xiàn)在是:
Context:?{?x:?2,?n:?3,?at?line?5?}?call:?pow(2,?3)
計(jì)算x * power (x, n - 1)，我們需要用新的參數(shù)power(2,2)對(duì)power進(jìn)行子調(diào)用。
pow(2, 2)
執(zhí)行嵌套調(diào)用時(shí)，JavaScript會(huì)在執(zhí)行上下文棧中記住當(dāng)前的執(zhí)行上下文。
我們稱這個(gè)函數(shù)為pow，但這完全不重要。所有函數(shù)的過(guò)程都是一樣的:
當(dāng)前上下文被“記住”在堆棧的頂部。
為子調(diào)用創(chuàng)建新的上下文。
當(dāng)子調(diào)用完成時(shí)——前一個(gè)上下文從堆棧中彈出，并繼續(xù)執(zhí)行。
下面是我們進(jìn)入子調(diào)用pow(2,2)時(shí)的上下文堆棧:
Context:?{?x:?2,?n:?2,?at?line?1?}?call:?pow(2,?2)
Context:?{?x:?2,?n:?3,?at?line?5?}?call:?pow(2,?3)
新的當(dāng)前執(zhí)行上下文位于頂部(和粗體)，前面記住的上下文位于下面。
當(dāng)我們完成子調(diào)用時(shí)，很容易恢復(fù)前面的上下文，因?yàn)樗Ａ袅藘蓚€(gè)變量和它停止的代碼的確切位置。
pow(2, 1
過(guò)程重復(fù):在第5行進(jìn)行新的子調(diào)用，現(xiàn)在參數(shù)x=2, n=1。
一個(gè)新的執(zhí)行上下文被創(chuàng)建，之前的執(zhí)行上下文被壓入棧頂:
Context:?{?x:?2,?n:?1,?at?line?1?}?call:?pow(2,?1)
Context:?{?x:?2,?n:?2,?at?line?5?}?call:?pow(2,?2)
現(xiàn)在有2個(gè)舊的上下文，1個(gè)正在運(yùn)行pow(2,1)。
The exit
在執(zhí)行pow(2,1)時(shí)，與之前不同，條件n == 1是真實(shí)的，因此if的第一個(gè)分支工作:
function?pow(x,?n)?{
??if?(n?==?1)?{
????return?x;
??}?else?{
????return?x?*?pow(x,?n?-?1);
??}
}
沒有更多的嵌套調(diào)用,因此函數(shù)完成,返回2。
當(dāng)函數(shù)結(jié)束時(shí)，不再需要它的執(zhí)行上下文，因此它被從內(nèi)存中刪除。前一個(gè)被從棧頂恢復(fù):
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)的執(zhí)行重新開始。它有子調(diào)用pow(2,1)的結(jié)果，所以它也可以完成x * pow(x, n - 1)的求值，返回4。
然后恢復(fù)之前的上下文:
Context:?{?x:?2,?n:?3,?at?line?5?}?call:?pow(2,?3)
當(dāng)它完成時(shí)，我們得到pow(2,3) = 8的結(jié)果。
在這種情況下，遞歸深度是:3。
從上面的例子中可以看出，遞歸深度等于堆棧中上下文的最大數(shù)量。
注意內(nèi)存要求。上下文需要內(nèi)存。在我們的例子中，n的冪實(shí)際上需要n個(gè)上下文的內(nèi)存，對(duì)于所有n的較小值。
基于循環(huán)的算法更節(jié)省內(nèi)存:
function?pow(x,?n)?{
??let?result?=?1;
??for?(let?i?=?0;?i?????result?*=?x;
??}
??return?result;
}