不少混java的亲们都曾经遇到过这样一道面试题：有一只猴子，它有一树桃子。猴子每天吃掉树上桃子数量的一半，不过瘾，又多吃一个。到了第十天，树上只剩下一个桃子。问：最开始树上有多少桃子？(要求采用递归的思想解决)。

拿到这类问题，我们该怎样思考呢？

昨天我们一起研究了斐波那契数列，我们已经有了一些概念。在昨天的问题中，我们先是找到了一个公式用来表达每天出生的兔子的数量，这个公式不断的拆解自身，直到拆解到第三天，从而达到了递归的跳出条件，结束了循环调用，得到结果。

同理，我们今天的问题还是采用一样的思路，所谓一招鲜，吃遍天。闲言少叙，先上代码：

大家可以看到，我在代码中已经写明了解题步骤：

找到一个函数，这个函数能够表达数列中任意两个连续数的关系

找到递归调用过程中，函数跳出递归的条件

第一条：找到一个表达数列中任意两个连续数的关系的函数，也就是公式。我们以前读书的时候，经常有做这样的练习，相信这一点难不倒大家。假设第一天树上的桃子为“x”个。猴子吃了一般，就是x/2。然后又多吃一个，所以第二天开始时，树上桃子的个数等于第一天猴子吃完以后，桃子剩下的个数，等于x/2-1。定义第y天猴子没吃之前，桃子的个数f(y)，那么y+1天时，猴子没吃之前，桃子个数为f(y+1)。由此我们得到：

f(y)=x;

f(y+1)=x/2-1;

假定y=1(第一天),则f(y)=f(1)=x个桃子，回到问题：要得到第一天桃子个数，我们只需要求出x得值即可！

那么由“f(y+1)=x/2-1”可以得到“f(y)=x=(f(y+1)+1)*2”。

这个公式已经出来了。第一步的工作已完成。(第一步找公式只是个数学题。)

接下来，我们来进行第二步：找出递归跳出条件。

读题可知，第十天，树上桃子还剩一个，y代表天数，即第十天时：y=10。所以第十天的f(y)=f(10)=1;那么递归地跳出条件就是f(10)。【通过公式f(y)=(f(y+1)+1)*2依次转化f(1)到f(2)、f(3)……】

到这里，相信大家都明白了，代码中的m(int i)就是我们的函数f(y)。方法m中只需要传入天数就能得到该天的桃子个数。

private int m(int i) {

if (i==10) {

return 1;

} else {

int i1 = (m(i + 1) + 1) * 2;

return i1;

代码解读：方法m中传入天数i，方法体中判断如果i==10，返回第十天桃子个数1。否则：执行公式 (m(i + 1) + 1) * 2来计算第i天的桃子个数。(见上面推导的公式：f(y)=x=(f(y+1)+1)*2)。这样，在m(i)执行时，只要i不等于10，就会执行该公式，从而执行m(i+1)。这里就执行了方法的递归调用。每一次执行m(i+1),m中的入参都会加一，知道m(10)时，返回1。此时方法不再自己调用自己了。从而得到一个明确的结果。

#程序员#