第5章归纳与递归 (Induction and Recursion)

一、导读

1.1 本章学习目标

完成本章学习后，你将能够：

理解数学归纳法的原理和证明步骤，能够熟练运用直接归纳法证明命题

掌握强归纳法（完全归纳法）及其适用场景

理解结构归纳法在递归定义数据结构上的应用

掌握递归函数的设计原则：基础情况、递归进展、子问题收敛

能够将递归算法转换为迭代形式，理解两者之间的等价性

掌握递推关系的建立和求解方法，包括特征方程法

理解递归在分治算法中的应用，分析归并排序和快速排序

识别和避免递归中的常见陷阱：无限递归、重复计算、栈溢出

1.2 为什么本章如此重要

归纳和递归是计算机科学中最核心的思维模式之一。

在程序设计中：递归是处理树形结构、图遍历、动态规划等问题的自然方式。许多优雅算法（如归并排序、快速排序、二分搜索）都基于递归思想。

在数据结构中：链表、树、图等递归定义的数据结构天然适合递归处理。理解结构归纳法有助于证明这些数据结构操作的正确性。

在算法分析中：递归算法的时间复杂度由递推关系描述。掌握递推关系求解方法是分析递归算法效率的关键。

在形式化验证中：归纳法是证明程序正确性的基本工具。循环不变式本质上是归纳假设，循环终止性证明类似于归纳的基础步骤和归纳步骤。

在函数式编程中：递归是主要的控制流机制（因为没有可变状态和循环）。Haskell、Scala等语言广泛使用递归和模式匹配。

在人工智能中：递归下降解析器用于自然语言处理；递归神经网络（RNN）处理序列数据。

1.3 核心问题引导

在学习本章之前，请思考以下问题：

数学归纳法为什么能保证命题对所有自然数成立？它的直观意义是什么？

递归函数必须有基础情况吗？如果没有会发生什么？

所有递归算法都能转换为迭代吗？反过来呢？

为什么有些递归算法效率低下（如朴素斐波那契）？如何优化？

什么是"尾递归"？为什么尾递归可以被优化为迭代？

结构归纳法和数学归纳法有什么区别和联系？

递推关系 T(n) = 2T(n/2) + n 的解是什么？它对应哪个算法？

递归深度受什么限制？如何避免栈溢出？

二、核心概念详解

5.1 数学归纳法

原理与直觉

数学归纳法是证明关于自然数命题的方法。它的逻辑基础是皮亚诺公理系统中的归纳公理。

归纳公理：如果S是自然数集的子集，满足：

0 ∈ S（或1 ∈ S，取决于定义）

如果 k ∈ S，则 k+1 ∈ S

那么 S = ℕ（所有自然数都在S中）。

直观解释：这就像多米诺骨牌。如果你能推倒第一块（基础步骤），且每一块倒下都会导致下一块倒下（归纳步骤），那么所有骨牌都会倒下。

标准归纳法

证明框架：

要证明命题 P(n) 对所有 n ≥ n₀ 成立：

基础步骤：证明 P(n₀) 成立

归纳步骤：假设 P(k) 成立（归纳假设），证明 P(k+1) 成立

示例1：证明 1 + 2 + 3 + ... + n = n(n+1)/2

证明：

基础步骤：n=1时，左边=1，右边=1×2/2=1。成立。

归纳步骤：假设对n=k成立，即 1+2+...+k = k(k+1)/2。

考虑n=k+1：

$$1 + 2 + ... + k + (k+1) = \frac{k(k+1)}{2} + (k+1)$$

$$= \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}$$

这正是公式对n=k+1的形式。因此由归纳法，命题对所有正整数n成立。∎

示例2：证明 2ⁿ > n 对所有 n ≥ 1 成立

证明：

基础步骤：n=1时，2¹ = 2 > 1。成立。

归纳步骤：假设 2ᵏ > k。

考虑n=k+1：

$$2^{k+1} = 2 \cdot 2^k > 2k$$

需要证明 2k ≥ k+1，即 k ≥ 1，这在归纳范围内成立。

所以 2^(k+1) > 2k ≥ k+1，即 2^(k+1) > k+1。∎

强归纳法（完全归纳法）

强归纳法的归纳假设更强：假设命题对所有 n₀ ≤ m ≤ k 都成立，而不仅仅是对k成立。

