递归方法实例

周子力大约 19 分钟教学文档算法设计与分析递归Python复杂度分析

递归方法实例

递归可以把一个暂时难以直接解决的问题，转化为规模更小的同类问题。学会递归，需要能说清楚函数解决什么问题、什么时候停止，以及如何利用子问题的答案完成当前问题。

下面通过猴子吃桃、约瑟夫环和汉诺塔三个实例，依次学习单链递归、编号转换和两次递归调用。每个实例都包含数学分析、Python 实现、执行过程和复杂度分析。阅读前需要掌握函数、条件判断、循环和取余运算；概念背景可参考递归与分治。

一设计递归函数的四个问题

1 函数解决什么问题

先用一句话说明函数的含义。例如，peaches(day, last_day) 表示“求第 day 天早晨的桃子数量，已知第 last_day 天早晨剩1个”。函数的参数和返回值一旦明确，才能判断递归调用是否解决了所需的子问题。

2 什么情况下可以直接回答

这就是递归的终止条件，也称递归基。例如，猴子吃桃中最后一天的桃子数已知；约瑟夫环只剩一个人时，幸存者已知；汉诺塔只有一个圆盘时，直接移动即可。

3 当前问题怎样依赖子问题

建立递归关系，说明子问题的答案怎样转换成当前问题的答案。可以先假设子问题已经正确解决，再考虑当前这一层需要做什么，不必一开始就在脑中展开所有调用。

4 为什么一定能结束

必须找到一个不断减少、最终到达边界的量。这个量可能是人数、圆盘数，也可能是距离最后一天的剩余天数。参数本身不一定减少，但距离终止条件必须越来越近。

下面是求值型递归的分析框架，作为伪代码阅读：

求解当前问题：
    如果到达终止条件：
        直接返回答案
    求解规模更小的同类问题
    利用子问题的答案计算并返回当前答案

“递推关系”描述答案之间的数学关系；“递归程序”通过函数调用自身来执行求解。相同的递推关系也可能用循环实现。

二猴子吃桃

1 题目与边界

猴子从第1天开始，每天吃掉现有桃子的一半，再多吃1个。第10天早晨发现只剩1个桃子。问第1天早晨有多少个桃子。

这里的“剩1个”发生在第10天早晨，因而第1天到第9天共进行了9次吃桃操作，第10天不再执行吃桃规则。这个时间边界决定了递归应该在哪里停止。

2 从题意建立递归关系

设第 $d$ 天早晨有 $P(d)$ 个桃子，吃完以后留到下一天，因此：

P(d+1)=\frac{P(d)}{2}-1.

题目已知的是最后一天的数量，把等式反过来得到：

P(d)=2\bigl(P(d+1)+1\bigr),\qquad P(10)=1.

这表示：如果知道明天的桃子数，就能计算今天的桃子数。于是求第1天的问题可以交给求第2天的函数，第2天再交给第3天，直到第10天直接返回1。

虽然 day 每次加1，但剩余天数 last_day - day 每次减1，所以递归一定会到达终止条件。

3 Python 递归实现

参数约定为正整数，且 day 不晚于 last_day。把下面代码完整复制到 Python 文件即可运行：

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 把当前这一层的答案交给上一层调用者。

4 递进去与返回来的过程

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

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个。反推得到的数量始终满足题意。

5 复杂度与循环实现

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

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

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

如果直接从最后一天向前循环，就不需要保存等待返回的调用：

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)$ 。两种实现依据同一个数学关系，区别在于计算过程如何组织。

Python 大整数的影响

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

三约瑟夫环

1 题目与模拟过程

$n$ 个人围成一圈，编号为1到 $n$ 。从1号开始报数，数到 $k$ 的人出局；下一人重新从1报数，直到只剩一个人。求最后幸存者的原始编号。约定 $n$ 和 $k$ 都是正整数。

例如 $n=7,k=3$ 时：

轮次	开始报数的人	出局者	下一轮开始报数的人
1	1	3	4
2	4	6	7
3	7	2	4
4	4	7	1
5	1	5	1
6	1	1	4

出局顺序是3、6、2、7、5、1，最后留下4号。逐个删除可以求解，但如果只要求幸存者，就可以利用更小圆环的答案。

2 删除一个人之后仍然是同类问题

第一次出局之后，还有 $n-1$ 个人，报数规则不变。这就是一个规模更小的约瑟夫环。不过它的报数起点变了，所以小环得到的编号必须转换回原来的编号。

