1.15 猴子吃了多少桃子

难度系数：★★★☆☆

被考查系数：★★★☆☆

题目描述：

猴子第一天摘了若干个桃子，当即吃了一半，它还不解馋，于是又多吃了一个；第二天，它吃了剩下桃子的一半，还不过瘾，又多吃了一个；以后每天都吃前一天剩下的一半多一个，到第10天想再吃时，只剩下一个桃子了。问第一天共摘了多少个桃子？

分析与解答：

本题可以采用逆向思维，从后往前推断，发现其中有相同的地方，即出现递推公式，可以采用递归方法。令S10=1，可以得出S9=2×（S10+1），简化罗列关系为：

S9=2×S10+2

S8=2×S9+2

…

Sn=2×Sn+2

实现代码如下：

程序的运行结果为