证明框架：

基础步骤：证明 P(n₀) 成立

归纳步骤：假设 P(n₀), P(n₀+1), ..., P(k) 都成立，证明 P(k+1) 成立

何时使用强归纳法：当证明 P(k+1) 需要用到不止 P(k)，还需要更早的情况时。

示例：证明每个大于1的整数都可以分解为素数的乘积。

证明：

基础步骤：n=2是素数，本身就是素数乘积。

归纳步骤：假设所有满足 2 ≤ m ≤ k 的整数m都可以分解为素数乘积。

考虑n=k+1：

如果k+1是素数，则它本身就是素数乘积。
如果k+1是合数，则存在 a, b 使得 k+1 = a × b，其中 2 ≤ a, b ≤ k。

由归纳假设，a和b都可以分解为素数乘积，因此k+1也可以。

由强归纳法，命题成立。∎

5.2 递归定义与结构归纳法

递归定义

递归定义通过以下方式定义对象：

基础情况：明确指定一些基本对象

递归规则：说明如何从已有对象构造新对象

极小性：只有通过有限次应用上述规则得到的对象才属于该集合

示例1：自然数的递归定义

基础：0是自然数
递归：如果n是自然数，则n+1是自然数
极小性：只有通过有限次应用上述规则得到的才是自然数

示例2：二叉树的递归定义

基础：空树是二叉树
递归：如果L和R是二叉树，则创建一个新节点，以L为左子树、R为右子树，构成新的二叉树

结构归纳法

结构归纳法用于证明递归定义结构上的命题。

证明框架：

要证明命题 P(x) 对递归定义结构中的所有x成立：

基础情况：证明P对所有基础对象成立

归纳步骤：假设P对构造规则中的子对象成立，证明P对新构造的对象也成立

示例：证明二叉树中叶节点数 = 内部节点数 + 1（对于满二叉树）

证明：

设 L(T) 为树T的叶节点数，I(T) 为内部节点数。

基础情况：空树。L=0, I=0。但空树不是满二叉树，考虑单节点树：L=1, I=0。1 = 0 + 1。成立。

归纳步骤：假设对左子树L和右子树R，有 L(L) = I(L) + 1 和 L(R) = I(R) + 1。

对于由L和R构成的新树T：

L(T) = L(L) + L(R)
I(T) = I(L) + I(R) + 1（加1是因为根节点成为内部节点）

需要证明 L(T) = I(T) + 1：

L(T) = L(L) + L(R)

= (I(L) + 1) + (I(R) + 1) （由归纳假设）

= I(L) + I(R) + 2

= (I(L) + I(R) + 1) + 1

= I(T) + 1

因此命题成立。∎

5.3 递归函数设计

递归三要素

设计递归函数时必须确保：

基础情况（Base Case）：至少有一个不需要递归就能直接求解的情况

递归进展（Progress）：每次递归调用必须使问题规模减小

子问题收敛（Convergence）：问题规模最终会达到基础情况

违反任一要素会导致无限递归！

经典递归示例

阶乘：

python

def factorial(n):
    if n == 0:          # 基础情况
        return 1
    return n * factorial(n - 1)  # 递归：问题规模减小

斐波那契数列：

python

def fibonacci(n):
    if n <= 1:          # 基础情况
        return n
    return fibonacci(n-1) + fibonacci(n-2)  # 两个递归调用

二分搜索：

python

def binary_search(arr, target, left, right):
    if left > right:    # 基础情况：未找到
        return -1
    
    mid = (left + right) // 2
    if arr[mid] == target:   # 基础情况：找到
        return mid
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, right)  # 搜索右半部分
    else:
        return binary_search(arr, target, left, mid - 1)   # 搜索左半部分

尾递归

尾递归：递归调用是函数的最后一个操作。

python

# 非尾递归
def factorial_non_tail(n):
    if n == 0:
        return 1
    return n * factorial_non_tail(n - 1)  # 乘法在递归调用之后

# 尾递归
def factorial_tail(n, accumulator=1):
    if n == 0:
        return accumulator
    return factorial_tail(n - 1, n * accumulator)  # 递归调用是最后操作

尾递归优化：某些编译器/解释器可以将尾递归转换为迭代，避免栈增长。Python不支持此优化，但Scheme、Scala等支持。

5.4 递推关系

定义

