第1章 递归问题 (Recurrence Problems)

一、导读

1.1 本章学习目标

在本章结束时，你将能够：

• 理解递归的本质：将大问题分解为相同结构的子问题
• 建立递推关系：从实际问题中抽象出数学递推式
• 求解汉诺塔问题：掌握 T(n) = 2T(n-1) + 1 的推导与闭合形式 T(n) = 2^n - 1
• 分析约瑟夫问题：理解 J(n) 的递推关系及其高效计算方法
• 使用递归树：可视化递归展开过程，直观理解时间复杂度
• 掌握"复制-粘贴"策略：理解递归解法的构造性证明思想
• 识别递归模式：在算法设计中主动运用递归思维

1.2 为什么本章如此重要

递归是计算机科学中最核心、最优雅的概念之一。从快速排序到归并排序，从树的遍历到动态规划，递归思维贯穿了整个算法世界。更重要的是，递归提供了一种强大的问题建模方式：当你面对一个复杂问题时，如果能够将其分解为规模更小但结构相同的子问题，你就找到了解决问题的钥匙。

《具体数学》以递归问题开篇并非偶然。Graham、Knuth 和 Patashnik 三位作者深知，递归不仅是编程技巧，更是连接离散数学与计算机科学的桥梁。通过研究汉诺塔和约瑟夫这两个经典问题，我们将学习如何从具体问题中提炼递推关系，如何将递推关系转化为闭合形式，以及如何用数学工具分析递归算法的效率。

对于程序员而言，掌握递归意味着掌握了分析算法复杂度的基本工具。当你写出一个递归函数时，你不仅是在编写代码，更是在定义一个数学对象——这个对象的性质可以通过数学方法精确刻画。这种"代码即数学"的视角，是成为优秀算法工程师的关键。

1.3 核心问题引导

在阅读本章之前，请思考以下问题：

汉诺塔游戏中，移动 n 个盘子最少需要多少步？为什么这个下界是紧的？

约瑟夫问题中，当 n 个人围成一圈、每次数到 2 就淘汰一人时，最后幸存者的位置有什么规律？

递推关系 T(n) = 2T(n-1) + 1 为什么可以写成闭合形式 T(n) = 2^n - 1？如何严格证明？

递归树如何帮助我们理解递归算法的时间复杂度？它与数学归纳法有何联系？

为什么有些递归问题可以直接求出闭合形式，而有些只能保留递推形式？

"复制-粘贴"策略在汉诺塔问题中如何体现？这种策略对其他递归问题有何启示？

约瑟夫问题的递推关系 J(2n) = 2J(n) - 1 和 J(2n+1) = 2J(n) + 1 是如何推导出来的？

如何将一个递归算法转换为迭代算法？这种转换对性能有何影响？

二、核心概念详解

2.1 汉诺塔问题：递归的经典范例

问题描述

汉诺塔（Tower of Hanoi）是一个经典的数学谜题，由法国数学家 Édouard Lucas 于 1883 年发明。游戏包含三根柱子和 n 个大小不同的圆盘，初始时所有圆盘按从小到大的顺序叠放在第一根柱子上。目标是将所有圆盘移动到第三根柱子上，规则如下：

每次只能移动一个圆盘

任何时候大盘不能放在小盘上面

可以使用中间柱子作为临时存放

通俗地说，你需要把一摞盘子从 A 柱搬到 C 柱，过程中可以借助 B 柱，但必须保持"上小下大"的顺序。

递推关系的建立

让我们从最简单的情况开始分析：

• n = 1：只需 1 步，直接将盘子从 A 移到 C
• n = 2：需要 3 步：小盘 A→B，大盘 A→C，小盘 B→C
• n = 3：需要 7 步

一般地，设 T(n) 为移动 n 个盘子所需的最少步数。要将 n 个盘子从 A 移到 C，我们必须：

先将上面的 n-1 个盘子从 A 移到 B（借助 C），需要 T(n-1) 步

将最大的盘子从 A 移到 C，需要 1 步

再将 n-1 个盘子从 B 移到 C（借助 A），需要 T(n-1) 步

因此得到递推关系：

