前文我們介紹了方法的基本用法，以及調(diào)用方式。今天我們來說一下，方法遞歸的邏輯，以及用法。

Part 1 引例

前文，我們說到了一種調(diào)用方式，是通過 Main 方法調(diào)用 A 方法、B 方法和 C 方法的模式展開的。那么，方法的調(diào)用是可以串聯(lián)的，比如 Main 方法里調(diào)用 A、A 里調(diào)用 B、B 里調(diào)用 C。

比如這樣一個簡單的例子。A 傳入了一個帶 ref 關(guān)鍵字的 a 變量。這表示數(shù)據(jù)在 A 方法里一旦修改，Main 方法里的 a 也發(fā)生改動。此時 A 方法里只對 a 增大一個單位后，調(diào)用了 B 方法。B 方法此時也是帶 ref 參數(shù)、傳入的 a，因此 Main、A 和 B 三個 a 用的是同一個 a 變量。此時 B 里增大 2 個單位 a，然后調(diào)用 C 方法。C 也是傳入 ref 參數(shù)，因此 A、B、C 還有 Main 用的是是同一個 a。最后，a 增大三個單位在 C 方法里，至此，整個調(diào)用過程結(jié)束。待調(diào)用過程結(jié)束后，自動回退到最開始的調(diào)用方，即 Main 里。a 在期間增大了一共 6 個單位，因此 a 此時會從 30 改成 36，這就是調(diào)用串聯(lián)的模式。

那么，有沒有可能是下面這樣的調(diào)用呢：

是的，你沒有看錯，A 方法里再次調(diào)用 A 自己。這個過程稱為遞歸調(diào)用（Recursively Call）；而這種遞歸調(diào)用的思路，稱為遞歸（Recursion）。

Part 2 基本遞歸

顯然，在前面這種遞歸示例里，我們無法退出調(diào)用過程。因為調(diào)用是“循環(huán)”的，A 里調(diào)用自己，那么 A 再次被得到調(diào)用；再次調(diào)用過程之中，A 又是一次調(diào)用自己，然后又再次得到一次調(diào)用。如此循環(huán)往復(fù)，無法退出來。這種遞歸稱為無窮遞歸或死遞歸（Infinity Recursion）。顯然，這種遞歸必然會導(dǎo)致程序掛掉，因為無窮無盡的調(diào)用只會無窮無盡地消耗內(nèi)存資源。直到程序執(zhí)行到某個時刻的時候，內(nèi)存消耗得差不多了，程序就直接崩潰了。

顯然，遞歸是危險的。但是遞歸有時候可以解決很復(fù)雜，也很有趣的問題。如果我們靠自己的邏輯來執(zhí)行，可能連個思路都想不出來，這個時候遞歸可能會很有幫助。

2-1 示例 1：計算從 1 到 100 的和

這一次，我們使用遞歸的思維來完成這個例子。

遞歸就等于是找一個遞推的思路。比如說通項公式使用遞推的模式來表達，那么自然而然就可以用遞歸來完成了。比如說，從 1 到 100 的話，我們可以倒過來思考：假設(shè)??專門用來表示從 1 到 n?的和，即好比這個公式：

那么，我們找尋的遞推式子可以這么考慮：我們要求的是 1 到 100，因此也就是 。而??不是嗎？這就是我們這里所謂的遞推公式。我們馬上可以將其寫成代碼：

這樣的式子，f 里再次使用了它自己。我們完成了遞歸的一半了。下面繼續(xù)思考下一步。因為遞歸無法自己退出，因此這樣寫代碼是顯然不夠的。它好比死循環(huán)一樣，一旦進來就沒辦法自己出去。于是，我們得設(shè)定一個“界限”。當(dāng)界限一旦觸碰到的時候，就自動退出遞歸過程。那么，界限是哪里呢？還記得遞推公式嗎？這里的遞推公式我們是從 100 開始算的。顯然，數(shù)字到 1 的時候，我們難不成還繼續(xù)算?f(1) = f(0) + 1 嗎？顯然沒有必要了。因此，我們可以考慮自己手動錄入 f(1)?的結(jié)果，這樣的話，由于算到 f(1)?的時候，會自動取出我們手動錄入的結(jié)果，程序就不再遞歸，至此，遞歸調(diào)用就結(jié)束了。那么寫成代碼也很簡單：