递推关系将序列的第n项表示为前面若干项的函数。

一般形式：aₙ = f(aₙ₋₁, aₙ₋₂, ..., aₙ₋ₖ)

需要k个初始条件：a₀, a₁, ..., aₖ₋₁

线性齐次递推关系

形式：aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + ... + cₖaₙ₋ₖ

其中cᵢ是常数，cₖ ≠ 0。

求解方法：特征方程法

写出特征方程：rᵏ - c₁rᵏ⁻¹ - c₂rᵏ⁻² - ... - cₖ = 0

求特征根

根据根的情况写出通解

情况1：k个不同实根 r₁, r₂, ..., rₖ

通解：aₙ = α₁r₁ⁿ + α₂r₂ⁿ + ... + αₖrₖⁿ

情况2：重根

如果r是m重根，则对应项为 (α₁ + α₂n + ... + αₘnᵐ⁻¹)rⁿ

示例：斐波那契数列

Fₙ = Fₙ₋₁ + Fₙ₋₂，F₀ = 0, F₁ = 1

特征方程：r² - r - 1 = 0

特征根：$r_1 = \frac{1+\sqrt{5}}{2}$（黄金比例φ），$r_2 = \frac{1-\sqrt{5}}{2}$

通解：$F_n = \alpha_1 r_1^n + \alpha_2 r_2^n$

代入初始条件求得：

$$F_n = \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right]$$

这就是比内公式（Binet's Formula）。

分治递推关系

形式：T(n) = aT(n/b) + f(n)

这类递推关系常用主定理（Master Theorem）求解。

主定理：对于 T(n) = aT(n/b) + O(nᵈ)，其中 a ≥ 1, b > 1：

令 $c = \log_b a$

如果 d < c，则 T(n) = Θ(nᶜ)
如果 d = c，则 T(n) = Θ(nᶜ log n)
如果 d > c，则 T(n) = Θ(nᵈ)

应用：

归并排序：T(n) = 2T(n/2) + O(n)，a=2, b=2, d=1, c=log₂2=1=d，所以 T(n) = Θ(n log n)
二分搜索：T(n) = T(n/2) + O(1)，a=1, b=2, d=0, c=log₂1=0=d，所以 T(n) = Θ(log n)

5.5 递归与迭代的转换

递归转迭代

任何递归算法都可以转换为迭代算法，通常需要使用显式栈来模拟递归调用栈。

示例：阶乘

python

# 递归
def factorial_recursive(n):
    if n == 0:
        return 1
    return n * factorial_recursive(n - 1)

# 迭代
def factorial_iterative(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

示例：树的前序遍历

python

# 递归
def preorder_recursive(node):
    if node is None:
        return
    visit(node)
    preorder_recursive(node.left)
    preorder_recursive(node.right)

# 迭代（使用显式栈）
def preorder_iterative(root):
    if root is None:
        return
    stack = [root]
    while stack:
        node = stack.pop()
        visit(node)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

迭代转递归

某些迭代算法用递归表达更清晰，特别是涉及分治或回溯时。

5.6 记忆化与动态规划

重复子问题

朴素递归可能重复计算相同的子问题，导致指数级时间复杂度。

示例：朴素斐波那契

fibonacci(5)
├── fibonacci(4)
│   ├── fibonacci(3)
│   │   ├── fibonacci(2)
│   │   │   ├── fibonacci(1)
│   │   │   └── fibonacci(0)
│   │   └── fibonacci(1)
│   └── fibonacci(2)  ← 重复计算！
│       ├── fibonacci(1)
│       └── fibonacci(0)
└── fibonacci(3)  ← 重复计算！
    ├── fibonacci(2)
    │   ├── fibonacci(1)
    │   └── fibonacci(0)
    └── fibonacci(1)

fibonacci(3) 被计算了2次，fibonacci(2) 被计算了3次。

记忆化（自顶向下）

存储已计算的子问题结果，避免重复计算。

python

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_memo(n):
    if n <= 1:
        return n
    return fibonacci_memo(n-1) + fibonacci_memo(n-2)

时间复杂度从 O(2ⁿ) 降低到 O(n)。

动态规划（自底向上）

先解决小问题，再逐步构建大问题的解。

python

def fibonacci_dp(n):
    if n <= 1:
        return n
    
    dp = [0] * (n + 1)
    dp[1] = 1
    
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]