为使转换公式简单，函数内部使用0到 $n-1$ 的编号。原题中的1号对应内部0号，原题中的3号对应内部2号，最终输出时再加1。

在内部编号下，从0开始报数，首次出局者是 $(k-1)\bmod n$ ，下一轮起点是 $k\bmod n$ 。把这个起点重新编号为0，沿圆环为其他幸存者编号。

以 $n=7,k=3$ 为例，原题3号出局后的映射为：

原题编号	原来的内部编号	小环的新内部编号
4	3	0
5	4	1
6	5	2
7	6	3
1	0	4
2	1	5

如果子问题告诉我们幸存者在新编号中是 $x$ ，其原来的内部编号就是：

(x+k)\bmod n.

加 $k$ 是恢复原来的起点偏移，取余是处理绕过圆环末尾的情况。偏移量是报数间隔 $k$ ，不是被删除人数1，也不是圆环人数 $n$ 。

3 建立递归公式

令 $f(n,k)$ 表示人数为 $n$ 、报数间隔为 $k$ 时，幸存者从0开始的内部编号。于是：

f(n,k)= \begin{cases} 0, & n=1,\\ \bigl(f(n-1,k)+k\bigr)\bmod n, & n>1. \end{cases}

终止条件是只剩一个人，其内部编号一定为0。每次调用让人数减1，最终会到达这个条件。子问题返回的是重新编号后的位置，当前层负责把它映射回自己的圆环。

4 Python 递归实现

对外函数返回原题中从1开始的编号；内部函数始终使用从0开始的编号，避免在每一层混用两种编号。

def josephus(n, k):
    """返回幸存者从1开始的原始编号。"""
    if n < 1 or k < 1:
        raise ValueError("n 和 k 必须是正整数")

    def survivor(size):
        """返回当前圆环中从0开始的幸存者编号。"""
        if size == 1:
            return 0

        smaller = survivor(size - 1)  # 小环的幸存者位置
        return (smaller + k) % size   # 映射回当前圆环

    return survivor(n) + 1           # 只在最终输出前加1


print("幸存者编号：", josephus(7, 3))

输出：

幸存者编号： 4

递归向下依次求人数7、6、5直到1的子问题，返回时依次计算：

人数 $n$	幸存者内部编号 $f(n,3)$	计算过程
1	0	终止条件
2	1	$(0+3)\bmod2$
3	1	$(1+3)\bmod3$
4	0	$(1+3)\bmod4$
5	3	$(0+3)\bmod5$
6	0	$(3+3)\bmod6$
7	3	$(0+3)\bmod7$

最后内部编号为3，对应原题编号4。表格每一行描述的是不同大小圆环各自的幸存者位置，不是同一个人在模拟过程中不断改变自己的原始编号。

5 复杂度与循环实现

采用前述基本操作计数模型，并把一次取余视为常数时间。每层只调用一次人数减1的子问题，有：

T(n)=T(n-1)+O(1),\qquad T(1)=O(1).

展开可知，共有 $n$ 层、每层常数工作量，所以时间复杂度为 $O(n)$ 。最大调用深度为 $n$ ，辅助空间复杂度为 $O(n)$ 。这一结论针对公式求幸存者，不是逐个删除列表的模拟算法。

由人数1的答案开始，也可以逐步计算人数2、3直到 $n$ 的答案：

def josephus_iterative(n, k):
    if n < 1 or k < 1:
        raise ValueError("n 和 k 必须是正整数")

    result = 0
    for size in range(2, n + 1):
        result = (result + k) % size
    return result + 1


print(josephus_iterative(7, 3))  # 4

循环版本时间复杂度为 $O(n)$ ，辅助空间为 $O(1)$ 。它正好按递归返回时的顺序计算各层答案，不需要把等待状态放入递归栈。

四汉诺塔

1 题目与函数含义

A柱上有 $n$ 个圆盘，圆盘从下到上越来越小。借助B柱，把所有圆盘移到C柱。每次只能移动一个圆盘，只能拿走某柱最上面的圆盘，大盘不能放在小盘上。

将函数定义为 hanoi(n, source, auxiliary, target)：借助 auxiliary，把 source 上最上面的 n 个圆盘合法地移到 target。本例约定 $n\geq1$ ，程序逐步输出移动操作，不返回一个数值答案。

2 把任务分成三个顺序步骤

要把最大的圆盘从A移到C，必须先把上面的 $n-1$ 个圆盘移到B，并保证C上没有更小的圆盘。因此可按以下顺序执行：

