def peaches(day=1, last_day=10):
    """返回第 day 天早晨的数量，最后一天早晨固定剩1个。"""
    if not 1 <= day <= last_day:
        raise ValueError("必须满足 1 <= day <= last_day")

    if day == last_day:              # 终止条件
        return 1

    tomorrow = peaches(day + 1, last_day)  # 求明天的数量
    return 2 * (tomorrow + 1)        # 由明天的答案算出今天的答案


print("第1天的桃子数：", peaches())

输出：

第1天的桃子数： 1534

tomorrow = peaches(...) 会先等待子调用执行完毕，再得到返回值。每一层都有自己的 day 和 tomorrow，不是多个调用共享同一组局部变量。return 把当前这一层的答案交给上一层调用者。

Python 循环实现

直接从最后一天向前计算，不需要保存等待返回的函数调用：

def peaches_iterative(last_day=10):
    if last_day < 1:
        raise ValueError("last_day 必须是正整数")

    count = 1
    for _ in range(last_day - 1):    # D天对应D-1次吃桃操作
        count = 2 * (count + 1)
    return count


print(peaches_iterative())  # 1534

循环版本时间复杂度仍为 $O(D)$ ，辅助空间为 $O(1)$ 。两种实现依据同一个数学关系，区别在于计算过程如何组织。

算法执行过程

交互动画

动画默认展示第10天早晨剩1个桃子的题目。点击“下一步”，依次从第10天回推第9天、第8天，直到第1天得到1534个；每一步先补回多吃的1个，再把数量乘2。这对应递归的返回阶段，也与循环实现的计算顺序一致。

黄色节点表示当前天，蓝色节点表示已知数量，问号表示尚未求出的数量。时间轴按天数从左到右排列，逆推方向从右向左；可以横向滚动查看，表格同步列出每天早晨的数量和计算关系。

支持上一步、下一步、自动演示、暂停、重置和全屏。修改天数后点击“应用”，可演示1到10天；只有1天时直接得到1个桃子，不需要逆推。第10天早晨是已知边界，10天对应9次吃桃操作和9次逆推。

递归调用与返回

向下调用时，函数还不知道答案，只是在等待下一天的结果：

peaches(1, 10)
  → peaches(2, 10)
    → peaches(3, 10)
      → ……
        → peaches(10, 10) 返回1

到达终止条件以后，答案按相反方向返回：

天数 $d$	$P(d)$	由下一天计算当前这一天
10	1	已知条件
9	4	$2(1+1)$
8	10	$2(4+1)$
7	22	$2(10+1)$
6	46	$2(22+1)$
5	94	$2(46+1)$
4	190	$2(94+1)$
3	382	$2(190+1)$
2	766	$2(382+1)$
1	1534	$2(766+1)$

可以用正向过程核对答案：1534吃掉一半再多吃1个，剩766；766按相同规则剩382；继续执行，经过9次后剩1个。反推得到的数量始终满足题意。

观察递归过程时，可以区分两个阶段：

调用阶段： 从第1天进入第2天，继续调用直到第10天；当前层等待下一天的答案。
返回阶段： 第10天返回1，再依次计算第9天、第8天，直到第1天。

循环实现直接执行第2阶段的反推过程。表格中的反推顺序是第10天到第1天，猴子实际吃桃的时间顺序是第1天到第9天。

复杂度分析

为了分析复杂度，将最后一天推广为第 $D$ 天。先采用课程常用的基本操作计数模型，把一次整数加法、乘法等算术操作视为常数时间，辅助空间按变量和栈帧数量计算。

每层只进行一次递归调用和常数次额外操作。从第1天调用到第 $D$ 天，共有 $D$ 次调用，因此时间复杂度为 $O(D)$ 。

在到达最后一天时，前面的调用都还在等待返回，最多同时保留 $D$ 层函数调用。递归栈保存每一层的参数、局部变量和返回位置，辅助空间复杂度为 $O(D)$ 。

循环版本在同一计数模型下，时间复杂度为 $O(D)$ ，辅助空间复杂度为 $O(1)$ 。

Python 大整数的影响

上述复杂度采用单位成本模型。Python 的整数可以不断变大，桃子数量随天数指数增长，其二进制位数为 $O(D)$ 。严格按位运算和位存储计费时，整数操作不能一直视为常数，循环版本的整数存储也不能视为常数位空间。入门分析中应明确使用的计数模型。

易错点

易错点	正确理解
把10天写成10次吃桃操作	第10天早晨剩1个，实际只吃了9次
写成 `2 * tomorrow + 1`	应写成 `2 * (tomorrow + 1)`
认为递归参数必须减小	`day` 增加，但距离终止条件的剩余天数减少
当前层没有返回结果	每层都要把当前天的答案返回给调用者
把大量桃子逐个模拟	只维护数量即可，无须创建桃子列表

Python 的递归深度受运行环境限制。天数较多时可使用循环版本；该单链递归没有重复求解同一个子问题，不需要额外添加缓存。

课堂练习

第5天早晨剩1个桃子，第1天早晨有多少个？实际进行了几次吃桃操作？
手算第9天和第8天的数量，并写出对应的返回表达式。
如果最后一天早晨剩的是 $r$ 个桃子，应修改递归函数的哪一处？

参考答案

第1天为46个，实际吃桃4次。
第9天为 2 * (1 + 1) = 4；第8天为 2 * (4 + 1) = 10。
将终止条件的返回值由1改为 $r$ ，反推关系保持不变。

相关学习：递归方法实例、递归与分治。