程序员的数学（六）递归：自己定义自己的编程魔法

欢迎回到 “程序员的数学” 系列专栏。在前五篇内容里，我们从 “0 的占位” 讲到 “递归生成排列组合”—— 其实在生成排列组合时，我们已经悄悄用了递归的思路：比如 “从 5 个元素选 3 个的组合”，可以拆解成 “选第一个元素 + 从剩下 4 个选 2 个” 和 “不选第一个元素 + 从剩下 4 个选 3 个”，这本质就是 “用小问题的解构建大问题的解”。

今天我们就专门深入 “递归” 这个主题。递归看似 “绕”，但掌握后会发现它是解决复杂问题的 “捷径”—— 比如用 10 行代码实现汉诺塔，用递归公式直接生成帕斯卡三角形。更重要的是，递归的思维和之前学的数学归纳法一脉相承：数学归纳法是 “证明无穷”，递归是 “实现无穷”，两者都依赖 “基底 + 归纳” 的核心逻辑。

接下来，我们从 “直观例子” 到 “核心原理”，再到 “编程实战与优化”，把递归讲透，让你不仅会写递归代码，更能理解 “什么时候该用递归”“如何避免递归陷阱”。

一、递归的直观感受：从汉诺塔说起

要理解递归，最好的例子就是汉诺塔（Hanoi Tower） —— 这个由数学家卢卡斯发明的游戏，完美诠释了 “大问题拆解为小问题” 的递归思想。

1. 汉诺塔的规则（回顾）

有 3 根柱子（A、B、C），A 柱上套着 n 个大小不同的圆盘，按 “大在下、小在上” 叠放。需要把所有圆盘从 A 柱移到 B 柱，规则是：

• 每次只能移动最顶端的 1 个圆盘；
• 小圆盘上不能放大圆盘。

我们先从3 个圆盘的简单情况入手，看看移动步骤（图 1）：

1. 把 A 柱最上面 2 个圆盘移到 C 柱（借助 B 柱）；
2. 把 A 柱剩下的最大圆盘移到 B 柱；
3. 把 C 柱的 2 个圆盘移到 B 柱（借助 A 柱）。

总共需要 7 步。关键发现：步骤 1 和步骤 3 其实是 “2 个圆盘的汉诺塔”，而步骤 2 是 “1 个圆盘的汉诺塔”（直接移动）。

2. 从 3 个圆盘到 n 个圆盘：发现递归结构

如果把 “n 个圆盘的汉诺塔” 记为H(n)，那么：

• 要完成H(n)，需要先做H(n-1)：把上面 n-1 个圆盘从 A 移到 C（借助 B）；
• 然后移动第 n 个圆盘（最大的那个）：从 A 移到 B；
• 最后再做H(n-1)：把 C 上的 n-1 个圆盘移到 B（借助 A）。

这就是递归的核心：用 n-1 规模的问题解，构建 n 规模的问题解。而 “基底”（最小规模问题）是H(1)：只有 1 个圆盘时，直接从 A 移到 B，1 步完成。

用公式表示递归步骤：

plaintext

H(n) = （H(n-1)：A→C） + （移动1次：A→B） + （H(n-1)：C→B）

移动次数的递推公式也很容易推导：H(n) = 2*H(n-1) + 1，结合基底H(1)=1，最终解析式是H(n)=2ⁿ -1（比如 n=3 时，2³-1=7，和实际步骤一致）。

3. 汉诺塔的递归代码实现

递归的神奇之处在于：几行代码就能实现复杂的移动逻辑，无需手动写循环。我们用 Python 实现汉诺塔，函数参数hanoi(n, x, y, z)表示 “将 n 个圆盘从 x 柱，经 z 柱中转，移到 y 柱”：

python

