经典演算法题每日演练——第三题猴子吃桃

猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾就多吃了一个。第二天早上又将剩下的桃子吃了一半，还是不过瘾又多
吃了一个。以后每天都吃前一天剩下的一半再加一个。到第 10 天刚好剩一个。问猴子第一天摘了多少个桃子？

分析: 这是一套非常经典的演算法题，这个题目体现了演算法思想中的递推思想，递回有两种形式，顺推和逆推，针对递推，只要
我们找到递推公式，问题就迎刃而解了。
令 S10=1，容易看出 S9=2(S10+1)，简化一下
S9=2S10+2
S8=2S9+2
…..
Sn=2Sn+1+2

遥想公瑾当年，老师说递回是最简洁，最容易理解的，好，就用递回试一下：

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 }

当我们玩转递回的时候，老师说线性递回会将 “变数，引数，返回值” 在 “递” 的过程中压栈，如果迟迟 “递” 不到头的话，栈就会越积越多，
最后就爆掉了，window 中系统预设的堆叠空间是 1M 。
那么解决方法是什么？尾递回，下面我们继续上程式码：

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 //将当前的值计算出传递给下一层
19 return SumPeachTail(day + 1, 2 * total + 2);
20 }
21 }

那么两种递回有什么区别呢？上图说话。

从图中我们可以清晰的看到 “线性递回” 和 “尾递回” 的区别，那到底有什么本质区别呢？尾递回中在每次向下递回的过程中，都会将当前
层的结果计算出来后向下一层传递，从理论上说，传到下一层后，上一层的引数值已经没有存在的必要了，可以清除上一层中的变数占
用的栈空间，那么最终达到的效果就是永远不会出现 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) 。文章来自互联网博客网站，原文地址：http://www.cnblogs.com/huangxincheng/archive/2012/08/08/2628022.html

经典演算法题每日演练——第三题 猴子吃桃