我們就是單純加了一句 if (n == 1) return 1; else ... 的框架。這么做確實可以避免遞歸。因為 n == 1 條件成立的時候，此時會直接把 1 作為 F(1) 執(zhí)行的結(jié)果而反饋給調(diào)用方，這樣就沒有再次繼續(xù)調(diào)用 F 方法了。這就避免了繼續(xù)遞歸。

我們試著調(diào)用一下 F 方法。

這樣就可以了。你是不是沒明白遞歸的過程？沒關(guān)系，我們還有別的例子給你參考。

順帶一提，如果兩個用 if-else 連接的部分都帶有 return 語句作為語句的話，那么 else 實際上是可以省略的。

這么寫沒有任何問題。原因很簡單：因為 return 語句會自動退出執(zhí)行，把結(jié)果自動反饋給調(diào)用方，因此后面的代碼不會執(zhí)行了；正是因為如此，我們完全可以省略 else 關(guān)鍵字。

另外，我們把前文里直接將字面量作為 return 語句的返回的那個部分稱為遞歸出口（Exit）。遞歸出口是專門用來阻止繼續(xù)無限制遞歸下去的過程的。

2-2 示例 2：兔子數(shù)列

簡要說明一下兔子數(shù)列。兔子數(shù)列也叫斐波那契數(shù)列。兔子數(shù)列的通項公式很復(fù)雜：

顯然這個數(shù)列完全沒有幫助。不過我們要是寫遞歸模式的話，式子可以這么搞：

那么，我們嘗試為其改成代碼：

下面我們看一下這個程序遞歸模式是不是可以完成計算。首先，將 F(100) 改成 F(99) + F(98)。然后 F(99) 和 F(98) 分別改成 F(98) + F(97) 和 F(97) + F(96)。然后這些數(shù)據(jù)，又被繼續(xù)拆分計算。直到這些數(shù)據(jù)改成 F(1) 和 F(0) 的時候，會自動提出 0 和 1 的結(jié)果作為表達式結(jié)果，以此避免繼續(xù)遞歸。

由于這里用到兩次遞歸部分，一個是 F(n - 1)，而另外一個是 F(n - 2)?？梢詮?n 的取值看出，我們必須設(shè)定兩個用來退出遞歸的 return 語句才行。

Part 3 尾遞歸

尾遞歸（Tail Recursion）是遞歸里的特別情況。我們犧牲一個方法的參數(shù)來存儲每一次遞歸過程里計算出來的結(jié)果。當(dāng)遞歸終止（遞歸出口觸發(fā)）的時候，直接就把這個數(shù)據(jù)提取出來直接作為方法的返回值返回出去的表達方式。

3-1 示例 1：數(shù)組求和

這不是循環(huán)就能搞定嗎？我們故意寫一個遞歸讓你明白遞歸怎么寫。

數(shù)組求和實際上就是把數(shù)組數(shù)據(jù)挨個排開，然后逐個加起來的過程。顯然，如果我們用 f(i)? 表示到下標(biāo)為 i?的時候，前面所有數(shù)據(jù)的和，那么 f(\text{arr.Length})?就是我們要求的結(jié)果了。但是，光有個下標(biāo)傳入還不夠，數(shù)組本身還沒傳入呢，我們肯定得傳入一個數(shù)組進去。所以代碼是這樣的：

這個例子可能難一點。我們借用一個臨時變量 temp 來表示臨時計算的結(jié)果。這個 temp 在調(diào)用方傳入的時候是沒有意義的，你給它規(guī)定為 0，表示從 0 開始計算。