def hanoi(n, x, y, z):
    """
    n: 圆盘数量
    x: 起点柱
    y: 目标柱
    z: 中转柱
    功能：打印n个圆盘从x到y的移动步骤
    """
    if n == 1:
        # 基底：1个圆盘，直接从x移到y
        print(f"{x}→{y}", end=" ")
        return
    # 步骤1：n-1个圆盘从x移到z（用y中转）
    hanoi(n-1, x, z, y)
    # 步骤2：第n个圆盘从x移到y
    print(f"{x}→{y}", end=" ")
    # 步骤3：n-1个圆盘从z移到y（用x中转）
    hanoi(n-1, z, y, x)

# 测试：3个圆盘从A到B，中转柱C
print("3个圆盘的移动步骤：")
hanoi(3, 'A', 'B', 'C')  # 输出：A→B A→C B→C A→B C→A C→B A→B 
# 验证移动次数：7次，正确

代码逻辑和我们手动分析的完全一致：基底处理 n=1，递归处理 n>1 时的三步。运行代码，会清晰打印出每一步的移动路径，这就是递归 “化繁为简” 的威力 —— 无需考虑 n=3 时的具体步骤，只需信任 n-1 的递归调用能完成任务。

二、递归的本质：自己定义自己（基底 + 归纳）

通过汉诺塔，我们能总结出递归的严格定义：递归是一种 “用同类小规模问题定义当前问题” 的方法，必须包含两个核心要素 —— 基底（最小规模问题的解）和归纳步骤（如何从小规模问题解构建当前问题解）。

这和之前学的数学归纳法高度呼应：

• 数学归纳法的 “基底”：验证 n=0 或 n=1 时成立；
• 数学归纳法的 “归纳步骤”：假设 n=k 成立，证明 n=k+1 成立；
• 递归的 “基底”：n=0 或 n=1 时的解；
• 递归的 “归纳步骤”：用 n-1 的解计算 n 的解。

可以说，数学归纳法是 “证明递归正确性的工具”，递归是 “实现数学归纳法思想的编程技巧”。

1. 阶乘的递归定义（重温）

之前在数学归纳法里证明过阶乘公式，现在用递归实现它。阶乘的递归定义：

• 基底：0! = 1（约定，确保递归终止）；
• 归纳步骤：对于 n≥1，n! = n × (n-1)!。

对应的递归代码：

python

def factorial(n):
    if n == 0:
        return 1  # 基底
    else:
        return n * factorial(n-1)  # 归纳步骤：用(n-1)!计算n!

# 测试：5! = 120，正确
print(factorial(5))  # 输出120

递归调用过程：factorial(5) =5*factorial(4) =5*4*factorial(3) =5*4*3*factorial(2) =5*4*3*2*factorial(1) =5*4*3*2*1*factorial(0) =5*4*3*2*1*1=120。每一步都拆解为更小的阶乘，直到基底factorial(0)=1，然后逐层返回计算结果。

2. 递归的核心要素：缺一不可

递归代码必须满足两个条件，否则会陷入 “无限递归”（导致栈溢出）：

1. 必须有基底：明确最小规模问题的解，让递归 “有终止的时候”；
   • 比如阶乘的基底是n=0，如果去掉if n==0，调用factorial(5)会一直递归到factorial(-1)、factorial(-2)… 直到栈溢出。
2. 归纳步骤必须缩小问题规模：确保每次递归调用的参数都比当前小，最终能到达基底；
   • 比如汉诺塔的hanoi(n-1, ...)，n 每次减 1，最终到n=1；如果写成hanoi(n+1, ...)，问题规模会越来越大，永远无法终止。

三、递归实战：从斐波那契到帕斯卡三角形

递归的应用远不止汉诺塔和阶乘，下面我们用两个经典案例，学习递归的实战技巧和优化方法。

1. 斐波那契数列（递归与优化）

斐波那契数列是 “兔子繁殖” 问题衍生的数列：0, 1, 1, 2, 3, 5, 8, 13…，递归定义为：

