循環、迭代與遞歸

方悅

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

關鍵詞：循環;迭代;遞歸;階乘;斐波那契數列

中圖分類號：TP311 文獻標識碼：A

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

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

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

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

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

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

遞歸算法實質就是一個函數不斷調用自身的過程，在調用過程中不斷地將局部變量、函數參數和返回地址壓人棧區，當返回時再將棧恢復到每一次調用前的狀態，每一層調用過程棧幀中存放的返回地址都是相同的（013813F9）。在整個的返回階段，始終以EAX寄存器作為橋梁，反復和棧交換數據，不斷地將中間結果保存在返回值中，從而實現參數的傳遞和結果的返回。

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

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

遞歸和循環是兩種不同的解決問題的思路。單從算法設計上講，遞歸和循環并無優劣之分。然而，在編程開發中，由于函數調用的開銷，遞歸常常會帶來性能問題，特別是在求解規模不確定的情況下;而循環因為沒有函數調用開銷，所以效率會比遞歸高。我們以計算Fibonacci（斐波那契）函數為例來說明。

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

從空間的角度來看，循環使用的是堆空間，而遞歸使用的是棧空間。循環占用的內存是一次性的，也就是O（1）的空間復雜度，而對于遞歸（不考慮尾遞歸優化的情況），每次函數調用都要壓棧，那么空間復雜度是O（n），和遞歸次數呈線性關系。

綜上所述，循環、迭代與遞歸、遞推這幾個概念既有聯系，又有區別。它們是人們解決復雜問題的思想方法，無論是在閱讀還是在表達時，不管是在學習還是在工作中，都應做到準確理解和正確使用。