第三题 猴子吃桃

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

分析: 这是一套非常经典的算法题，这个题目体现了算法思想中的递推思想，递归有两种形式，顺推和逆推，针对递推，只要 

  1.      我们找到递推公式，问题就迎刃而解了。 
  3.             令S<sub>10</sub>=1，容易看出 S9=2(S10+1)， 简化一下  
  5.               S<sub>9</sub>=2S<sub>10</sub>+2 
  7.               S<sub>8</sub>=2S<sub>9</sub>+2 
  9.                   ..... 
  11.               S<sub>n</sub>=2S<sub>n+1</sub>+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.     }

第三题 猴子吃桃 - 图1

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

第三题 猴子吃桃 - 图2

从图中我们可以清晰的看到“线性递归”和“尾递归”的区别，那到底有什么本质区别呢？尾递归中在每次向下递归的过程中，都会将当前

层的结果计算出来后向下一层传递，从理论上说，传到下一层后，上一层的参数值已经没有存在的必要了，可以清除上一层中的变量占

用的栈空间，那么最终达到的效果就是永远不会出现StackOverflowException了，但实际上是否真有这个效果，得要看编译程序是否

真的给你优化了。

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

第三题 猴子吃桃 - 图3

很可惜，有图有真相，抛出异常了，当然我是菜鸟，早已看不懂汇编了，大家也可以讨论讨论，目前我个人认为C#编译器没有给

我做这个优化:-D。

下一步我们就要计算一下这个递归的时间复杂度是多少，关于求“递归”的时间复杂度主要有三种：

  1. 代换法。

  2. 递归树法。

  3. 主定理。

这一篇我就说下代换法，作法如下

①：猜一下递归式复杂度的上界或者下界。

②：用数学归纳法证明你的复杂度是正确的。

为了具有通用性，我们将“猴子吃桃”的问题反过来写，也就是已知S1，求S10，当然原理是一样的，通用公式就有如下形式： 

  1.               T<sub>n</sub>=2T<sub>n-1</sub>+2             ①

假使 Tn=O(n) ②

则必定存在一个 c>0的自然数使 

  1.              Tn&lt;=cO(n)=cn           ③

③代入①知 

  1.              Tn&lt;=2c(n-1)+2=2cn-2c+2 
  3.                                    =cn-c+1 
  5.                                    =cn-(c-1)

当c>=1时，则必有 Tn<=cn

最后得出递归式的时间复杂度为O(N)。