• 基底：F (0)=0，F (1)=1；
• 归纳步骤：F (n) = F (n-1) + F (n-2)（n≥2）。

（1）直接递归的问题：重复计算

直接按递归公式写代码，会发现计算 F (5) 时，需要计算 F (4) 和 F (3)；计算 F (4) 时，又需要计算 F (3) 和 F (2)——F (3) 被重复计算了两次。当 n=30 时，重复计算的次数会呈指数级增长，效率极低（时间复杂度 O (2ⁿ)）。

直接递归代码（效率低）：

python

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

# 计算F(30)需要几秒，F(40)需要更久
print(fib(30))  # 输出832040

（2）优化：记忆化缓存（避免重复计算）

解决重复计算的核心是 “把已经计算过的 F (n) 存起来，下次直接用”，这就是 “记忆化缓存”（Memoization）。我们用字典存储计算结果，时间复杂度可优化到 O (n)：

python

def fib_memo(n, memo=None):
    if memo is None:
        memo = {0: 0, 1: 1}  # 初始化基底，存储已计算的结果
    if n in memo:
        return memo[n]  # 已计算过，直接返回
    # 计算F(n)，并存入memo
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

# 计算F(100)也能瞬间完成
print(fib_memo(100))  # 输出354224848179261915075

Python 还提供了lru_cache装饰器，能自动实现记忆化，代码更简洁：

python

from functools import lru_cache

