猴子第一天摘下若幹個桃子，當即吃了一半，還不過瘾就多吃了一個。第二天早上又将剩下的桃子吃了一半，還是不過瘾又多
吃了一個。以後每天都吃前一天剩下的一半再加一個。到第10天剛好剩一個。問猴子第一天摘了多少個桃子？
分析: 這是一套非常經典的算法題，這個題目展現了算法思想中的遞推思想，遞歸有兩種形式，順推和逆推，針對遞推，隻要
我們找到遞推公式，問題就迎刃而解了。
令s10=1，容易看出 s9=2(s10+1)， 簡化一下
s9=2s10+2
s8=2s9+2
.....
sn=2sn+1+2
遙想公瑾當年，老師說遞歸是最簡潔，最容易了解的，好，就用遞歸試一下：
當我們玩轉遞歸的時候，老師說線性遞歸會将“變量，參數，傳回值”在“遞”的過程中壓棧，如果遲遲“遞”不到頭的話，棧就會越積越多，
最後就爆掉了，window中系統預設的堆棧空間是1m。
那麼解決方法是什麼？ 尾遞歸，下面我們繼續上代碼：
那麼兩種遞歸有什麼差別呢？上圖說話。
從圖中我們可以清晰的看到“線性遞歸”和“尾遞歸”的差別，那到底有什麼本質差別呢？尾遞歸中在每次向下遞歸的過程中，都會将目前
層的結果計算出來後向下一層傳遞，從理論上說，傳到下一層後，上一層的參數值已經沒有存在的必要了，可以清除上一層中的變量占
用的棧空間，那麼最終達到的效果就是永遠不會出現stackoverflowexception了，但實際上是否真有這個效果，得要看編譯程式是否
真的給你優化了。
下面我們将day=10改成day=int.maxvalue，跑一下程式看看：
很可惜，有圖有真相，抛出異常了，當然我是菜鳥，早已看不懂彙編了，大家也可以讨論讨論，目前我個人認為c#編譯器沒有給
我做這個優化:-d。
下一步我們就要計算一下這個遞歸的時間複雜度是多少，關于求“遞歸”的時間複雜度主要有三種：
1. 代換法。
2. 遞歸樹法。
3. 主定理。
這一篇我就說下代換法，作法如下
①：猜一下遞歸式複雜度的上界或者下界。
②：用數學歸納法證明你的複雜度是正确的。
為了具有通用性，我們将“猴子吃桃”的問題反過來寫，也就是已知s1，求s10，當然原理是一樣的，通用公式就有如下形式：
tn=2tn-1+2 ①
假使 tn=o(n) ②
則必定存在一個 c>0的自然數使
tn<=co(n)=cn ③
③代入①知
tn<=2c(n-1)+2=2cn-2c+2
=cn-c+1
=cn-(c-1)
當c>=1時，則必有 tn<=cn
最後得出遞歸式的時間複雜度為o(n)。