$$T(n) = 2T(n-1) + 1, \quad T(1) = 1$$

闭合形式的推导

如何从递推关系得到闭合形式？我们采用"展开法"：

$$\begin{aligned}

T(n) &= 2T(n-1) + 1 \\

&= 2(2T(n-2) + 1) + 1 = 2^2 T(n-2) + 2 + 1 \\

&= 2^2(2T(n-3) + 1) + 2 + 1 = 2^3 T(n-3) + 2^2 + 2 + 1 \\

&= \cdots \\

&= 2^{n-1} T(1) + 2^{n-2} + 2^{n-3} + \cdots + 2 + 1 \\

&= 2^{n-1} + 2^{n-2} + \cdots + 2 + 1 \\

&= 2^n - 1

\end{aligned}$$

最后一步使用了等比数列求和公式。因此，T(n) = 2^n - 1。

严格证明：数学归纳法

猜想 T(n) = 2^n - 1，我们用数学归纳法证明：

基础情况：n = 1 时，T(1) = 1 = 2^1 - 1，成立。

归纳假设：假设 T(k) = 2^k - 1 对所有 k < n 成立。

归纳步骤：

$$T(n) = 2T(n-1) + 1 = 2(2^{n-1} - 1) + 1 = 2^n - 2 + 1 = 2^n - 1$$

证毕。

最优性证明

T(n) = 2^n - 1 是最少步数吗？是的。我们可以用归纳法证明下界：

• n = 1 时，至少需要 1 步，下界为 1 = 2^1 - 1
• 假设 n-1 个盘子至少需要 2^{n-1} - 1 步
• 对于 n 个盘子，最大盘子必须从 A 移到 C，这要求上面 n-1 个盘子先全部移到 B（至少 2^{n-1} - 1 步），然后最大盘子移动 1 步，最后 n-1 个盘子从 B 移到 C（至少 2^{n-1} - 1 步）
• 总计至少 2(2^{n-1} - 1) + 1 = 2^n - 1 步

因此 T(n) = 2^n - 1 既是上界也是下界，即最优解。

2.2 "复制-粘贴"策略：递归的构造性视角

汉诺塔的解法揭示了一个重要的递归思想：复制-粘贴。

要将 n 个盘子从 A 移到 C：

"复制" n-1 个盘子到 B（使用与原始问题相同的策略，只是目标柱不同）

移动最大盘子

"粘贴" n-1 个盘子到 C（再次使用相同策略）

这种策略的核心在于：解决规模为 n 的问题时，我们调用了两次规模为 n-1 的子问题的解法。这正是递归的本质——自我引用。

从程序实现的角度看，汉诺塔的递归代码如下：

def hanoi(n, source, target, auxiliary):
    """
    将 n 个盘子从 source 柱移动到 target 柱，借助 auxiliary 柱
    
    参数:
        n: 盘子数量
        source: 源柱子名称
        target: 目标柱子名称
        auxiliary: 辅助柱子名称
    """
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
        return 1
    # 第一步：将 n-1 个盘子从 source 移到 auxiliary
    steps1 = hanoi(n-1, source, auxiliary, target)
    # 第二步：移动最大盘子
    print(f"Move disk {n} from {source} to {target}")
    # 第三步：将 n-1 个盘子从 auxiliary 移到 target
    steps2 = hanoi(n-1, auxiliary, target, source)
    return steps1 + 1 + steps2

# 测试
total_steps = hanoi(3, 'A', 'C', 'B')
print(f"Total steps: {total_steps}")

运行结果：

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C
Total steps: 7

这段代码完美体现了"复制-粘贴"策略：hanoi(n-1, source, auxiliary, target) 和 hanoi(n-1, auxiliary, target, source) 是同一函数的两次调用，只是参数不同。

2.3 约瑟夫问题：循环淘汰的数学

问题描述

约瑟夫问题（Josephus Problem）源于一个历史传说：Flavius Josephus 是一位犹太历史学家，在罗马军队包围时，他和 40 名战友决定宁死不降，于是围成一圈，从某个人开始报数，每数到第 3 个人就自杀，直到只剩一人。Josephus 不想死，他应该站在什么位置才能成为最后的幸存者？

