(c#)數(shù)據(jù)結(jié)構(gòu)與算法分析 --遞歸
遞歸
不知道有新手聽沒聽過別人拿剝糖塊來形容遞歸，諸如一層層地剝好比一層層地進入遞歸。這種比喻可是誤導了我，只想著剝了，其實剝完皮兒，取出糖塊，再把皮兒一層層地穿上才算個完整的遞歸。
遞歸就是自己調(diào)用自己的函數(shù)或方法了，一般情況，像我這樣的新手剛接觸遞歸的時候，迷就迷在了不明白遞歸的原理上，在 (c#)數(shù)據(jù)結(jié)構(gòu)與算法分析 --棧與隊列 中說過，編譯器一般用棧來實現(xiàn)遞歸，具體就看那篇文章吧。
這里先舉一個用到遞歸的例子。
求第n項的三角數(shù)字，三角數(shù)字就是數(shù)列中，第n項的值是第n-1項加上n得來的。這里可不是那個斐波那契數(shù)列。
1，3，6，10，15，21......... 這些個數(shù)就是三角數(shù)字。
這個遞歸方法就是計算第n項的三角數(shù)字：
很簡單的一個算法，可用 第n個三角數(shù)字=(n*n+n)/2 這個公式來驗證其正確性。
仔細看看這個圖就會完全明白遞歸到底怎么遞歸了。
n=5時，開始調(diào)用
↓
第1層
↓
返回15
（這個表格在firefox下顯示有點問題）
這時，應該把遞歸理順了吧，自己可以試試用遞歸求階乘，然后試著解決漢諾塔問題，google搜一下會有很多漢諾塔問題的源碼。
很明顯，上面那個遞歸是尾遞歸，在某些情況下，比如函數(shù)體比較龐大，有很多局部變量，則很容易引起棧溢出。有時候應該消除遞歸。
這就用到棧了，下面這個源碼，功能和上面一樣，只不過用棧來消除遞歸了。
不是很難吧，主要把遞歸的原理理清，思路自然就明了了。
要注意的是，使用遞歸千萬可別忘了基準情形，不然就永遠遞歸不出來了。遞歸的效率有時候比較低，這樣就可以用棧或循環(huán)來代替遞歸了。
不知道有新手聽沒聽過別人拿剝糖塊來形容遞歸，諸如一層層地剝好比一層層地進入遞歸。這種比喻可是誤導了我，只想著剝了，其實剝完皮兒，取出糖塊，再把皮兒一層層地穿上才算個完整的遞歸。
遞歸就是自己調(diào)用自己的函數(shù)或方法了，一般情況，像我這樣的新手剛接觸遞歸的時候，迷就迷在了不明白遞歸的原理上，在 (c#)數(shù)據(jù)結(jié)構(gòu)與算法分析 --棧與隊列 中說過，編譯器一般用棧來實現(xiàn)遞歸，具體就看那篇文章吧。
這里先舉一個用到遞歸的例子。
求第n項的三角數(shù)字，三角數(shù)字就是數(shù)列中，第n項的值是第n-1項加上n得來的。這里可不是那個斐波那契數(shù)列。
1，3，6，10，15，21......... 這些個數(shù)就是三角數(shù)字。
這個遞歸方法就是計算第n項的三角數(shù)字：
1 //使用遞歸求第n項的三角數(shù)
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)); //調(diào)用本方法
11 }
12 }
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)); //調(diào)用本方法
11 }
12 }
很簡單的一個算法，可用 第n個三角數(shù)字=(n*n+n)/2 這個公式來驗證其正確性。
仔細看看這個圖就會完全明白遞歸到底怎么遞歸了。
↓
第1層
|
n=5 |
||||||||
|
第2層
返回 15 |
返回15
（這個表格在firefox下顯示有點問題）
這時，應該把遞歸理順了吧，自己可以試試用遞歸求階乘，然后試著解決漢諾塔問題，google搜一下會有很多漢諾塔問題的源碼。
很明顯，上面那個遞歸是尾遞歸，在某些情況下，比如函數(shù)體比較龐大，有很多局部變量，則很容易引起棧溢出。有時候應該消除遞歸。
這就用到棧了，下面這個源碼，功能和上面一樣，只不過用棧來消除遞歸了。
1 //消除遞歸，使用棧代替遞歸
2 private int triangleStack(int n)
3 {
4 Stack<int> traingle = new Stack<int>(); //這個棧來模擬遞歸中的環(huán)境變量
5
6 while (n >= 1) //相當于遞歸中的基準了
7 {
8 traingle.Push(n); //將每次遞減的值壓入棧，相當于逐層調(diào)用遞歸
9 n = n - 1;
10 }
11
12 while (traingle.Count > 0) //這個相當于逐層跳出遞歸
13 {
14 n = n + traingle.Pop(); //計算
15 }
16
17 return n;
18 }
2 private int triangleStack(int n)
3 {
4 Stack<int> traingle = new Stack<int>(); //這個棧來模擬遞歸中的環(huán)境變量
5
6 while (n >= 1) //相當于遞歸中的基準了
7 {
8 traingle.Push(n); //將每次遞減的值壓入棧，相當于逐層調(diào)用遞歸
9 n = n - 1;
10 }
11
12 while (traingle.Count > 0) //這個相當于逐層跳出遞歸
13 {
14 n = n + traingle.Pop(); //計算
15 }
16
17 return n;
18 }
不是很難吧，主要把遞歸的原理理清，思路自然就明了了。
要注意的是，使用遞歸千萬可別忘了基準情形，不然就永遠遞歸不出來了。遞歸的效率有時候比較低，這樣就可以用棧或循環(huán)來代替遞歸了。
浙公網(wǎng)安備 33010602011771號