@lru_cache(maxsize=None)  # 无限缓存
def fib_lru(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib_lru(n-1) + fib_lru(n-2)

print(fib_lru(100))  # 输出354224848179261915075

2. 帕斯卡三角形（递归生成组合数）

帕斯卡三角形（杨辉三角）的每个数是组合数 C (n,k)（第 n 行第 k 列，从 0 开始），而组合数的递归公式我们之前学过：

• 基底：C (n,0)=1，C (n,n)=1（每行首尾都是 1）；
• 归纳步骤：C (n,k) = C (n-1,k-1) + C (n-1,k)（中间的数等于上一行左右两数之和）。

我们用递归生成帕斯卡三角形的前 n 行：

python

def pascal_triangle(n):
    """生成帕斯卡三角形的前n行（n≥1）"""
    if n == 1:
        return [[1]]  # 基底：第1行只有[1]
    # 递归生成前n-1行
    prev_rows = pascal_triangle(n-1)
    # 计算第n行：首尾是1，中间是上一行左右两数之和
    current_row = [1]  # 第n行第0列
    for k in range(1, n-1):
        # 第n行第k列 = 第n-1行第k-1列 + 第n-1行第k列
        current_row.append(prev_rows[-1][k-1] + prev_rows[-1][k])
    current_row.append(1)  # 第n行第n-1列
    return prev_rows + [current_row]

# 测试：生成前5行帕斯卡三角形
triangle = pascal_triangle(5)
for row in triangle:
    print(row)
# 输出：
# [1]
# [1, 1]
# [1, 2, 1]
# [1, 3, 3, 1]
# [1, 4, 6, 4, 1]

代码逻辑：先递归生成前 n-1 行，再基于前 n-1 行的最后一行，计算当前行的元素，最后拼接 —— 这体现了递归 “先解决小问题，再构建大问题” 的思路。

四、递归的陷阱与避坑指南

递归虽然简洁，但如果使用不当，很容易出现问题。我们总结几个常见陷阱及解决方案：

1. 陷阱 1：无限递归（栈溢出）

原因：缺少基底，或归纳步骤未缩小问题规模。例子：阶乘代码去掉if n==0，调用factorial(5)会一直递归到负整数，最终触发RecursionError（递归深度超过 Python 默认限制，默认约 1000）。解决方案：

• 必须明确基底，确保递归能终止；
• 检查归纳步骤，确保参数规模每次都缩小（如 n→n-1，而非 n→n+1）。

2. 陷阱 2：重复计算（效率低）

原因：递归过程中多次计算同一问题（如斐波那契的 F (3) 被计算多次）。解决方案：

• 记忆化缓存：用字典、列表或lru_cache存储已计算结果；
• 迭代转换：将递归改为循环（如斐波那契用循环计算，从 F (0) 和 F (1) 逐步算到 F (n)）。

3. 陷阱 3：递归深度过大（栈溢出）

原因：Python 默认递归深度有限（约 1000），当 n 超过 1000 时，如factorial(2000)，会触发栈溢出。解决方案：

• 迭代转换：将递归改为循环（如阶乘用循环result *= i从 1 算到 n）；
• 手动设置递归深度（谨慎使用）：用sys.setrecursionlimit(10000)增大限制，但不推荐（可能导致内存问题）。

递归转迭代示例：阶乘的循环实现

python

def factorial_iter(n):
    result = 1
    for i in range(1, n+1):
        result *= i
    return result

print(factorial_iter(2000))  # 输出极大的数，无栈溢出

五、递归与编程：应用场景与思维价值

递归不仅是一种编程技巧，更是一种 “拆解问题的思维方式”，在编程中应用广泛：

1. 递归的典型应用场景

• 树形结构处理：如文件系统遍历（文件夹里有子文件夹，子文件夹里又有文件，结构递归）、二叉树的遍历（前序 / 中序 / 后序遍历，递归代码比循环简洁）；
• 分治算法：如快速排序（将数组分成左右两部分，递归排序每部分）、归并排序（递归合并两个有序数组）；
• 动态规划基础：如斐波那契的记忆化、最长公共子序列（用递归 + 记忆化存储中间结果）。

示例：递归遍历文件夹

python

import os

def traverse_folder(path):
    """递归遍历文件夹，打印所有文件路径"""
    # 遍历当前路径下的所有文件和文件夹
    for name in os.listdir(path):
        full_path = os.path.join(path, name)
        if os.path.isfile(full_path):
            # 基底：是文件，直接打印
            print(f"文件：{full_path}")
        else:
            # 归纳步骤：是文件夹，递归遍历
            print(f"文件夹：{full_path}")
            traverse_folder(full_path)

# 测试：遍历当前目录
traverse_folder(".")

2. 递归的思维价值：化繁为简

递归的核心思维是 “信任递归”—— 不用纠结 n=5 时的具体步骤，只需确保：

• 基底正确（n=1 时能解决）；
• 能把 n 的问题拆解为 n-1 的问题（且 n-1 的问题能解决）。

这种思维能帮我们跳出 “细节陷阱”，比如汉诺塔不用手动想 n=100 的步骤，只需信任 n=99 的递归调用能完成任务 —— 这和之前数学归纳法 “信任 n=k 成立，证明 n=k+1 成立” 的思想完全一致。

六、小结：递归是 “数学归纳法” 的编程实现

今天我们深入学习了递归，核心收获可以总结为：

1. 递归与数学归纳法的联系：基底对应数学归纳法的 “基础验证”，归纳步骤对应 “归纳推理”，两者都用 “小规模问题” 解决 “大规模问题”；
2. 递归的核心要素：必须有基底（终止条件）和缩小规模的归纳步骤，缺一不可；
3. 递归的实战技巧：遇到重复计算用记忆化优化，遇到深度过大转迭代，复杂结构（如树形）优先用递归；
4. 递归的应用场景：树形结构、分治算法、动态规划，递归代码往往比循环更简洁易懂。

递归是之前数学归纳法的 “落地工具”，而接下来我们要学习的 “指数爆炸”，会解释递归中 “重复计算导致效率低” 的本质（如斐波那契的 O (2ⁿ) 复杂度），同时也会讲如何利用指数爆炸（如二分查找）—— 递归和指数爆炸的结合，会让我们更深入理解算法效率的重要性。

如果你在编程中用递归解决过有趣的问题（比如遍历复杂数据结构、实现算法），欢迎在评论区分享你的经历！