简化版本：n 个人编号为 1, 2, ..., n，围成一圈。从 1 开始报数，每数到 2 的人被淘汰，下一人重新从 1 开始报数。求最后幸存者的编号 J(n)。

小规模案例分析

让我们手动计算前几个值：

• n = 1：只有 1 人，J(1) = 1
• n = 2：1, 2 → 淘汰 2，J(2) = 1
• n = 3：1, 2, 3 → 淘汰 2，剩 1, 3 → 淘汰 1，J(3) = 3
• n = 4：1, 2, 3, 4 → 淘汰 2, 4，剩 1, 3 → 淘汰 1，J(4) = 3
• n = 5：1, 2, 3, 4, 5 → 淘汰 2, 4, 1, 5，J(5) = 3
• n = 6：淘汰 2, 4, 6, 3, 1，J(6) = 5
• n = 7：淘汰 2, 4, 6, 1, 5, 3，J(7) = 7
• n = 8：淘汰 2, 4, 6, 8, 3, 7, 5，J(8) = 1

列出表格：

观察规律：J(n) 似乎总是奇数，且在 n 是 2 的幂时重置为 1。

递推关系的推导

关键洞察：第一轮淘汰后，所有偶数位置的人都被淘汰了。

情况 1：n 是偶数，n = 2m

第一轮淘汰 2, 4, 6, ..., 2m，剩下 1, 3, 5, ..., 2m-1，共 m 人。接下来从 1 开始继续报数。

如果我们重新编号：1→1, 3→2, 5→3, ..., 2m-1→m，那么问题转化为 m 个人的约瑟夫问题。设 m 个人时的幸存者编号为 J(m)，则原编号为 2J(m) - 1。

因此：J(2m) = 2J(m) - 1

情况 2：n 是奇数，n = 2m + 1

第一轮淘汰 2, 4, 6, ..., 2m，剩下 1, 3, 5, ..., 2m+1，共 m+1 人。但注意，下一轮从 1 开始报数，1 会被淘汰（因为上一轮最后淘汰的是 2m，下一个是 2m+1 报 1，然后 1 报 2 被淘汰）。

等等，让我重新分析。n = 2m+1 时：

• 第 1 轮：淘汰 2
• 第 2 轮：淘汰 4
• ...
• 第 m 轮：淘汰 2m
• 剩下：1, 3, 5, ..., 2m+1，共 m+1 人
• 下一轮从 2m+1 之后的 1 开始，1 报 1，3 报 2，所以 3 被淘汰？

不对，让我更仔细地模拟 n = 5：

• 初始：1, 2, 3, 4, 5
• 从 1 开始：1 报 1，2 报 2 → 淘汰 2
• 从 3 开始：3 报 1，4 报 2 → 淘汰 4
• 从 5 开始：5 报 1，1 报 2 → 淘汰 1
• 从 3 开始：3 报 1，5 报 2 → 淘汰 5
• 剩下 3，J(5) = 3

所以 n = 5 = 2×2 + 1，m = 2。第一轮（指淘汰偶数的过程）后剩下 1, 3, 5，但紧接着 1 也被淘汰（因为 5 报 1，1 报 2）。所以实际上剩下 3, 5，然后从 3 开始。

更准确地说，n = 2m+1 时：

• 淘汰 2, 4, ..., 2m（共 m 人）
• 剩下 1, 3, 5, ..., 2m+1（共 m+1 人）
• 下一轮：2m+1 报 1，1 报 2 → 淘汰 1
• 剩下 3, 5, ..., 2m+1（共 m 人），从 3 开始报数

重新编号：3→1, 5→2, ..., 2m+1→m。如果 m 人问题的幸存者是新编号中的 J(m)，则原编号为 2J(m) + 1。

因此：J(2m+1) = 2J(m) + 1

综合两种情况，得到递推关系：

$$J(1) = 1$$

$$J(2n) = 2J(n) - 1, \quad n \geq 1$$

$$J(2n+1) = 2J(n) + 1, \quad n \geq 1$$

闭合形式的发现

让我们重新观察 J(n) 的值：

