猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了一个。第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第10 天早上想再吃时，见只剩下一个桃子了。求第一天共摘了多少？
考虑倒推，有迭代表达式：
peaches = (peaches+1)*2; // 前一天的桃子数与当天桃子数的关系
//除2减1和加1乘2是顺向思考和逆向思考的关系，也就是表达式的一个变换
//int count = peachCount(10);
int peachCount(int days)
{
int peaches = 1; // 最后一天桃子数
while(days>1)
{
peaches = (peaches+1)*2;
days--;
}
return peaches;
}考虑递归，有递归表达式：
peachcount(n) =
peachcount(1) = 1 // 最后一天（倒数第1天）
(peachCount(--n)+1)*2 // n>1
code:
// peachCountRecursive(10); // 1534
int peachCountRecursive(int day)
{
if(day == 1) // 最后一天
return 1;
else
return (peachCountRecursive(--day)+1)*2;
}对于递归来说，三个概念很重要：
1 子问题的解与规模为n的整体问题的解有相同的表达式（子问题与原问题之间是纵向的， 同类的关系），当规模为n(1)时，有直接解，这就是递归结束条件，也称为递归出口。
2 递归函数的两个阶段（以递归函数内自己调用的语句为基准）：递归前进段和递归返回段。前进段形成函数的n次调用（call到基准点），返回段形成形成函数的n次return（基准点到ret，如果是尾递归，直接return）。算法的递推思想可以区分为顺推和逆推两种，与递归思想的两个阶段形成对照关系。
3 递归函数的递推展开和回退收缩，是由编译器隐式维护的一个栈的数据结构来实现的。在递推展开阶段，n次调用形成了n个栈栈帧，在回退收缩阶段，n个栈帧逐个返回（移动EBP和ESP寄存器指针来实现）。栈帧上的数据一方面是函数回退到调用点的需要（记录回退地址），另一方面也是回退阶段使用递归函数参数和局部变量历史值的需要。如果用循环改写非尾递归，需要手工维护一个栈数据结构来记录历史值。
-End-