循環(huán)、迭代與遞歸

方悅

摘要：該文對比了循環(huán)、迭代與遞歸在概念、用法和性質(zhì)上的異同，以階乘和Fibonacci數(shù)列為例在c語言和匯編語言環(huán)境中進(jìn)行說明。

關(guān)鍵詞：循環(huán);迭代;遞歸;階乘;斐波那契數(shù)列

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A

文章編號：1009-3044（2020）06-0055-03

任何復(fù)雜的事物都是由簡單的東西發(fā)展演變而來的，讓我們來從頭說起。這里最初始的概念是重復(fù)/反復(fù)（repeat），意思是一遍又一遍（again and again），是相對于“只做一遍”而言的。從強(qiáng)調(diào)“行為次數(shù)”到以“執(zhí)行路徑”為關(guān)注點(diǎn)，我們引入了循環(huán)。循環(huán)（100p）的概念源自對環(huán)（cycle）這種物理形狀的邏輯抽象，用于形容運(yùn)行過程的周而復(fù)始。在計(jì)算機(jī)程序設(shè)計(jì)中，“循環(huán)”這一術(shù)語指的是一種專門的控制結(jié)構(gòu)。特征是重復(fù)執(zhí)行循環(huán)體中的語句，比一般情況下的順序執(zhí)行復(fù)雜一些，需要跳轉(zhuǎn)命令和條件判斷組合實(shí)現(xiàn)。循環(huán)側(cè)重于解決問題的過程，至于方法，主要有迭代和遞歸兩種。根據(jù)《簡明數(shù)學(xué)詞典》的定義，迭代（Iteration）指的是重復(fù)執(zhí)行一系列的運(yùn)算步驟，直到求得最終結(jié)果，特點(diǎn)是每一次迭代得到的結(jié)果都作為下一次迭代的初始值。在計(jì)算機(jī)領(lǐng)域，上述“一系列的運(yùn)算步驟”如果用“子程序”這個(gè)詞來代替就容易理解了。在此，迭代是用重復(fù)更替的方法，實(shí)現(xiàn)了更新變量數(shù)值的目的。有別于直接法（或者稱為一次解法），即一次性解決問題。講完了迭代，再來看遞歸。不過在談遞歸之前，引入另外一個(gè)詞：遞推。遞推與遞歸，一字之差，卻有不同，我們先看區(qū)別。從字面來簡單理解，遞推就是“以此類推”的意思。根據(jù)《中國中學(xué)教學(xué)百科全書·數(shù)學(xué)卷》定義，遞推是將復(fù)雜運(yùn)算化簡為若干步重復(fù)的簡單運(yùn)算。聽起來有一些抽象。其實(shí)遞推本是一個(gè)數(shù)學(xué)概念，源于數(shù)列。我們知道，如果數(shù)列{an}的第n項(xiàng)依靠其前一項(xiàng)或幾項(xiàng)確定，這種關(guān)系就叫遞推。例如：經(jīng)典的等差數(shù)列an=an-1+d、等比數(shù)列an=aa-1q、斐波那契數(shù)列（Fibonacci Sequence）an=an-1+an-2（n>=3，a1=1，a2=1），等。在計(jì)算機(jī)科學(xué)中，這種由初值求終值的遞推式理所當(dāng)然用迭代法來實(shí)現(xiàn)。