惊人的规律：J(n) 等于将 n 的二进制表示左循环移位一位！

例如：n = 13 = 1101₂，左循环移位得到 1011₂ = 11，而 J(13) = 11。✓

另一种表述：设 n = 2^m + l，其中 0 ≤ l < 2^m（即 2^m 是不超过 n 的最大 2 的幂），则：

$$J(n) = 2l + 1$$

验证：n = 13 = 8 + 5，所以 m = 3, l = 5，J(13) = 2×5 + 1 = 11。✓

n = 10 = 8 + 2，J(10) = 2×2 + 1 = 5。✓

n = 16 = 16 + 0，J(16) = 2×0 + 1 = 1。✓

闭合形式的证明

定理：若 n = 2^m + l，其中 0 ≤ l < 2^m，则 J(n) = 2l + 1。

证明：对 m 进行归纳。

基础情况：m = 0 时，n = 1 + l，由于 l < 1，所以 l = 0，n = 1，J(1) = 1 = 2×0 + 1。成立。

归纳假设：假设对所有 m' < m，结论成立。

归纳步骤：考虑 n = 2^m + l。

若 l = 0，则 n = 2^m。由递推关系 J(2^m) = 2J(2^{m-1}) - 1。反复应用：

$$J(2^m) = 2J(2^{m-1}) - 1 = 2(2J(2^{m-2}) - 1) - 1 = \cdots = 2^m J(1) - (2^{m-1} + \cdots + 2 + 1) = 2^m - (2^m - 1) = 1$$

而 2l + 1 = 2×0 + 1 = 1。成立。

若 l > 0，分两种情况：

情况 1：l 是偶数，l = 2k。则 n = 2^m + 2k = 2(2^{m-1} + k)。

$$J(n) = J(2(2^{m-1} + k)) = 2J(2^{m-1} + k) - 1$$

由归纳假设，J(2^{m-1} + k) = 2k + 1（因为 k < 2^{m-1}）。

$$J(n) = 2(2k + 1) - 1 = 4k + 1 = 2(2k) + 1 = 2l + 1$$

情况 2：l 是奇数，l = 2k + 1。则 n = 2^m + 2k + 1 = 2(2^{m-1} + k) + 1。

$$J(n) = J(2(2^{m-1} + k) + 1) = 2J(2^{m-1} + k) + 1$$

由归纳假设，J(2^{m-1} + k) = 2k + 1。

$$J(n) = 2(2k + 1) + 1 = 4k + 3 = 2(2k + 1) + 1 = 2l + 1$$

证毕。

2.4 递归树：可视化的力量

递归树是理解递归算法的强大工具。它将递归展开过程可视化，每一层代表一次递归调用，节点的值代表该层的工作量。

汉诺塔的递归树

对于 T(n) = 2T(n-1) + 1：

T(n)          层级 0: 1 个节点，工作量 1
        /    \
     T(n-1)  T(n-1)   层级 1: 2 个节点，工作量 2
     /  \    /  \
   ...  ... ... ...  层级 2: 4 个节点，工作量 4
   ...
  T(1) ... T(1)      层级 n-1: 2^{n-1} 个节点，工作量 2^{n-1}

总工作量 = 1 + 2 + 4 + ... + 2^{n-1} = 2^n - 1。

递归树的优势在于它直观地展示了：

每层的工作量呈指数增长

叶子节点的数量决定了基本情况被调用的次数

总工作量是各层工作量之和

更复杂的例子

考虑 T(n) = 3T(n/2) + n（这是某些分治算法的递推关系）：

T(n)              层级 0: 1 个节点，工作量 n
           / | \
       T(n/2) T(n/2) T(n/2)  层级 1: 3 个节点，工作量 3×(n/2)
       /|\   /|\   /|\
      ...   ...   ...        层级 2: 9 个节点，工作量 9×(n/4)
      ...
     T(1) ... T(1)           层级 log₂n: 3^{log₂n} 个节点

总工作量 = n + 3n/2 + 9n/4 + ... = n(1 + 3/2 + 9/4 + ...)

这是一个等比数列，公比为 3/2 > 1，主导项是最后一项。通过主定理（Master Theorem），我们知道 T(n) = Θ(n^{log₂3}) ≈ Θ(n^{1.585})。

