吃了一個(gè)。以后每天都吃前一天剩下的一半再加一個(gè)。到第10天剛好剩一個(gè)。問猴子第一天摘了多少個(gè)桃子？

分析: 這是一套非常經(jīng)典的算法題，這個(gè)題目體現(xiàn)了算法思想中的遞推思想，遞歸有兩種形式，順推和逆推，針對(duì)遞推，只要

我們找到遞推公式，問題就迎刃而解了。

令S₁₀=1，容易看出 S9=2(S10+1)， 簡(jiǎn)化一下

S₉=2S₁₀+2

S₈=2S₉+2

.....

S_n=2S_n+1+2

遙想公瑾當(dāng)年，老師說遞歸是最簡(jiǎn)潔，最容易理解的，好，就用遞歸試一下：

 1     class Program
 2     {
 3         static void Main(string[] args)
 4         {
 5             int sum = SumPeach(1);
 6 
 7             Console.WriteLine("第一天摘得桃子有:{0}", sum);
 8 
 9             Console.Read();
10         }
11 
12         //遞歸
13         static int SumPeach(int day)
14         {
15             if (day == 10)
16                 return 1;
17 
18             return 2 * SumPeach(day + 1) + 2;
19         }
20     }

當(dāng)我們玩轉(zhuǎn)遞歸的時(shí)候，老師說線性遞歸會(huì)將“變量，參數(shù)，返回值”在“遞”的過程中壓棧，如果遲遲“遞”不到頭的話，棧就會(huì)越積越多，

最后就爆掉了，window中系統(tǒng)默認(rèn)的堆棧空間是1M。

那么解決方法是什么？ 尾遞歸，下面我們繼續(xù)上代碼：

 1     class Program
 2     {
 3         static void Main(string[] args)
 4         {
 5             int sum = SumPeachTail(1, 1);
 6 
 7             Console.WriteLine("第一天摘得桃子有:{0}", sum);
 8 
 9             Console.Read();
10         }
11 
12         //尾遞歸
13         static int SumPeachTail(int day, int total)
14         {
15             if (day == 10)
16                 return total;
17 
18             //將當(dāng)前的值計(jì)算出傳遞給下一層
19             return SumPeachTail(day + 1, 2 * total + 2);
20         }
21     }

那么兩種遞歸有什么區(qū)別呢？上圖說話。

從圖中我們可以清晰的看到“線性遞歸”和“尾遞歸”的區(qū)別，那到底有什么本質(zhì)區(qū)別呢？尾遞歸中在每次向下遞歸的過程中，都會(huì)將當(dāng)前

層的結(jié)果計(jì)算出來后向下一層傳遞，從理論上說，傳到下一層后，上一層的參數(shù)值已經(jīng)沒有存在的必要了，可以清除上一層中的變量占

用的棧空間，那么最終達(dá)到的效果就是永遠(yuǎn)不會(huì)出現(xiàn)StackOverflowException了，但實(shí)際上是否真有這個(gè)效果，得要看編譯程序是否

真的給你優(yōu)化了。

下面我們將day=10改成day=int.MaxValue，跑一下程序看看：

很可惜，有圖有真相，拋出異常了，當(dāng)然我是菜鳥，早已看不懂匯編了，大家也可以討論討論，目前我個(gè)人認(rèn)為C#編譯器沒有給

我做這個(gè)優(yōu)化:-D。

下一步我們就要計(jì)算一下這個(gè)遞歸的時(shí)間復(fù)雜度是多少，關(guān)于求“遞歸”的時(shí)間復(fù)雜度主要有三種：

1. 代換法。

2. 遞歸樹法。

3. 主定理。

這一篇我就說下代換法，作法如下

①：猜一下遞歸式復(fù)雜度的上界或者下界。

②：用數(shù)學(xué)歸納法證明你的復(fù)雜度是正確的。

為了具有通用性，我們將“猴子吃桃”的問題反過來寫，也就是已知S1，求S10，當(dāng)然原理是一樣的，通用公式就有如下形式：

T_n=2T_n-1+2 ①

假使 Tn=O(n) ②

則必定存在一個(gè) c>0的自然數(shù)使

Tn<=cO(n)=cn ③

③代入①知

Tn<=2c(n-1)+2=2cn-2c+2

=cn-c+1

=cn-(c-1)

當(dāng)c>=1時(shí)，則必有 Tn<=cn

最后得出遞歸式的時(shí)間復(fù)雜度為O(N)。