遞歸函數的執行

tomato 發布于2019-08-21 11:37 / 2862人閱讀

摘要：遞歸一個函數可以指向并調用自身。這是的一個獨特的用法，在這個結構下無法替代，出錯但我們可以用下面這種方式，把遞歸函數賦值給一個變量

遞歸(Recursion)

一個函數可以指向并調用自身(call itself)。有三種方法可以達到這個目的：

函數名

arguments.callee

作用域下的一個指向該函數的變量名

上述概念引用自MDN，對遞歸概念不清楚的可以自行查看；

遞歸函數的執行

在這里我們討論一下遞歸函數中遞歸后的語句如何執行，先看這樣一個例子：

function rec(x){
if(x!==1){
   console.log(x)
   rec(x-1)
   console.log(x) 
   }   
}
rec(5) //輸出為5 4 3 2 2 3 4 5

以上這段代碼執行的結果就是遞歸前的語句順序執行，遞歸后的語句倒序執行。初看到這段代碼，完全不能理解它執行的順序。通過調試讓代碼逐行執行，可以看到執行的順序，其實就是一層一層執行遞歸，每執行到rec(x-1)時就重新執行該函數，遞歸后的語句會在遞歸執行到最里層后再由內向外輸出。
CSDN上的一篇博客很好的總結了遞歸的特性如下：
１　每一次函數調用都會有一次返回．當程序流執行到某一級遞歸的結尾處時，它會轉移到前一級遞歸緊接著的后面繼續執行．
２　遞歸函數中，位于遞歸調用前的語句和各級被調函數具有相同的順序．如打印語句 #1 位于遞歸調用語句前，它按照遞歸調用的順序被執行了 4 次．
３　每一級的函數調用都有自己的私有變量．
４　遞歸函數中，位于遞歸調用語句后的語句的執行順序和各個被調用函數的順序相反．
５　雖然每一級遞歸有自己的變量，但是函數代碼并不會得到復制．
６　遞歸函數中必須包含可以終止遞歸調用的語句．

在這個例子中，終止遞歸調用的條件是if(x!==1)，如果調用時取值x小于1，會構成死循環；這個例子中的遞歸采用了通過函數名調用的方法。
下面我們再討論一下argumengts.callee方式，在ES5嚴格模式下，callee是無法使用的，原因詳見MDN中arguments.callee。

這是callee的一個獨特的用法，在這個結構下無法替代，

function factorial(num){
    if (num <= 1){
        return 1;
    } else {
        return num * factorial(num-1);
    }
}
var anotherFactorial = factorial;
alert(anotherFactorial(4)); //出錯！

但我們可以用下面這種方式，把遞歸函數賦值給一個變量：

var factorial = (function f(num){
if (num <= 1){
return 1;
} else {
return num * f(num-1);
}
});

GPU云服務器云服務器函數的執行過程遞歸執行遞歸函數printf 遞歸函數python

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/86925.html

翻譯連載 | 第 9 章：遞歸（下）－《JavaScript輕量級函數式編程》 |《你不知道的JS》

摘要：每個函數調用都將開辟出一小塊稱為堆棧幀的內存。當第二個函數開始執行，堆棧幀增加到個。當這個函數調用結束后，它的幀會從堆棧中退出。保持堆棧幀跟蹤函數調用的狀態，并將其分派給下一個遞歸調用迭。原文地址：Functional-Light-JS 原文作者：Kyle Simpson－《You-Dont-Know-JS》作者關于譯者：這是一個流淌著滬江血液的純粹工程：認真，是 HTM...

LeviDing 2019-08-21 16:44 評論0 收藏0
JavaScript專題之遞歸

摘要：專題系列第十八篇，講解遞歸和尾遞歸定義程序調用自身的編程技巧稱為遞歸。然而非尾調用函數，就會創建多個執行上下文壓入執行上下文棧。所以我們只用把階乘函數改造成一個尾遞歸形式，就可以避免創建那么多的執行上下文。 JavaScript 專題系列第十八篇，講解遞歸和尾遞歸定義程序調用自身的編程技巧稱為遞歸(recursion)。階乘以階乘為例： function factorial(n...

asoren 2019-08-22 11:05 評論0 收藏0
最大子序列的求解-分治方法

摘要：下面進行簡單的作圖分析注意到，遞歸函數從外層，沿著計算的路徑，經過三次遞歸調用函數，到達基準，在基準層分別計算遞歸函數內部的三部分左側最大子序列與右側最大子序列的和，并利用求出最大者返回。問題描述問題：給定整數序列，求解其中最大子序列（連續的序列）。思路分析利用分治和遞歸的思想求解，在《數據結構與算法分析（Java語言描述）》Page29，作者給出了具體的java代碼。...

microelec 2019-08-16 14:37 評論0 收藏0
【從蛋殼到滿天飛】JAVA 數據結構解析和算法實現-鏈表與遞歸

摘要：鏈表與遞歸已經從底層完整實現了一個單鏈表這樣的數據結構，并且也依托鏈表這樣的數據結構實現了棧和隊列，在實現隊列的時候對鏈表進行了一些改進。計算這個區間內的所有數字之和。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言【從蛋殼到滿天飛】JAVA 數據結構解析和算法實現，全部文...

lastSeries 2019-08-23 16:19 評論0 收藏0
【從蛋殼到滿天飛】JAVA 數據結構解析和算法實現-鏈表與遞歸

摘要：鏈表與遞歸已經從底層完整實現了一個單鏈表這樣的數據結構，并且也依托鏈表這樣的數據結構實現了棧和隊列，在實現隊列的時候對鏈表進行了一些改進。計算這個區間內的所有數字之和。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言【從蛋殼到滿天飛】JAVA 數據結構解析和算法實現，全部文...

alanoddsoff 2019-08-16 16:04 評論0 收藏0