借助C，把上面的 $n-1$ 个圆盘从A移到B。
把第 $n$ 个圆盘从A移到C。
借助A，把 $n-1$ 个圆盘从B移到C。

第1步和第3步都是规模为 $n-1$ 的汉诺塔任务。我们可以让同一个函数执行它们，只需调整柱子的角色：

当前任务	源柱 source	辅助柱 auxiliary	目标柱 target
整体任务	A	B	C
第一次递归	A	C	B
第二次递归	B	A	C

“辅助柱”是当前子问题中的角色，不是某根柱子固定的名称。如果递归时只是复制参数、不交换角色，就无法完成正确的移动。

只有一个圆盘时，直接从源柱移到目标柱。每次递归让圆盘数减1，最终一定会到达这个条件。

3 Python 递归实现

下面代码直接输出每一步，不使用全局计数器，也不保存全部移动步骤：

def hanoi(n, source="A", auxiliary="B", target="C"):
    """输出把n个圆盘从source移到target的合法移动过程。"""
    if n < 1:
        raise ValueError("n 必须是正整数")

    if n == 1:
        print(f"圆盘1：{source} → {target}")
        return

    # 先把上面n-1个圆盘移到辅助柱
    hanoi(n - 1, source, target, auxiliary)

    # 子任务完成后，才能移动当前最大的圆盘
    print(f"圆盘{n}：{source} → {target}")

    # 再把n-1个圆盘从辅助柱移到目标柱
    hanoi(n - 1, auxiliary, source, target)


hanoi(3)

输出：

圆盘1：A → C
圆盘2：A → B
圆盘1：C → B
圆盘3：A → C
圆盘1：B → A
圆盘2：B → C
圆盘1：A → C

圆盘编号表示大小，1最小，3最大。前3步完成第一个子任务，第4步移动最大圆盘，后3步完成第二个子任务。

4 两次递归如何执行

以3个圆盘为例，调用结构是：

hanoi(3, A, B, C)
├─ hanoi(2, A, C, B)
│  ├─ hanoi(1, A, B, C)  输出 A → C
│  ├─ 移动圆盘2          输出 A → B
│  └─ hanoi(1, C, A, B)  输出 C → B
├─ 移动圆盘3             输出 A → C
└─ hanoi(2, B, A, C)
   ├─ hanoi(1, B, C, A)  输出 B → A
   ├─ 移动圆盘2          输出 B → C
   └─ hanoi(1, A, B, C)  输出 A → C

执行是从上到下、逐个完成的。第一次递归没有完成时，当前调用停在第一条 hanoi(...) 语句处等待；它完成后，才执行中间的 print，再进入第二次递归。

图中的“移动圆盘”是当前函数内部的操作，不是一次额外的函数调用。两次递归也不是同时执行，所以不能把整棵调用树的节点数当作同时占用的栈空间。

汉诺塔的递归基中，return 只表示当前任务已完成。这里的函数通过输出产生效果，默认返回 None，与前两个实例通过 return 交回答案的方式不同。

5 移动次数与最优性

设移动 $n$ 个圆盘所需的最少步数为 $M(n)$ 。上述方案的两个子任务各需要 $M(n-1)$ 步，中间移动最大圆盘需要1步：

M(1)=1,\qquad M(n)=2M(n-1)+1.

为什么这也是最少步数？考虑任何完成任务的方案中最大圆盘的第一次和最后一次移动：第一次移动前，其他 $n-1$ 个盘必须全部放在另一根柱子上，至少需要 $M(n-1)$ 步；最后一次移动后，其他圆盘必须从另一根柱子移到它上面，至少还需要 $M(n-1)$ 步。最大圆盘本身至少移动一次。因此总步数至少为 $2M(n-1)+1$ ，而递归方案恰好达到这个下界。

将递推关系两边加1，可得 $M(n)+1=2(M(n-1)+1)$ 。从 $M(1)+1=2$ 展开，得到：

M(n)=2^n-1.

3个圆盘需要7步，4个需要15步，10个需要1023步。圆盘数只增加1，移动次数就接近翻倍。

6 时间复杂度与空间复杂度

把每次输出一条移动记录按一个基本操作计数，有：

T(n)=2T(n-1)+O(1).

调用树各层的调用数是 $1,2,4,\ldots,2^{n-1}$ ，总调用数为 $2^n-1$ ，因此时间复杂度为 $O(2^n)$ 。题目要求输出全部移动步骤时，仅输出这些记录就需要这么多次操作。