在方法體里，我們先來看結(jié)果表達式 GetSum(arr, currentIndex ?+ 1, temp + arr[currentIndex])。這個表達式可能不是很好理解。三個參數(shù)對應(yīng)了方法本身的這三個參數(shù)。第一個參數(shù)自然是 arr，因為數(shù)組是不論如何都需要用到的；第二個參數(shù)是表示，遞歸的時候算到哪個索引了。在調(diào)用方（Main 方法），我們傳入 0 表示初始從第 1 個元素開始計算。在遞歸的時候，顯然我們遞歸就得計算下一個數(shù)據(jù)，因此索引在這里傳入 currentIndex + 1 以表達下一次遞歸的時候，傳入的參數(shù)是 1，即從第 2 個元素開始計算；第三個參數(shù)是 temp，用來臨時記住遞歸的結(jié)果。初始的時候傳入 0，而每一次運算都需要將前面的結(jié)果數(shù)值累計起來，因此下一次遞歸的 temp 數(shù)值應(yīng)該是 temp + arr[currentIndex]（即原本的 temp 數(shù)值，加上數(shù)組當(dāng)前索引下的數(shù)值）。

按道理來說，單說 currentIndex 變量的話，在遞歸的時候，必然會因為第二個參數(shù)總是傳入原始數(shù)值 + 1 的關(guān)系，這個參數(shù)每次的數(shù)值就會變得越來越大。當(dāng) currentIndex == arr.Length 的時候，我們就可以認為遞歸可以結(jié)束了。因此，我們直接將累計結(jié)果的那個參數(shù) temp 直接返回就可以了。至此，這就是這個題用遞歸寫出來的方法。

那么，看下調(diào)用方的寫法：

這樣就可以了。

3-2 示例 2：求數(shù)組里元素的最大值

如果我們使用遞歸來完成這個操作的話，那么我們必然得找到一個遞推公式。和前面這個例子一樣，由于它和數(shù)學(xué)式子有所不同，因此不是很好表達成遞歸公式的形式。因此得自己想辦法。

我們要用遞歸獲取整個數(shù)組里最大的那個數(shù)，我們肯定最后是拿前面的比較結(jié)果和最后一個數(shù)一起比較的。因此，假設(shè)數(shù)學(xué)函數(shù) f(i)?表示數(shù)組從 0 到 i 索引期間的最大值，那么我們可以這么表示：

其中的數(shù)學(xué)式子? 就等價于 C# 里的條件運算符表達式 a > b ? a : b，即取這兩個數(shù)的較大者。那么，整個功能要寫成方法的話，可以考慮和前面這個例子實現(xiàn)的思路依葫蘆畫瓢：

其中，Math.Max 方法是系統(tǒng)自帶的取兩者較大的那個數(shù)字的方法。這么寫的話，我們就不用寫條件運算符表達式了。

3-3 尾遞歸方法的入口點重載

顯然，第二個參數(shù)和第三個參數(shù)暴露給用戶是沒有必要的，因為我們大家都知道，隨時隨地這兩個參數(shù)都是 0（比如前面兩個例子，都是傳入 0 和 0 分別作為第 2 個和第 3 個參數(shù)）。既然如此，我們就沒有必要讓用戶了解和知道這倆參數(shù)到底拿來干嘛。于是我們可以考慮重載一個沒有這兩個參數(shù)的方法，然后讓這個方法專門調(diào)用遞歸方法。

我們拿前面這個例子舉例說明。

然后，我們在使用遞歸方法的時候，可以直接使用前者即可。

這樣一來，方法重載就會通過調(diào)用下面的方法來達到自動遞歸的效果，而且也體現(xiàn)了包裝的思想。

Part 4 遞歸方法的條件運算符簡寫

很容易看出，前文給的例子全都可以用條件運算符來替換。因為 if (條件) return a; else return b; 的寫法完全可以改成 return 條件 ? a : b;。因此，我們試著改寫一下內(nèi)容：

求從 1 到 n 的和：

兔子數(shù)列：

數(shù)組求和：

數(shù)組求最大值：

當(dāng)然，這樣的寫法我估計不單獨列出來你可能看不太明白，它實際上就是從前面 if-else 代換簡寫過來的寫法，因此應(yīng)當(dāng)是等價的書寫格式。只是使用條件運算符的話，不容易明白而已。

條件運算符里使用條件運算符的話，C# 是知道計算順序的，因此不用使用小括號，因此前面兔子數(shù)列的結(jié)果可以直接去掉小括號這么寫：return n == 0 ? 0 : n == 1 ? 1 : F(n - 1) + F(n - 2);。