基于階乘的遞歸算法內部研究

辜雙佳 栗智

摘?要：直接或間接地調用自身的函數(shù)稱為遞歸函數(shù)。不管數(shù)據(jù)結構本身是否具有遞歸屬性，當用到遞歸技術時，我們可以更加直觀地解釋函數(shù)與算法，讓閱讀者更好地理解算法的內部運行。但其實很多人并不知道調用遞歸函數(shù)時程序的具體執(zhí)行過程，這要歸結于“?！边@種數(shù)據(jù)結構。在該論文中，我們將在“階乘”的基礎上，分析遞歸函數(shù)的具體執(zhí)行過程。本文代碼采用C語言實現(xiàn)。

關鍵詞：遞歸;階乘;C語言

1?緒論

1.1?遞歸的概念

直接或間接地調用自身的算法稱為遞歸算法[1]。用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)[1]。直接調用自己稱為直接遞歸，間接調用自己稱為間接遞歸。在計算機算法設計與分析中，遞歸技術是十分有用的。使用遞歸技術往往使函數(shù)的定義和算法的描述簡捷且易于理解。有些數(shù)據(jù)結構，如二叉樹等，由于其本身固有的遞歸特性的遞歸特性特別適合用遞歸的形式來描述。有些問題，雖然本身沒有遞歸結構，但用遞歸技術可以使設計的算法簡潔易懂且易于分析[1]。

1.2?分治和遞歸的關系

將一個難以直接解決的大問題分割成一些規(guī)模較小的相同問題，以便各個擊破，即分而治之[1]。分治和遞歸就像是一對孿生兄弟，經(jīng)常一起應用于算法設計中，并由此產生了許多的高效算法。我們可以把它理解為：分治策略用遞歸算法實現(xiàn)。

1.3?遞歸適用的場合

遞歸算法的基本思想是：把規(guī)模大的、較難解決的問題變成規(guī)模較小的、易解決的同一問題。規(guī)模較小的問題又變成規(guī)模更小的問題，并且小到一定程度可以直接得出它的解（遞歸出口）[2]。故在解決現(xiàn)實問題中，對于求解一個復雜的或者問題規(guī)模較大的問題，我們在將其劃分為一些簡單的或者規(guī)模較小的問題時，如果滿足：（1）所劃分成的子問題性質與原來的大問題相同。（2）當問題規(guī)模小到一定程度的時候直接有解。對于滿足以上條件的問題我們就可以考慮使用遞歸的方法求解。

1.4?棧（stack）

棧是只允許在一端進行插入或刪除操作的線性表。首先棧是一種線性表，但是限定這種線性表只能在某一端進行插入或刪除操作[3]。形象地理解就是：棧就像一個圓柱形的桶，先放進去的東西被壓在了最底下（棧底），后放進去的東西依次放在了上面（棧頂），不放任何東西（元素）的棧叫作空棧。放入東西的操作由棧頂指針（top）來控制，即每放進去一樣東西則棧頂指針（top）自動加一。初學者請記住一句最關鍵的話就是：先進后出。

1.5?遞歸過程與遞歸工作棧

遞歸過程在實現(xiàn)時，需要自己調用自己。層層向下遞歸，退出時的次序正好相反，主程序第一次調用遞歸過程為外部調用，遞歸過程每次遞歸調用自己為內部調用，它們返回調用它的過程的地址不同。函數(shù)調用針對主調函數(shù)和被調用函數(shù)分別進行三步操作。

√主調函數(shù)：

①開辟空間（工作棧）;

②實參→形參;

③控制權給被調用函數(shù)（即top（棧頂指針）移動）。

工作棧在內存中，工作棧里面會依次存放返回地址（下一條指令）、局部變量、參數(shù)

√被調函數(shù)：

①返回值;

②釋放空間;

③控制權給被調用函數(shù)（即top（棧頂指針）移動）。

每一次遞歸調用時，需要為過程中使用的參數(shù)、局部變量等另外分配存儲空間。每層遞歸調用需分配的空間形成遞歸工作記錄，按后進先出的棧組織。

1.6?總結

本文將結合“階乘”這個經(jīng)典的遞歸算法，用“?！边@種數(shù)據(jù)結構分析數(shù)據(jù)的出棧入棧過程，讓學習遞歸的人真正知道調用遞歸函數(shù)時程序的具體執(zhí)行過程。

2?階乘

2.1?引言

所謂階乘，即遞減數(shù)字的乘積。一個正整數(shù)的階乘（factorial）是所有小于及等于該數(shù)的正整數(shù)的積，并且0的階乘為1。自然數(shù)n的階乘寫作n！。亦即n！=1×2×3×…×n。

