遞歸
????不知道有新手聽沒聽過別人拿剝糖塊來形容遞歸，諸如一層層地剝好比一層層地進入遞歸。這種比喻可是誤導了我，只想著剝了，其實剝完皮兒，取出糖塊，再把皮兒一層層地穿上才算個完整的遞歸。????

??? 遞歸就是自己調用自己的函數或方法了，一般情況，像我這樣的新手剛接觸遞歸的時候，迷就迷在了不明白遞歸的原理上，在 (c#)數據結構與算法分析 --棧與隊列 中說過，編譯器一般用棧來實現遞歸，具體就看那篇文章吧。

??? 這里先舉一個用到遞歸的例子。

??? 求第n項的三角數字，三角數字就是數列中，第n項的值是第n-1項加上n得來的。這里可不是那個斐波那契數列。
??? 1，3，6，10，15，21......... 這些個數就是三角數字。

??? 這個遞歸方法就是計算第n項的三角數字：
?1?//使用遞歸求第n項的三角數
?2?private?int?triangle(int?n)
?3?????????{
?4?????????????if?(n?==?1)?//這是遞歸的基準情形，一個遞歸沒有基準的話，就沒法跳出遞歸。
?5?????????????{
?6?????????????????return?n;
?7?????????????}
?8?????????????else
?9?????????????{
10?????????????????return?(n?+?triangle(n?-?1));?//調用本方法
11?????????????}
12?????????}
很簡單的一個算法，可用 第n個三角數字=(n*n+n)/2 這個公式來驗證其正確性。

仔細看看這個圖就會完全明白遞歸到底怎么遞歸了。

n=5時，開始調用
↓
第1層

n=5

第2層 n=4 第3層 n=3 第4層 n=2 第3層 n=1 返回 1 加 2 返回 3 加 3 返回 6 加 4 返回 10 加 5 返回 15

↓
返回15
（這個表格在firefox下顯示有點問題）

??? 這時，應該把遞歸理順了吧，自己可以試試用遞歸求階乘，然后試著解決漢諾塔問題，google搜一下會有很多漢諾塔問題的源碼。

??? 很明顯，上面那個遞歸是尾遞歸，在某些情況下，比如函數體比較龐大，有很多局部變量，則很容易引起棧溢出。有時候應該消除遞歸。
???
??? 這就用到棧了，下面這個源碼，功能和上面一樣，只不過用棧來消除遞歸了。
?1?//消除遞歸，使用棧代替遞歸
?2?????????private?int?triangleStack(int?n)
?3?????????{
?4?????????????Stack<int>?traingle?=?new?Stack<int>();?//這個棧來模擬遞歸中的環境變量
?5?
?6?????????????while?(n?>=?1)?//相當于遞歸中的基準了
?7?????????????{
?8?????????????????traingle.Push(n);?//將每次遞減的值壓入棧，相當于逐層調用遞歸
?9?????????????????n?=?n?-?1;
10?????????????}
11?
12?????????????while?(traingle.Count?>?0)?//這個相當于逐層跳出遞歸
13?????????????{
14?????????????????n?=?n?+?traingle.Pop();?//計算
15?????????????}
16?
17?????????????return?n;
18?????????}
??? 不是很難吧，主要把遞歸的原理理清，思路自然就明了了。

??? 要注意的是，使用遞歸千萬可別忘了基準情形，不然就永遠遞歸不出來了。遞歸的效率有時候比較低，這樣就可以用棧或循環來代替遞歸了。

總結

以上是生活随笔為你收集整理的(c#)数据结构与算法分析 --递归的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。