递归树帮助我们直观理解为什么某些递归算法比线性更高效，以及分治策略的威力所在。

2.5 递归与迭代的等价性

每个递归算法都可以转换为迭代算法，反之亦然。这种等价性是计算理论的基础。

汉诺塔的迭代实现

虽然递归实现最自然，但我们也可以用迭代方式实现。关键观察：汉诺塔的移动序列有规律可循。

对于 n 个盘子，总共需要 2^n - 1 步。第 k 步（从 1 开始）移动的盘子编号等于 k 的二进制表示中最低位的 1 的位置（从 1 开始计数）。移动方向取决于盘子编号的奇偶性。

def hanoi_iterative(n):
    """汉诺塔的迭代实现"""
    total_steps = 2**n - 1
    for step in range(1, total_steps + 1):
        # 找到 step 的二进制表示中最低位 1 的位置
        disk = 1
        temp = step
        while temp % 2 == 0:
            disk += 1
            temp //= 2
        
        # 确定移动方向（简化版，假设三根柱子为 A, B, C）
        # 奇数号盘子顺时针移动，偶数号盘子逆时针移动
        if disk % 2 == 1:
            direction = "clockwise"
        else:
            direction = "counterclockwise"
        
        print(f"Step {step}: Move disk {disk} ({direction})")

hanoi_iterative(3)

递归转迭代的一般方法

显式栈：用栈数据结构模拟递归调用栈

尾递归优化：如果递归调用是函数的最后一步操作，可以转换为循环

记忆化：对于重叠子问题，用表格存储已计算的结果

例如，斐波那契数列的递归实现效率极低（指数时间），但用记忆化或迭代可以实现线性时间：

# 低效的递归
def fib_recursive(n):
    if n <= 1:
        return n
    return fib_recursive(n-1) + fib_recursive(n-2)

# 高效的迭代
def fib_iterative(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n+1):
        a, b = b, a + b
    return b

# 记忆化
def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

三、程序员的视角

3.1 在算法分析中的应用

递归思维在算法分析中无处不在。以下是几个典型例子：

归并排序

归并排序将数组分成两半，分别排序，然后合并。其时间复杂度满足：

$$T(n) = 2T(n/2) + O(n)$$

其中 O(n) 是合并两个有序数组的时间。通过主定理或递归树，可得 T(n) = O(n log n)。

快速排序

快速排序的平均情况时间复杂度也满足类似的递推关系，但最坏情况下（每次划分极不均匀）：

$$T(n) = T(n-1) + O(n) = O(n^2)$$

二叉树遍历

遍历一棵有 n 个节点的二叉树，时间复杂度为：

$$T(n) = T(k) + T(n-k-1) + O(1)$$

其中 k 是左子树的节点数。无论树的结构如何，T(n) = O(n)，因为每个节点恰好访问一次。

动态规划

许多动态规划问题本质上也是递归，只是通过记忆化避免了重复计算。例如，最长公共子序列（LCS）问题：

$$LCS(i, j) = \begin{cases}

0 & \text{if } i = 0 \text{ or } j = 0 \\

LCS(i-1, j-1) + 1 & \text{if } s_i = t_j \\

\max(LCS(i-1, j), LCS(i, j-1)) & \text{otherwise}

\end{cases}$$

3.2 常见陷阱与误区

陷阱 1：忽略基本情况

递归必须有终止条件，否则会导致无限递归和栈溢出。

# 错误：缺少基本情况
def bad_fib(n):
    return bad_fib(n-1) + bad_fib(n-2)

# 正确
def good_fib(n):
    if n <= 1:
        return n
    return good_fib(n-1) + good_fib(n-2)

陷阱 2：重复计算

朴素递归可能导致指数级的重复计算。

# 计算 fib(50) 可能需要几分钟
fib_recursive(50)

# 计算 fib(1000) 瞬间完成
fib_iterative(1000)

避免方法：使用记忆化或转换为迭代。

陷阱 3：栈溢出

递归深度过大时，可能超出系统栈空间。