那么什么是遞歸呢？維基百科（Wikipedia）給出了這樣的詮釋：Recursion is the process of repeating items in a self-similarway.意思是說遞歸f或遞推）就是用自相似的方法進(jìn)行重復(fù)。何為“自相似”？根據(jù)《數(shù)學(xué)辭?！さ谖寰怼范x，當(dāng)該集的任一個(gè)局部放大適當(dāng)倍數(shù)后，它的形狀將會和其原來的整體相一致。如何做到這一點(diǎn)呢？在數(shù)學(xué)與計(jì)算機(jī)科學(xué)中，遞歸通過在函數(shù)（子程序）的定義中使用函數(shù)（子程序）自身這種方法實(shí)現(xiàn)。后面的例子中我們將會看到，遞歸的求解包含“遞推”和“回歸”兩個(gè)過程。有趣的是，我們發(fā)現(xiàn)遞推和遞歸的英文都是Recursion，二者是不做區(qū)分的，都是指用相同的方法進(jìn)行自我更替。舉個(gè)大家熟悉的例子：從前有座山，山里有座廟，廟里有個(gè)和尚講故事，講的什么呢？從前有座山，山里有座廟，廟里有個(gè)和尚講故事，講的什么呢？從前有座山，山里有座廟，廟里有個(gè)和尚講故事，講的什么呢？……根據(jù)定義，這是典型的遞歸，同時(shí)也是一種遞推，在此過程中用到了迭代。在中文的語境，遞推暗含方向朝前（forward），而遞歸描述的是方向往回（back）。遞歸和遞推的共同點(diǎn)在于“遞”，強(qiáng)調(diào)使用相同算法更新迭代，所以二者在英文中是用分形來定義的。事實(shí)上，從嚴(yán)格的意義上講，遞歸除了有一般的自遞歸，還包括互遞歸?；ミf歸，是通過調(diào)用其他函數(shù)間接地調(diào)用自身的過程。此外，在C語言中，還有一個(gè)嵌套函數(shù)的概念。所謂嵌套函數(shù)，指的是在某些情況下，可能需要將某函數(shù)作為另一函數(shù)的參數(shù)使用，這一函數(shù)就是嵌套函數(shù)。在一個(gè)函數(shù)被調(diào)用的過程中又調(diào)用另一個(gè)函數(shù)，這就是函數(shù)的嵌套調(diào)用。特別的，如果是函數(shù)本身嵌套調(diào)用函數(shù)本身，那就是函數(shù)遞歸調(diào)用了。遞歸調(diào)用是嵌套調(diào)用的特殊情形，遞歸調(diào)用的本質(zhì)就是對同一個(gè)子程序（函數(shù)）的嵌套調(diào)用。接下來我們以c語言和匯編語言條件下求階乘n！為例。

可以很清楚地看到，C語言中的循環(huán)在匯編環(huán)境下是用簡單的：比較指令cmp+跳轉(zhuǎn)指令（如jmp）的組合來實(shí)現(xiàn)的，這與我們下面談到的遞歸方法有所不同。

這里略微復(fù)雜一些，C語言中的遞歸調(diào)用factorial（n-1）是用call指令完成的。我們知道，call調(diào)用一個(gè)子程序的步驟是push+jump，即在堆棧中先用eax保存參數(shù)n-1，再跳轉(zhuǎn)到函數(shù)入口f013813C0）循環(huán)調(diào)用.factorial。此過程與迭代的相同之處是都含有計(jì)數(shù)器和參數(shù)的變化、并且都有出口條件保iiEN環(huán)次數(shù)有限，不同的地方是：迭代過程更新的是所求未知量，循環(huán)結(jié)束就能求得目標(biāo)結(jié)果;遞歸過程由兩部分組成，其分界線是到達(dá)函數(shù)出口（01381403）。前半部分壓棧操作（call）完成的只是參數(shù)的準(zhǔn)備工作（1、2、3、……、n），后半部分彈棧操作（retn）完成的才是實(shí)際計(jì)算（resuh=lx2x3x……×n）。從形式上可以看出，迭代一般只是“0型”的循環(huán)結(jié)構(gòu)，而遞歸則是“8型”的循環(huán)結(jié)構(gòu)，換句話說是由兩個(gè)循環(huán)連接組成的，見圖1：子程序的調(diào)用過程。

我們發(fā)現(xiàn)，遞歸主要分為兩步，第一步是從目標(biāo)出發(fā)回溯到源頭，稱為回歸。第二步是從源頭出發(fā)逐步回代達(dá)到目標(biāo)，稱為遞推。這就必須保存子程序的變量、參數(shù)與返回地址，使程序能夠返回到調(diào)用處繼續(xù)執(zhí)行。這一步是通過棧來實(shí)現(xiàn)的，做法是將函數(shù)的返回地址（也稱為“斷點(diǎn)”）即該函數(shù)下一條待執(zhí)行指令的地址壓棧。反復(fù)call（調(diào)用）子程序相當(dāng)于是“回歸”過程，多次執(zhí)行ret（返回）指令就相當(dāng)于“遞堆”過程。每一個(gè)call都會有一個(gè)ret與之對應(yīng)，并且是某一級遞歸返回到調(diào)用它的那一級，而不是直接返回到main（）函數(shù)中的初始調(diào)用部分。雖然每一級遞歸都有自己的變量和參數(shù)，但是函數(shù)代碼并不會復(fù)制，變化的主要是棧區(qū)的數(shù)據(jù)，下面我們用圖示來進(jìn)一步觀察和分析。

