前言

递归是计算机科学中一种强大而优雅的编程范式，其核心思想是“将大问题分解为结构相同的小问题”，直到达到一个可以直接求解的基础情况（Base Case）。递归不仅广泛应用于数学计算、数据结构遍历，更是理解分治、动态规划等高级算法的基础。

本文将以《Python常用算法手册》中的7个经典算法演练为例，深入剖析递归的思想本质，并通过Python代码实现，帮助读者从理论走向实践。每个案例均包含详细分析、可视化图表或表格、完整可运行代码及注释，适合初学者与进阶者共同学习。

一、斐波那契数列 —— 递归的经典入门

算法分析

斐波那契数列定义为：

• F₀ = 1
• F₁ = 1
• Fₙ = Fₙ₋₂ + Fₙ₋₁ （n ≥ 2）

该数列源于兔子繁殖模型：每对兔子出生后两个月开始繁殖，每月生一对新兔，且永不死亡。由此推导出每月兔子对数满足递推关系。

表3-1 月数与对数关系表

规律总结：当前月兔子总数 = 上月总数 + 上上月总数
即：Fₙ = Fₙ₋₁ + Fₙ₋₂

实现思路

使用递归函数直接映射数学定义：

• 基础情况：n=0 或 n=1 时返回 1
• 递归情况：返回 fib(n-1) + fib(n-2)

⚠️ 注意：朴素递归效率低（指数级），实际应用中建议用记忆化或迭代优化。

代码实现

# 文件名: fibonacci.py

def fibonacci(n):
    """
    递归计算第n个月的兔子对数（斐波那契数列）
    :param n: 月份（非负整数）
    :return: 第n个月的兔子对数
    """
    if n == 0 or n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

# 演示前10个月的结果
if __name__ == "__main__":
    print("月份\t兔子对数")
    for i in range(1, 11):
        print(f"{i}\t{fibonacci(i)}")

二、汉诺塔问题 —— 递归的分治典范

算法分析

汉诺塔问题要求将n个盘子从A柱移动到C柱，借助B柱，规则：

1. 每次只能移动一个盘子；
2. 大盘不能压在小盘上。

解题策略（递归三步法）：

设 move(n, source, target, auxiliary) 表示将n个盘子从source移到target，auxiliary为辅助柱：

1. 将前n-1个盘子从source → auxiliary（借助target）
2. 将第n个盘子从source → target
3. 将n-1个盘子从auxiliary → target（借助source）

示意图（以n=3为例）：

初始状态:
A: [3,2,1]   B: []      C: []

步骤1: 移动1→C
A: [3,2]     B: []      C: [1]

步骤2: 移动2→B
A: [3]       B: [2]     C: [1]

步骤3: 移动1→B
A: [3]       B: [2,1]   C: []

步骤4: 移动3→C
A: []        B: [2,1]   C: [3]

步骤5: 移动1→A
A: [1]       B: [2]     C: [3]

步骤6: 移动2→C
A: [1]       B: []      C: [3,2]

步骤7: 移动1→C
A: []        B: []      C: [3,2,1] ✅

实现思路

递归函数接收四个参数：盘子数量、源柱、目标柱、辅助柱。每次调用自身处理子问题。

代码实现

# 文件名: hanoi.py

def hanoi(n, source, target, auxiliary):
    """
    递归解决汉诺塔问题
    :param n: 盘子数量
    :param source: 起始柱子
    :param target: 目标柱子
    :param auxiliary: 辅助柱子
    """
    if n == 1:
        print(f"移动盘子 1 从 {source} 到 {target}")
        return
    # 步骤1: 将n-1个盘子从source移到auxiliary
    hanoi(n - 1, source, auxiliary, target)
    # 步骤2: 将第n个盘子从source移到target
    print(f"移动盘子 {n} 从 {source} 到 {target}")
    # 步骤3: 将n-1个盘子从auxiliary移到target
    hanoi(n - 1, auxiliary, target, source)

# 演示3个盘子的移动过程
if __name__ == "__main__":
    print("=== 汉诺塔问题演示 (3个盘子) ===")
    hanoi(3, 'A', 'C', 'B')

三、阶乘问题 —— 递归的线性累积

算法分析

阶乘定义：n! = 1 × 2 × 3 × … × n
递归定义：

• 0! = 1
• n! = n × (n-1)!

示意图（以4!为例）：

4! = 4 × 3!
   = 4 × (3 × 2!)
   = 4 × (3 × (2 × 1!))
   = 4 × (3 × (2 × (1 × 0!)))
   = 4 × (3 × (2 × (1 × 1)))
   = 4 × (3 × (2 × 1))
   = 4 × (3 × 2)
   = 4 × 6
   = 24

实现思路

递归函数直接按定义展开，基础情况为n=0或n=1时返回1。

代码实现

# 文件名: factorial.py

def factorial(n):
    """
    递归计算n的阶乘
    :param n: 非负整数
    :return: n!
    """
    if n == 0 or n == 1:
        return 1
    return n * factorial(n - 1)

# 演示1~10的阶乘
if __name__ == "__main__":
    print("n\tn!")
    for i in range(1, 11):
        print(f"{i}\t{factorial(i)}")

四、进制转换器 —— 递归的除基取余

算法分析

十进制转二进制：不断除以2，记录余数，最后逆序排列。

递归思路：

• 基础情况：n < 2 时直接返回 str(n)
• 递归情况：先递归处理 n//2，再拼接 n%2

例如：13 → 1101