從階乘的定義，我們不難找到規(guī)律，所以階乘亦可用遞歸方式定義：0！=1，n！=（n1）！×n。初學者請?zhí)貏e注意一點，那就是遞歸函數(shù)一定由兩部分組成，一個叫作遞歸方程，他是遞歸函數(shù)的入口，是函數(shù)調用自身的地方，這里也就是n！=（n1）！×n，其中n為正整數(shù)。另一個叫邊界條件，他是遞歸函數(shù)的出口，遞歸函數(shù)的出口一般為一個返回值，這里也就是0！=1，每個遞歸函數(shù)都必須有非遞歸定義的初始值（邊界條件），否則遞歸函數(shù)將永遠無限地調用下去導致遞歸函數(shù)無法計算[1]。

2.2?階乘

階乘的數(shù)學表達式為：n！=1×2×3×…×n，階乘的遞歸定義如圖2所示：

邊界條件與遞歸方程是遞歸函數(shù)的二個要素，遞歸函數(shù)只有具備了這兩個要素，才能在有限次計算后得出結果。

2.3?運行結果

通過在vc6.0上面編輯、編譯、連接、運行C語言代碼，得到了以下的運行結果，為了便于后面棧的分析，我們這里選擇輸入一些比較小的數(shù)，比如3和邊界值0，如圖3、如圖4所示：

2.4?結果分析

特別說明，為了后面描述方便，有以下代替：

當輸入3的時候，s=3，然后去執(zhí)行“1”（函數(shù)調用），此時在內存開辟了空間，也就是開辟了一個工作棧，里面放了三樣東西，分別是一會兒的返回地址（即“2”）、局部變量的值（m）、參數(shù)（即s=3）。接著把實參傳給形參，也就是把s的值傳給n，則n=3。最后將控制權給被調函數(shù)，也就是“3”，此時棧頂指針（top）移動。然后來到我們的被調用函數(shù)“3”，此時n=3，執(zhí)行else進入遞歸（即“4”），此時的返回值為“5”，局部變量n=3，然后又執(zhí)行else進入遞歸（即“4”），此時的返回值為“5”。局部變量n=2，然后又執(zhí)行else進入遞歸（即“4”），此時的返回值為“5”。局部變量n=1，然后執(zhí)行if進入邊界條件（出口）（即“6”），此時的返回值為“5”。

到此為止，我們的遞歸函數(shù)終于找到出口了，大家可能也再次深刻地理解了為什么一個遞歸函數(shù)必須有邊界條件，即“每個遞歸函數(shù)都必須有非遞歸定義的初始值（邊界條件），否則遞歸函數(shù)將永遠無限地調用下去導致遞歸函數(shù)無法計算”。

接著才是返回，這也是一個收獲的過程，人們最容易在這個地方感到困惑，感覺腦子里面理不清的退回。因為棧有“先進后出”的特點，所有返回時的次序正好相反，而這個時候，最重要的就是知道每一次遞歸調用時，使用的參數(shù)、局部變量和返回值具體是什么。

基于前面仔細地記錄，我們知道當執(zhí)行到局部變量n=1，得到返回值，進入出口（即“6”），此時的返回值為“5”，即結束被調用函數(shù)，此時整個結果為1，然后返回給調用它的地方，即“4”里面的factorial（n1）的結果為1（此時n=2），然后執(zhí)行“4”，返回n*factorial（n1），即2*1，此時的返回值為“5”，即結束被調用函數(shù)，此時整個結果為2*1，然后返回給調用它的地方，即“4”里面的factorial（n1）的結果為2*1（此時n=3），然后執(zhí)行“4”，返回n*factorial（n1），即3*2*1，此時的返回值為“5”，即到此為止得到最終的遞歸值為3*2*1，即3！=6，即最終返回的遞歸值為6傳給m進而輸出到控制臺。

我們可以看到這是一個非常繞的過程，但是只要將返回地址、局部變量、參數(shù)的值分別壓進棧里面再依次彈出，那么就不會亂。到此遞歸最精華和核心的地方就說完了。當然，后面還有釋放空間和將控制權交回給被調用函數(shù)，到此為止才是一個完整的遞歸函數(shù)調用過程。

3?總結

本節(jié)以一個簡單又經(jīng)典的例子：“階乘”，詳細地講解了遞歸調用的內部原理，我們在初學時深入了解遞歸的內部原理和執(zhí)行過程才可以真正學懂遞歸，也為我們會用遞歸創(chuàng)造了可能。但從文字表述也可以發(fā)現(xiàn)這個過程很繞，有很多重復的工作，但那是計算機關心的過程，我們在進行程序設計的時候只需要掌握這種思想就可以了。在理解了“階乘”的基礎上，大家可以進一步用畫工作棧中存放的返回地址（下一條指令）、局部變量、參數(shù)來驗證“Fibonacci數(shù)列”“全排列”“Hanoi塔”“快速排序”“二分查找”等經(jīng)典的遞歸算法。

參考文獻：

[1]王曉東.計算機算法設計與分析（第五版）.電子工業(yè)出版社，2013：11.

[2]Thomas?H.Cormen?Charles?E.Leiserson，Ronald?L.Rivest?Clifford?Stein.Introduction?to?Algorithms?3nd.2013：52.

[3]王道論壇組編.數(shù)據(jù)結構聯(lián)考復習指南（第一版）.電子工業(yè)出版社，2016：4.