文章目录
一、递归的直观感受：从汉诺塔说起
1. 汉诺塔的规则（回顾）
2. 从 3 个圆盘到 n 个圆盘：发现递归结构
3. 汉诺塔的递归代码实现
二、递归的本质：自己定义自己（基底 + 归纳）
1. 阶乘的递归定义（重温）
2. 递归的核心要素：缺一不可
三、递归实战：从斐波那契到帕斯卡三角形
1. 斐波那契数列（递归与优化）
（1）直接递归的问题：重复计算
（2）优化：记忆化缓存（避免重复计算）
2. 帕斯卡三角形（递归生成组合数）
四、递归的陷阱与避坑指南
1. 陷阱 1：无限递归（栈溢出）
2. 陷阱 2：重复计算（效率低）
3. 陷阱 3：递归深度过大（栈溢出）
递归转迭代示例：阶乘的循环实现
五、递归与编程：应用场景与思维价值
1. 递归的典型应用场景
示例：递归遍历文件夹
2. 递归的思维价值：化繁为简
六、小结：递归是 “数学归纳法” 的编程实现
欢迎回到 “程序员的数学” 系列专栏。在前五篇内容里，我们从 “0 的占位” 讲到 “递归生成排列组合”—— 其实在生成排列组合时，我们已经悄悄用了递归的思路：比如 “从 5 个元素选 3 个的组合”，可以拆解成 “选第一个元素 + 从剩下 4 个选 2 个” 和 “不选第一个元素 + 从剩下 4 个选 3 个”，这本质就是 “用小问题的解构建大问题的解”。
今天我们就专门深入 “递归” 这个主题。递归看似 “绕”，但掌握后会发现它是解决复杂问题的 “捷径”—— 比如用 10 行代码实现汉诺塔，用递归公式直接生成帕斯卡三角形。更重要的是，递归的思维和之前学的数学归纳法一脉相承：数学归纳法是 “证明无穷”，递归是 “实现无穷”，两者都依赖 “基底 + 归纳” 的核心逻辑。
接下来，我们从 “直观例子” 到 “核心原理”，再到 “编程实战与优化”，把递归讲透，让你不仅会写递归代码，更能理解 “什么时候该用递归”“如何避免递归陷阱”。
一、递归的直观感受：从汉诺塔说起
要理解递归，最好的例子就是汉诺塔（Hanoi Tower） —— 这个由数学家卢卡斯发明的游戏，完美诠释了 “大问题拆解为小问题” 的递归思想。
1. 汉诺塔的规则（回顾）
有 3 根柱子（A、B、C），A 柱上套着 n 个大小不同的圆盘，按 “大在下、小在上” 叠放。需要把所有圆盘从 A 柱移到 B 柱，规则是：
每次只能移动最顶端的 1 个圆盘；
小圆盘上不能放大圆盘。
我们先从3 个圆盘的简单情况入手，看看移动步骤（图 1）：
把 A 柱最上面 2 个圆盘移到 C 柱（借助 B 柱）；
把 A 柱剩下的最大圆盘移到 B 柱；
把 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. 递归的核心要素：缺一不可
递归代码必须满足两个条件，否则会陷入 “无限递归”（导致栈溢出）：
必须有基底：明确最小规模问题的解，让递归 “有终止的时候”；
比如阶乘的基底是n=0，如果去掉if n==0，调用factorial(5)会一直递归到factorial(-1)、factorial(-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 成立” 的思想完全一致。
六、小结：递归是 “数学归纳法” 的编程实现
今天我们深入学习了递归，核心收获可以总结为：
递归与数学归纳法的联系：基底对应数学归纳法的 “基础验证”，归纳步骤对应 “归纳推理”，两者都用 “小规模问题” 解决 “大规模问题”；
递归的核心要素：必须有基底（终止条件）和缩小规模的归纳步骤，缺一不可；
递归的实战技巧：遇到重复计算用记忆化优化，遇到深度过大转迭代，复杂结构（如树形）优先用递归；
递归的应用场景：树形结构、分治算法、动态规划，递归代码往往比循环更简洁易懂。
递归是之前数学归纳法的 “落地工具”，而接下来我们要学习的 “指数爆炸”，会解释递归中 “重复计算导致效率低” 的本质（如斐波那契的 O (2ⁿ) 复杂度），同时也会讲如何利用指数爆炸（如二分查找）—— 递归和指数爆炸的结合，会让我们更深入理解算法效率的重要性。
如果你在编程中用递归解决过有趣的问题（比如遍历复杂数据结构、实现算法），欢迎在评论区分享你的经历！