# Python 默认递归深度限制约为 1000
import sys
sys.setrecursionlimit(10000)  # 谨慎使用

避免方法：对于深度较大的递归，优先使用迭代或尾递归优化。

陷阱 4：错误的递推关系

建立递推关系时，容易遗漏某些情况或重复计算。

避免方法：用小规模案例验证递推关系的正确性，确保覆盖所有情况。

3.3 与其他层级的联系

递归与计算机科学的多个领域紧密相关：

• 数据结构：树和图的定义本身就是递归的
• 编译器设计：语法分析常用递归下降解析器
• 操作系统：进程创建、文件系统遍历都涉及递归
• 人工智能：搜索算法（如 DFS）天然适合递归实现
• 函数式编程：递归是函数式语言的核心控制结构

理解递归，就是理解计算的本质。

四、代码实战

4.1 示例一：通用递归求解器

下面是一个通用的递归关系求解器，可以计算给定递推关系的值：

class RecurrenceSolver:
    """递归关系求解器"""
    
    def __init__(self):
        self.memo = {}
    
    def solve_hanoi(self, n):
        """求解汉诺塔问题的步数"""
        if n in self.memo:
            return self.memo[n]
        if n == 1:
            return 1
        result = 2 * self.solve_hanoi(n-1) + 1
        self.memo[n] = result
        return result
    
    def solve_josephus(self, n):
        """求解约瑟夫问题"""
        if n in self.memo:
            return self.memo[n]
        if n == 1:
            return 1
        if n % 2 == 0:
            result = 2 * self.solve_josephus(n // 2) - 1
        else:
            result = 2 * self.solve_josephus(n // 2) + 1
        self.memo[n] = result
        return result
    
    def josephus_closed_form(self, n):
        """约瑟夫问题的闭合形式解法"""
        # 找到不超过 n 的最大 2 的幂
        m = n.bit_length() - 1
        power_of_2 = 1 << m  # 2^m
        l = n - power_of_2
        return 2 * l + 1

# 测试
solver = RecurrenceSolver()
print("汉诺塔:")
for n in range(1, 11):
    print(f"  T({n}) = {solver.solve_hanoi(n)} = 2^{n} - 1 = {2**n - 1}")

print("\n约瑟夫问题:")
for n in range(1, 17):
    j_rec = solver.solve_josephus(n)
    j_closed = solver.josephus_closed_form(n)
    match = "✓" if j_rec == j_closed else "✗"
    print(f"  J({n:2d}) = {j_rec:2d} (闭合形式: {j_closed:2d}) {match}")

4.2 示例二：递归可视化

使用 matplotlib 绘制递归树：

import matplotlib.pyplot as plt
import matplotlib.patches as patches

def draw_recursion_tree(n, ax=None, x=0, y=0, dx=1, level=0):
    """绘制汉诺塔递归树"""
    if ax is None:
        fig, ax = plt.subplots(1, 1, figsize=(12, 8))
    
    # 绘制当前节点
    circle = plt.Circle((x, -y), 0.3, color='lightblue', ec='black')
    ax.add_patch(circle)
    ax.text(x, -y, f'T({n-level})', ha='center', va='center', fontsize=8)
    
    if level < n:
        # 左子节点
        left_x = x - dx
        draw_recursion_tree(n, ax, left_x, y+1, dx/2, level+1)
        
        # 右子节点
        right_x = x + dx
        draw_recursion_tree(n, ax, right_x, y+1, dx/2, level+1)
        
        # 绘制连线
        ax.plot([x, left_x], [-y-0.3, -(y+1)+0.3], 'k-', linewidth=0.5)
        ax.plot([x, right_x], [-y-0.3, -(y+1)+0.3], 'k-', linewidth=0.5)
    
    if level == 0:
        ax.set_xlim(-2**n, 2**n)
        ax.set_ylim(-n-1, 1)
        ax.set_aspect('equal')
        ax.axis('off')
        plt.title(f'Hanoi Recursion Tree (n={n})')
        plt.tight_layout()
        plt.savefig('hanoi_tree.png', dpi=150, bbox_inches='tight')
        plt.show()

# 绘制 n=4 的递归树
draw_recursion_tree(4)

4.3 示例三：性能对比

比较递归、记忆化和迭代三种实现的效率：

import time

def time_function(func, *args):
    """测量函数执行时间"""
    start = time.time()
    result = func(*args)
    elapsed = time.time() - start
    return result, elapsed

# 测试不同实现
n = 30

# 朴素递归（较慢，仅用于小 n）
start = time.time()
result_rec = solve_hanoi_recursive(n)
time_rec = time.time() - start

# 记忆化
solver = RecurrenceSolver()
start = time.time()
result_memo = solver.solve_hanoi(n)
time_memo = time.time() - start

# 闭合形式
start = time.time()
result_closed = 2**n - 1
time_closed = time.time() - start

print(f"n = {n}")
print(f"递归:     {result_rec}, 时间: {time_rec:.6f}s")
print(f"记忆化:   {result_memo}, 时间: {time_memo:.6f}s")
print(f"闭合形式: {result_closed}, 时间: {time_closed:.6f}s")

五、深入思考

5.1 历史背景

汉诺塔由法国数学家 Édouard Lucas 于 1883 年发明。Lucas 还发明了一个传说：在印度的一座寺庙里，僧侣们正在移动 64 个金盘，当他们完成时，世界将会终结。按照 T(64) = 2^64 - 1 ≈ 1.8 × 10^19 步的计算，如果每秒移动一步，需要约 5800 亿年——远超宇宙年龄。

约瑟夫问题以 Flavius Josephus 命名，他是公元 1 世纪的犹太历史学家。据传他在罗马军队包围时，与战友约定集体自杀，但他通过计算找到了幸存的位置。当然，这个故事可能是后人附会的。

这两个问题在 20 世纪因计算机科学的兴起而重新受到关注，成为递归和算法分析的经典案例。

5.2 未解决的问题

约瑟夫问题的一般形式（每数到 k 淘汰一人，k > 2）没有简单的闭合形式。虽然存在 O(n) 的动态规划解法，但对于大规模 n，是否有更高效的算法仍是一个开放问题。

此外，汉诺塔的变种问题（如四根柱子、受限移动等）的最优解仍然是研究热点。Frame-Stewart 猜想给出了四柱汉诺塔的最优步数公式，但至今未被完全证明。

5.3 延伸阅读

《具体数学》（Concrete Mathematics） - Graham, Knuth, Patashnik

本章内容的源头，强烈推荐通读全书。

《算法导论》（Introduction to Algorithms） - Cormen et al.

第 4 章详细讲解了递归式和主方法。

《计算机程序设计艺术》卷 1（The Art of Computer Programming, Vol. 1） - Donald Knuth

Knuth 对汉诺塔和约瑟夫问题有更深入的分析。

"The Tower of Hanoi: Bibliography" - Paul K. Stockmeyer

关于汉诺塔问题的全面文献综述。

"Josephus Problem" - Wikipedia 和相关数学论文

了解约瑟夫问题的最新研究进展。

六、实验笔记

实验一：汉诺塔动画可视化

目标：使用 Python 的 turtle 或 pygame 库，实现汉诺塔的动画演示。

步骤：

安装依赖：pip install pygame

实现汉诺塔的图形界面，显示三根柱子和圆盘

实现递归算法，每一步更新图形界面

添加速度控制和暂停功能

记录移动步数，验证是否等于 2^n - 1

预期结果：能够流畅演示 n = 1 到 8 的汉诺塔求解过程。

思考题：

• 如何优化动画性能，使大规模演示不卡顿？
• 能否实现用户交互，让用户手动移动盘子并检测合法性？

实验二：约瑟夫问题的推广

目标：研究一般约瑟夫问题（每数到 k 淘汰一人）的规律。

步骤：

实现 J(n, k) 的递推求解：J(1, k) = 1，J(n, k) = (J(n-1, k) + k - 1) mod n + 1

计算并记录 J(n, k) 对于不同 n 和 k 的值

尝试发现 k = 3, 4, 5 时的规律

比较递推解法和模拟解法的效率

代码框架：

def josephus_general(n, k):
    """一般约瑟夫问题：每数到 k 淘汰一人"""
    if n == 1:
        return 1
    return (josephus_general(n-1, k) + k - 1) % n + 1

# 测试
for k in [2, 3, 4, 5]:
    print(f"k = {k}:")
    for n in range(1, 21):
        print(f"  J({n:2d}, {k}) = {josephus_general(n, k)}")
    print()

思考题：

• 对于 k = 3，是否存在类似 k = 2 的闭合形式？
• 当 n 很大时（如 n = 10^6），递推解法和模拟解法哪个更快？为什么？

七、本章小结

本章通过汉诺塔和约瑟夫两个经典问题，深入探讨了递归的核心思想。

关键公式：

• 汉诺塔：T(n) = 2T(n-1) + 1，闭合形式 T(n) = 2^n - 1
• 约瑟夫问题：J(2n) = 2J(n) - 1，J(2n+1) = 2J(n) + 1
• 约瑟夫闭合形式：若 n = 2^m + l（0 ≤ l < 2^m），则 J(n) = 2l + 1

核心思想：

递归分解：将大问题分解为相同结构的子问题

递推关系：用数学语言描述问题的自相似性

闭合形式：通过展开、归纳等方法求得简洁表达式

递归树：可视化工具帮助理解递归结构

最优性：证明解的下界，确保算法的最优性

定理总结：

• 汉诺塔的最少移动步数为 2^n - 1，且该下界是紧的
• 约瑟夫问题的幸存者编号可通过二进制左循环移位得到
• 每个递归算法都可以转换为等价的迭代算法

递归不仅是编程技巧，更是一种思维方式。掌握递归，你就掌握了分析复杂问题的利器。

八、习题

基础题

习题 1.1：计算 T(10) 和 T(20) 的值，验证 T(n) = 2^n - 1。

习题 1.2：手动模拟 n = 6 时的约瑟夫问题，列出每轮淘汰的顺序，验证 J(6) = 5。

习题 1.3：证明 J(n) 总是奇数。

习题 1.4：用数学归纳法证明：对于汉诺塔问题，任何合法策略至少需要 2^n - 1 步。

进阶题

习题 1.5：[ME] 考虑四柱汉诺塔问题（四根柱子而非三根）。设 F(n) 为移动 n 个盘子所需的最少步数。

• (a) 证明 F(n) ≤ 2F(n-2) + 3
• (b) 计算 F(1), F(2), F(3), F(4), F(5)
• (c) Frame-Stewart 猜想认为 F(n) = min_{1≤k<n}(2F(k) + 2^{n-k} - 1)。验证这个公式对 n ≤ 5 的结果。

习题 1.6：[ME] 修改约瑟夫问题：每数到 3 淘汰一人（而非 2）。设 J₃(n) 为 n 个人时的幸存者编号。

• (a) 推导 J₃(n) 的递推关系
• (b) 计算 J₃(1) 到 J₃(20)
• (c) 是否存在闭合形式？尝试寻找规律。

习题 1.7：考虑汉诺塔的受限版本：不允许直接从 A 移到 C，必须经过 B。设 R(n) 为最少步数。

• (a) 推导 R(n) 的递推关系
• (b) 求 R(n) 的闭合形式

挑战题

习题 1.8：[HM25] 证明约瑟夫问题的二进制左循环移位性质：J(n) 等于将 n 的二进制表示左循环移位一位。

习题 1.9：[HM30] 研究双参数约瑟夫问题 J(n, k)：n 个人围成一圈，每数到 k 淘汰一人。

• (a) 证明递推关系：J(1, k) = 1，J(n, k) = (J(n-1, k) + k - 1) mod n + 1
• (b) 对于固定的 k，J(n, k) 是否有闭合形式或高效计算方法？
• (c) 当 k = n 时，J(n, n) 是什么？这与什么著名问题相关？

习题 1.10：[HM40] 考虑广义汉诺塔问题：n 个盘子，m 根柱子（m ≥ 3）。

• (a) 对于 m = 4，证明或反驳 Frame-Stewart 猜想
• (b) 对于一般的 m，给出一个上界和下界
• (c) 当 m → ∞ 时，最少步数是多少？

本章完