空间优化版本：

python

def fibonacci_optimized(n):
    if n <= 1:
        return n
    
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    
    return curr

三、程序员的视角

3.1 在计算机科学中的应用

分治算法

归并排序：T(n) = 2T(n/2) + O(n)
快速排序：平均 T(n) = 2T(n/2) + O(n)
二分搜索：T(n) = T(n/2) + O(1)
Strassen矩阵乘法：T(n) = 7T(n/2) + O(n²)

树形结构处理

文件系统遍历：目录树是递归结构
XML/JSON解析：嵌套结构天然适合递归
决策树：机器学习中的分类模型

回溯算法

N皇后问题：尝试放置皇后，冲突时回溯
数独求解：填入数字，矛盾时回溯
图的着色：尝试颜色，冲突时回溯

动态规划

最短路径（Floyd-Warshall）
最长公共子序列
背包问题
编辑距离

3.2 常见陷阱与误区

缺少基础情况

python

# 错误：无限递归
def factorial(n):
    return n * factorial(n - 1)  # 没有基础情况！

递归不收敛

python

# 错误：问题规模没有减小
def bad_recursion(n):
    if n == 0:
        return 1
    return bad_recursion(n)  # 参数没变！

重复计算

python

# 低效：指数时间
def fibonacci_naive(n):
    if n <= 1:
        return n
    return fibonacci_naive(n-1) + fibonacci_naive(n-2)

栈溢出

递归深度过大可能导致栈溢出。Python默认递归限制约1000层。

python

import sys
sys.setrecursionlimit(10000)  # 增加限制（谨慎使用）

3.3 与其他层级的联系

硬件层：递归调用使用调用栈，存储在内存中
操作系统层：栈空间有限，深递归可能导致段错误
编译器层：尾递归优化将递归转换为跳转
应用层：递归下降解析器用于编译器和解释器

四、代码实战

4.1 数学归纳法验证工具

python

"""
数学归纳法验证工具：帮助理解和验证归纳证明
"""


def verify_sum_formula(max_n=100):
    """
    验证求和公式：1 + 2 + ... + n = n(n+1)/2
    """
    print("验证求和公式: 1 + 2 + ... + n = n(n+1)/2")
    print("-" * 50)
    
    for n in range(1, max_n + 1):
        lhs = sum(range(1, n + 1))
        rhs = n * (n + 1) // 2
        
        if lhs != rhs:
            print(f"公式在 n={n} 时失败！")
            return False
    
    print(f"公式对 1 到 {max_n} 的所有值都成立！")
    return True


def verify_induction_step(formula_func, k):
    """
    演示归纳步骤
    
    参数:
        formula_func: 公式函数，输入n返回理论值
        k: 当前归纳假设的值
    """
    # 计算前k项的和
    actual_sum = sum(formula_func(i) for i in range(1, k + 1))
    formula_at_k = formula_func(k)
    
    # 计算前k+1项的和
    actual_sum_next = actual_sum + formula_func(k + 1)
    formula_at_k_plus_1 = formula_func(k + 1)
    
    print(f"归纳步骤验证 (k={k}):")
    print(f"  前{k}项和: {actual_sum}")
    print(f"  第{k+1}项: {formula_at_k_plus_1}")
    print(f"  前{k+1}项和: {actual_sum_next}")
    

def demonstrate_geometric_series():
    """演示几何级数求和"""
    
    print("\n几何级数: 1 + r + r² + ... + rⁿ = (r^(n+1) - 1)/(r - 1)")
    print("-" * 50)
    
    r = 2
    for n in [5, 10, 15]:
        lhs = sum(r ** i for i in range(n + 1))
        rhs = (r ** (n + 1) - 1) // (r - 1)
        
        print(f"n={n}: 左边={lhs}, 右边={rhs}, 相等={lhs == rhs}")


if __name__ == "__main__":
    verify_sum_formula(1000)
    demonstrate_geometric_series()

4.2 递归算法集合

python

"""
经典递归算法实现
"""

from functools import lru_cache


# --- 阶乘 ---

def factorial(n):
    """计算n的阶乘"""
    if n < 0:
        raise ValueError("阶乘未定义于负数")
    if n == 0:
        return 1
    return n * factorial(n - 1)


# --- 斐波那契数列 ---