一条调用链中的圆盘数依次为 $n,n-1,\ldots,1$ ，最长只有 $n$ 层。因此辅助空间复杂度为 $O(n)$ ，而不是 $O(2^n)$ 。第一次递归返回时，它占用的子调用栈已经释放，第二次递归可以再次使用这些空间。

如果改用列表保存全部步骤，还要额外存储 $2^n-1$ 条记录；本文的逐步输出实现不包含这部分存储。这里分析的是移动记录数量，没有进一步按输出字符串的字符数计费。

如果只问最少移动次数，可以直接使用 2 ** n - 1，无须执行移动过程。计算一个总数和列出全部步骤，是两个不同的任务。 更进一步的指定步骤查询可参考汉诺塔。

五三个实例的共同规律

比较项	猴子吃桃	约瑟夫环	汉诺塔
函数任务	求某一天的桃子数	求当前圆环幸存者编号	输出当前圆盘任务的移动过程
终止条件	到达最后一天	人数为1	圆盘数为1
减少的量	剩余天数	人数	圆盘数
每个非终止调用的子调用数	1	1	2
当前层的工作	从明天数量计算今天数量	把小环编号映射回当前圆环	两次递归之间移动最大盘
时间复杂度	$O(D)$	$O(n)$	$O(2^n)$
辅助空间复杂度	$O(D)$	$O(n)$	$O(n)$

表中沿用前述基本操作计数模型。前两个实例的递归调用构成一条链，汉诺塔构成一棵树。但复杂度不是由代码里有没有出现“递归”决定的，而要分别考察：总共有多少次调用、每次做多少额外工作、最多有多少层调用同时等待。

正确性也可以按同一个思路解释：先确认终止条件的答案正确，再假设较小问题已正确解决，证明当前层的转换或操作仍然正确。猴子吃桃的转换来自吃桃等式，约瑟夫环的转换来自编号映射，汉诺塔则依靠两个合法子任务和中间的合法移动。

六常见错误与使用建议

常见问题	会发生什么	检查方法
遗漏终止条件	调用无法正常结束	先手算最小输入
参数不趋近边界	递归反复求相同问题或越走越远	指出每次减少的量
求值型递归忘记返回答案	调用者拿到 `None`	检查每个有效分支的 `return`
约瑟夫环混用两种编号	幸存者编号偏差1	内部统一从0开始，最后加1
汉诺塔柱子角色传错	移动目标错误或违反大小规则	逐次检查源柱、辅助柱、目标柱
把调用总数当作栈深度	空间复杂度判断错误	画出最长同时等待的调用链

Python 的递归深度受运行环境限制，可以用 sys.getrecursionlimit() 查看。输入较大时，猴子吃桃和约瑟夫环可采用上述循环版本，避免过深的调用栈。汉诺塔即使圆盘数没有达到递归深度限制，输出量也可能已经非常大，需要先估算 $2^n-1$ 。

猴子吃桃和约瑟夫环的单链计算没有重复求解同一个子问题，不需要额外加上缓存。汉诺塔中，即使相同的函数参数组合再次出现，它也发生在不同的圆盘状态下，需要实际执行对应的移动；缓存一次调用的返回值不能代替这些操作。记忆化主要用于可以重复利用答案的子问题，例如朴素递归计算斐波那契数列。

七课堂练习

改变吃桃天数。 第5天早晨剩1个桃子，第1天有多少个？画出调用链，说明执行了几次吃桃操作。
解释递归参数。 猴子吃桃的 day 在增加，为什么递归仍能终止？如果误写成 day - 1 会怎样？
检验编号转换。 求 $n=5,k=2$ 的约瑟夫环幸存者，同时写出逐个报数的出局顺序，核对两种方法。
比较树与栈。 4个圆盘的汉诺塔需要多少步？调用总数是多少，最长调用链有几层？
把数学关系变为程序。 独立写出猴子吃桃或约瑟夫环的循环版本，说明为什么时间复杂度不变、辅助空间减少。

参考答案

第1天为46个，调用涉及5天，实际吃桃4次。
剩余天数 last_day - day 在减少。误写成 day - 1 会远离最后一天；本文代码会在越过有效范围时抛出 ValueError，若没有范围检查则可能持续调用直到触发递归深度错误。
出局顺序为2、4、1、5，幸存者为3号。
需要15步；对于本文以 n == 1 为终止条件的实现，调用总数为15，最长调用链有4层。
循环按递归返回时的顺序计算，只保留当前结果，省去了等待返回的调用栈。