遞歸算法實(shí)質(zhì)就是一個(gè)函數(shù)不斷調(diào)用自身的過程，在調(diào)用過程中不斷地將局部變量、函數(shù)參數(shù)和返回地址壓人棧區(qū)，當(dāng)返回時(shí)再將棧恢復(fù)到每一次調(diào)用前的狀態(tài)，每一層調(diào)用過程棧幀中存放的返回地址都是相同的（013813F9）。在整個(gè)的返回階段，始終以EAX寄存器作為橋梁，反復(fù)和棧交換數(shù)據(jù)，不斷地將中間結(jié)果保存在返回值中，從而實(shí)現(xiàn)參數(shù)的傳遞和結(jié)果的返回。

由此可見，遞歸確實(shí)是一種奇妙的思維方式。其優(yōu)點(diǎn)是很顯然的：容易理解，容易編程。不過，PeterDeutsch（彼得·道奇）曾說：To Iterate is Human，to Recurse，Divine.（用迭代的是人，用遞歸的，是神。）他想表達(dá)的意思是：遞歸雖好，能夠用對卻不容易。當(dāng)我們面對一個(gè)復(fù)雜問題的時(shí)候，應(yīng)當(dāng)想想能否將其轉(zhuǎn)化為較為簡單的同類問題呢？可以的話，就先轉(zhuǎn)換為簡單的同類問題來解決，然后再利用簡單的同類問題解法來解決復(fù)雜的同類問題，這就是遞歸思維方式的精髓所在。

遞歸的使用是有條件的。只有當(dāng)算法存在預(yù)期的收斂效果時(shí)，采用遞歸算法才是可行的，否則，就不能使用遞歸算法。從數(shù)學(xué)角度講，有這幾種表達(dá)方式：函數(shù)具備收斂性=有確定的（或有限的）極限=極限是（確定的點(diǎn)或有限的數(shù)），對于計(jì)算機(jī)來說也一樣，要求約束條件必須收斂。簡而言之，循環(huán)次數(shù)是有限的，即有一個(gè)明確的邊界條件或臨界點(diǎn)，作為遞歸出口。為做到這一點(diǎn)，遞歸函數(shù)中必須包含終止遞歸的語句。通常遞歸函數(shù)會使用一個(gè)if條件語句或其他類似語句以便當(dāng)函數(shù)參數(shù)達(dá)到某個(gè)特定值（如上例的n=1）時(shí)結(jié)束遞歸調(diào)用。

遞歸和循環(huán)是兩種不同的解決問題的思路。單從算法設(shè)計(jì)上講，遞歸和循環(huán)并無優(yōu)劣之分。然而，在編程開發(fā)中，由于函數(shù)調(diào)用的開銷，遞歸常常會帶來性能問題，特別是在求解規(guī)模不確定的情況下;而循環(huán)因?yàn)闆]有函數(shù)調(diào)用開銷，所以效率會比遞歸高。我們以計(jì)算Fibonacci（斐波那契）函數(shù)為例來說明。

對于應(yīng)用程序而言，時(shí)間開銷和空間開銷是兩個(gè)重要的考察項(xiàng)目。從時(shí)間的角度來看，遞歸存在計(jì)算速度慢、執(zhí)行時(shí)間長的弊端，時(shí)間復(fù)雜度0（2ⁿ）呈現(xiàn)指數(shù)級的增長，相比于循環(huán)的線性變化0（n）要高得多，原因在于不必要的重復(fù)計(jì)算。下圖是n=5時(shí)的遞歸樹（recursion tree），可以看出虛線框中Fibonacci（2）的計(jì)算用到了三次，同樣的Fibonacci（3）的計(jì)算用到了兩次，顯然我們進(jìn)行了不少的重復(fù)運(yùn)算。不得不考慮到，當(dāng)n越大時(shí)，情況越嚴(yán)重。

從空間的角度來看，循環(huán)使用的是堆空間，而遞歸使用的是?？臻g。循環(huán)占用的內(nèi)存是一次性的，也就是O（1）的空間復(fù)雜度，而對于遞歸（不考慮尾遞歸優(yōu)化的情況），每次函數(shù)調(diào)用都要壓棧，那么空間復(fù)雜度是O（n），和遞歸次數(shù)呈線性關(guān)系。

綜上所述，循環(huán)、迭代與遞歸、遞推這幾個(gè)概念既有聯(lián)系，又有區(qū)別。它們是人們解決復(fù)雜問題的思想方法，無論是在閱讀還是在表達(dá)時(shí)，不管是在學(xué)習(xí)還是在工作中，都應(yīng)做到準(zhǔn)確理解和正確使用。