@lru_cache(maxsize=None)
def fibonacci(n):
    """计算第n个斐波那契数（记忆化版本）"""
    if n < 0:
        raise ValueError("斐波那契数未定义于负数")
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)


def fibonacci_iterative(n):
    """斐波那契数列的迭代实现"""
    if n <= 1:
        return n
    
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    
    return curr


# --- 汉诺塔 ---

def hanoi(n, source='A', target='C', auxiliary='B'):
    """
    汉诺塔问题
    
    参数:
        n: 盘子数量
        source: 源柱
        target: 目标柱
        auxiliary: 辅助柱
    
    返回: 移动步骤列表
    """
    if n <= 0:
        return []
    
    moves = []
    
    # 将n-1个盘子从source移到auxiliary
    moves.extend(hanoi(n - 1, source, auxiliary, target))
    
    # 将最大盘子从source移到target
    moves.append(f"移动盘子 {n} 从 {source} 到 {target}")
    
    # 将n-1个盘子从auxiliary移到target
    moves.extend(hanoi(n - 1, auxiliary, target, source))
    
    return moves


# --- 幂集生成 ---

def powerset(items):
    """
    生成集合的幂集（所有子集）
    
    返回: 所有子集的列表
    """
    if not items:
        return [[]]
    
    first = items[0]
    rest = items[1:]
    
    # 不包含first的子集
    without_first = powerset(rest)
    
    # 包含first的子集
    with_first = [[first] + subset for subset in without_first]
    
    return without_first + with_first


# --- 排列组合 ---

def permutations(items):
    """生成所有排列"""
    if len(items) <= 1:
        return [items[:]]
    
    result = []
    for i, item in enumerate(items):
        remaining = items[:i] + items[i+1:]
        for perm in permutations(remaining):
            result.append([item] + perm)
    
    return result


def combinations(items, k):
    """
    生成所有k元素组合
    
    参数:
        items: 元素列表
        k: 组合大小
    
    返回: 所有k元素组合的列表
    """
    if k == 0:
        return [[]]
    if not items or k > len(items):
        return []
    
    first = items[0]
    rest = items[1:]
    
    # 包含first的组合
    with_first = [[first] + comb for comb in combinations(rest, k - 1)]
    
    # 不包含first的组合
    without_first = combinations(rest, k)
    
    return with_first + without_first


def demonstrate_recursion():
    """演示各种递归算法"""
    
    print("=== 阶乘 ===")
    for n in range(6):
        print(f"  {n}! = {factorial(n)}")
    
    print("\n=== 斐波那契数列 ===")
    for n in range(11):
        print(f"  F({n}) = {fibonacci(n)}")
    
    print("\n=== 汉诺塔 (3个盘子) ===")
    moves = hanoi(3)
    for i, move in enumerate(moves, 1):
        print(f"  {i}. {move}")
    print(f"  总步数: {len(moves)} (公式: 2ⁿ-1 = {2**3-1})")
    
    print("\n=== 幂集 ===")
    items = [1, 2, 3]
    subsets = powerset(items)
    print(f"  集合 {items} 的幂集:")
    for subset in subsets:
        print(f"    {subset}")
    print(f"  子集总数: {len(subsets)} (公式: 2ⁿ = {2**len(items)})")
    
    print("\n=== 排列 ===")
    items = [1, 2, 3]
    perms = permutations(items)
    print(f"  {items} 的所有排列:")
    for perm in perms:
        print(f"    {perm}")
    print(f"  排列总数: {len(perms)} (公式: n! = {factorial(len(items))})")
    
    print("\n=== 组合 ===")
    items = [1, 2, 3, 4]
    k = 2
    combs = combinations(items, k)
    print(f"  从 {items} 中选 {k} 个的组合:")
    for comb in combs:
        print(f"    {comb}")
    print(f"  组合总数: C({len(items)},{k}) = {len(combs)}")


if __name__ == "__main__":
    demonstrate_recursion()

4.3 动态规划示例

python

"""
动态规划经典问题
"""