13 // 2 = 6 余 1
6 // 2 = 3 余 0
3 // 2 = 1 余 1
1 // 2 = 0 余 1
→ 逆序：1101

实现思路

递归函数返回字符串形式的二进制表示，通过“先递归后拼接”实现逆序。

代码实现

# 文件名: decimal_to_binary.py

def dec_to_bin(n):
    """
    递归将十进制数转换为二进制字符串
    :param n: 非负整数
    :return: 二进制字符串
    """
    if n < 2:
        return str(n)
    return dec_to_bin(n // 2) + str(n % 2)

# 测试
if __name__ == "__main__":
    num = int(input("请输入一个十进制数: "))
    binary = dec_to_bin(num)
    print(f"{num} 的二进制表示为: {binary}")

五、分解数字 —— 递归的数字拆解

算法分析

将多位数按位拆分为列表，如12345 → [1,2,3,4,5]

递归思路：

• 基础情况：n < 10 时返回 [n]
• 递归情况：先递归处理 n//10，再追加 n%10

例如：12345

12345 → [1234] + [5]
      → [[123] + [4]] + [5]
      → [[[12] + [3]] + [4]] + [5]
      → [[[[1] + [2]] + [3]] + [4]] + [5]
      → [1,2,3,4,5]

实现思路

利用整除和取模操作逐层剥离最低位，递归构建列表。

代码实现

# 文件名: split_digits.py

def split_number(n):
    """
    递归分解数字为各位数字列表
    :param n: 正整数
    :return: 各位数字组成的列表
    """
    if n < 10:
        return [n]
    return split_number(n // 10) + [n % 10]

# 测试
if __name__ == "__main__":
    num = int(input("请输入一个多位数: "))
    digits = split_number(num)
    print(f"{num} 分解为: {digits}")

六、二叉树遍历 —— 递归的结构化访问

算法分析

二叉树有三种深度优先遍历方式：

• 先序遍历（Preorder）：根 → 左 → 右
• 中序遍历（Inorder）：左 → 根 → 右
• 后序遍历（Postorder）：左 → 右 → 根
• 层次遍历（Level Order）：广度优先，需队列实现（非递归）

示意图（示例树）：

      A
     / \
    B   C
   / \   \
  D   E   F

先序: A B D E C F
中序: D B E A C F
后序: D E B F C A
层次: A B C D E F

实现思路

定义树节点类，递归实现三种遍历。层次遍历使用队列模拟BFS。

代码实现

# 文件名: tree_traversal.py

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def preorder(root):
    """先序遍历：根->左->右"""
    if not root:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)

def inorder(root):
    """中序遍历：左->根->右"""
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

def postorder(root):
    """后序遍历：左->右->根"""
    if not root:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]

def level_order(root):
    """层次遍历：使用队列"""
    if not root:
        return []
    result = []
    queue = [root]
    while queue:
        node = queue.pop(0)
        result.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return result

# 构建示例树
if __name__ == "__main__":
    #       A
    #      / \
    #     B   C
    #    / \   \
    #   D   E   F
    root = TreeNode('A')
    root.left = TreeNode('B')
    root.right = TreeNode('C')
    root.left.left = TreeNode('D')
    root.left.right = TreeNode('E')
    root.right.right = TreeNode('F')

    print("先序遍历:", preorder(root))
    print("中序遍历:", inorder(root))
    print("后序遍历:", postorder(root))
    print("层次遍历:", level_order(root))

七、最大公约数与最小公倍数 —— 递归的欧几里得算法

算法分析

• 最大公约数（GCD）：使用欧几里得算法（辗转相除法）
  • gcd(a, b) = gcd(b, a mod b)，当b=0时返回a
• 最小公倍数（LCM）：lcm(a,b) = (a×b) / gcd(a,b)

示例：gcd(48, 18)

gcd(48, 18) → gcd(18, 12) → gcd(12, 6) → gcd(6, 0) → 6

实现思路

递归实现gcd，再用公式求lcm。

代码实现

# 文件名: gcd_lcm.py

def gcd(a, b):
    """
    递归计算两个数的最大公约数（欧几里得算法）
    :param a: 第一个数
    :param b: 第二个数
    :return: 最大公约数
    """
    if b == 0:
        return a
    return gcd(b, a % b)

def lcm(a, b):
    """
    计算两个数的最小公倍数
    :param a: 第一个数
    :param b: 第二个数
    :return: 最小公倍数
    """
    return abs(a * b) // gcd(a, b)

# 测试
if __name__ == "__main__":
    x = int(input("请输入第一个数: "))
    y = int(input("请输入第二个数: "))
    g = gcd(x, y)
    l = lcm(x, y)
    print(f"{x} 和 {y} 的最大公约数是: {g}")
    print(f"{x} 和 {y} 的最小公倍数是: {l}")

小结

递归是一种“化繁为简”的思维艺术。本文通过七个经典算法演练，展示了递归在不同场景下的应用：

• 斐波那契：体现递推关系的自然表达；
• 汉诺塔：展示分治思想的完美落地；
• 阶乘/进制/分解数字：揭示线性递归的简洁之美；
• 二叉树遍历：展现结构化数据的递归访问；
• GCD/LCM：体现数学算法的优雅递归实现。

虽然递归代码简短易读，但需注意：

• 必须有明确的终止条件，避免无限递归；
• 对于大规模数据，考虑尾递归优化或改用迭代；
• 理解递归调用栈有助于调试和优化。

掌握递归，不仅是学会写代码，更是培养一种“分解问题、自相似求解”的计算思维。希望本文能为你打开递归世界的大门！