def coin_change(coins, amount):
    """
    硬币找零问题：最少硬币数
    
    参数:
        coins: 可用硬币面额列表
        amount: 目标金额
    
    返回: 最少硬币数，无法找零返回-1
    """
    # dp[i] 表示凑成金额i所需的最少硬币数
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    
    for i in range(1, amount + 1):
        for coin in coins:
            if i >= coin and dp[i - coin] != float('inf'):
                dp[i] = min(dp[i], dp[i - coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1


def longest_common_subsequence(s1, s2):
    """
    最长公共子序列（LCS）
    
    参数:
        s1, s2: 两个序列（字符串或列表）
    
    返回: LCS的长度和具体序列
    """
    m, n = len(s1), len(s2)
    
    # dp[i][j] 表示 s1[:i] 和 s2[:j] 的LCS长度
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    # 回溯找出LCS
    lcs = []
    i, j = m, n
    while i > 0 and j > 0:
        if s1[i-1] == s2[j-1]:
            lcs.append(s1[i-1])
            i -= 1
            j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    
    lcs.reverse()
    
    return dp[m][n], ''.join(lcs) if isinstance(s1, str) else lcs


def edit_distance(s1, s2):
    """
    编辑距离（Levenshtein距离）
    
    参数:
        s1, s2: 两个字符串
    
    返回: 将s1转换为s2所需的最少编辑操作数
    """
    m, n = len(s1), len(s2)
    
    # dp[i][j] 表示 s1[:i] 和 s2[:j] 的编辑距离
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # 初始化
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(
                    dp[i-1][j],      # 删除
                    dp[i][j-1],      # 插入
                    dp[i-1][j-1]     # 替换
                )
    
    return dp[m][n]


def knapsack(weights, values, capacity):
    """
    0-1背包问题
    
    参数:
        weights: 物品重量列表
        values: 物品价值列表
        capacity: 背包容量
    
    返回: 最大价值
    """
    n = len(weights)
    
    # dp[i][w] 表示前i个物品、容量w时的最大价值
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            # 不选第i个物品
            dp[i][w] = dp[i-1][w]
            
            # 选第i个物品（如果放得下）
            if w >= weights[i-1]:
                dp[i][w] = max(dp[i][w], dp[i-1][w-weights[i-1]] + values[i-1])
    
    return dp[n][capacity]


def demonstrate_dp():
    """演示动态规划问题"""
    
    print("=== 硬币找零 ===")
    coins = [1, 5, 10, 25]
    amount = 63
    min_coins = coin_change(coins, amount)
    print(f"  硬币面额: {coins}")
    print(f"  目标金额: {amount}")
    print(f"  最少硬币数: {min_coins}")
    
    print("\n=== 最长公共子序列 ===")
    s1 = "ABCBDAB"
    s2 = "BDCABA"
    length, lcs = longest_common_subsequence(s1, s2)
    print(f"  s1 = '{s1}'")
    print(f"  s2 = '{s2}'")
    print(f"  LCS长度: {length}")
    print(f"  LCS: '{lcs}'")
    
    print("\n=== 编辑距离 ===")
    s1 = "kitten"
    s2 = "sitting"
    distance = edit_distance(s1, s2)
    print(f"  '{s1}' -> '{s2}'")
    print(f"  编辑距离: {distance}")
    
    print("\n=== 背包问题 ===")
    weights = [2, 3, 4, 5]
    values = [3, 4, 5, 6]
    capacity = 8
    max_value = knapsack(weights, values, capacity)
    print(f"  重量: {weights}")
    print(f"  价值: {values}")
    print(f"  容量: {capacity}")
    print(f"  最大价值: {max_value}")


if __name__ == "__main__":
    demonstrate_dp()

五、深入思考

5.1 历史背景

数学归纳法的使用可以追溯到帕斯卡（1654年），但直到19世纪才被严格形式化。朱塞佩·皮亚诺（1889年）的公理系统将归纳法作为自然数的基本性质。

递归在语言学中由诺姆·乔姆斯基强调，他认为递归是人类语言的核心特征。在计算机科学中，约翰·麦卡锡在Lisp语言中展示了递归的强大表达能力。

5.2 前沿方向

递归类型理论：在依赖类型系统中处理递归
共递归（Corecursion）：处理无限数据结构的对偶概念
自动归纳定理证明：使用机器学习辅助寻找归纳假设
并行递归算法：利用多核加速递归计算

5.3 延伸阅读

《Concrete Mathematics》by Graham, Knuth, Patashnik
《The Art of Computer Programming, Vol. 1》by Donald E. Knuth
《Introduction to Algorithms》by CLRS, Chapter 4

六、实验笔记

实验1：递归可视化

目标：创建递归执行过程的可视化工具。

任务：

选择一个递归算法（如汉诺塔、归并排序）

记录每次递归调用的参数和返回值

绘制递归树，标注每层的计算

显示记忆化的效果（哪些子问题被跳过）

比较不同输入规模下的递归深度和调用次数

提交物：可运行的可视化程序、示例输出。

实验2：递推关系求解器

目标：实现一个能够求解线性齐次递推关系的程序。

任务：

输入递推关系系数和初始条件

求解特征方程（数值方法）

计算通解中的待定系数

验证解的正确性

（进阶）处理重根和复根情况

提交物：源代码、测试用例、验证报告。

七、本章小结

本章介绍了归纳法和递归这两个紧密相关的概念。数学归纳法是证明关于自然数命题的有力工具，包括标准归纳法和强归纳法两种形式。结构归纳法将归纳思想扩展到递归定义的数据结构上。

递归是函数调用自身的编程技巧，设计递归函数需要确保基础情况、递归进展和子问题收敛三个要素。尾递归是一种特殊形式，可以被优化为迭代以避免栈溢出。

递推关系描述了递归算法的时间复杂度，线性齐次递推关系可以通过特征方程法求解。分治递推关系常用主定理分析。

记忆化和动态规划是优化递归算法的两种技术，前者自顶向下存储子问题解，后者自底向上构建解。两者都能将指数时间算法优化为多项式时间。

理解归纳和递归不仅有助于算法设计和分析，也是培养计算思维的关键。

八、习题

习题1（基础）：用数学归纳法证明：

(a) 1 + 3 + 5 + ... + (2n-1) = n²

(b) 2ⁿ > n² 对所有 n ≥ 5 成立

习题2（基础）：写出下列递归函数的基础情况和递归步骤：

(a) def f(n): return 1 if n == 0 else n + f(n-1)

(b) def g(n): return n if n < 2 else g(n-1) + g(n-2)

习题3（中等）：求解递推关系 aₙ = 3aₙ₋₁ - 2aₙ₋₂，a₀ = 1, a₁ = 3。

习题4（中等）：使用主定理求解下列递推关系：

(a) T(n) = 4T(n/2) + n

(b) T(n) = 2T(n/2) + n/log n

习题5（中等）：实现递归的二叉树遍历（前序、中序、后序），并转换为迭代版本。

习题6（较难）：用强归纳法证明：任何大于等于2的整数都可以表示为素数的乘积。

习题7（较难）：分析递归实现的阿克曼函数 A(m, n) 的增长率，为什么它增长如此之快？

习题8（挑战）：设计并实现一个通用的记忆化装饰器，能够缓存任意函数的结果。

习题9（挑战）：研究并实现Cooley-Tukey快速傅里叶变换（FFT）算法，分析其递推关系。

习题10（开放）：选择一个你感兴趣的递归问题（如分形生成、迷宫求解等），实现并撰写报告，包括算法思路、复杂度分析和优化方法。

第5章 归纳与递归 (Induction and Recursion)

一、导读

1.1 本章学习目标

1.2 为什么本章如此重要

1.3 核心问题引导

二、核心概念详解

5.1 数学归纳法

原理与直觉

标准归纳法

强归纳法（完全归纳法）

5.2 递归定义与结构归纳法

递归定义

结构归纳法

5.3 递归函数设计

递归三要素

经典递归示例

尾递归

5.4 递推关系

定义

线性齐次递推关系

分治递推关系

5.5 递归与迭代的转换

递归转迭代

迭代转递归

5.6 记忆化与动态规划

重复子问题

记忆化（自顶向下）

动态规划（自底向上）

三、程序员的视角

3.1 在计算机科学中的应用

分治算法

树形结构处理

回溯算法

动态规划

3.2 常见陷阱与误区

缺少基础情况

递归不收敛

重复计算

栈溢出

3.3 与其他层级的联系

四、代码实战

4.1 数学归纳法验证工具

4.2 递归算法集合

4.3 动态规划示例

五、深入思考

5.1 历史背景

5.2 前沿方向

5.3 延伸阅读

六、实验笔记

实验1：递归可视化

实验2：递推关系求解器

七、本章小结

八、习题

第5章归纳与递归 (Induction and Recursion)