第十七篇：递归函数——原理与经典案例
前言
递归是编程中最强大也最令人着迷的概念之一。本文讲解递归的基本原理、Python 中的递归深度限制、常见递归问题以及如何通过记忆化优化递归性能。
什么是递归？
核心概念
递归 = 函数调用自身来解决更小的子问题。
def countdown(n):
if n == 0: # 基准条件
print("Go!")
return
print(n)
countdown(n - 1) # 递归步骤
countdown(3) # 输出：3, 2, 1, Go!
递归的两个必要元素：
- 基准条件 — 终止递归，防止无限循环
- 递归步骤 — 缩小问题规模，向基准条件收敛
经典递归案例
阶乘计算
def factorial(n):
"""计算 n!"""
if n <= 1: # 基准条件
return 1
return n * factorial(n - 1) # 递归步骤
print(factorial(5)) # 120 (5×4×3×2×1)
print(factorial(0)) # 1
执行过程图解：
factorial(5)
→ 5 × factorial(4)
→ 4 × factorial(3)
→ 3 × factorial(2)
→ 2 × factorial(1)
→ 1 ← 基准条件触发
← 2 × 1 = 2
← 3 × 2 = 6
← 4 × 6 = 24
← 5 × 24 = 120
斐波那契数列
def fibonacci(n):
"""返回第 n 个斐波那契数"""
if n <= 0: # 基准条件
return 0
elif n == 1: # 基准条件
return 1
return fibonacci(n - 1) + fibonacci(n - 2)
# F(0)=0, F(1)=1, F(2)=1, F(3)=2, F(4)=3, F(5)=5...
for i in range(10):
print(f"F({i}) = {fibonacci(i)}")
链表反转
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
def reverse_linked_list(head):
"""递归反转链表"""
if head is None or head.next is None:
return head # 基准条件
new_head = reverse_linked_list(head.next) # 递归
head.next.next = head # 反转指向
head.next = None # 断开旧连接
return new_head # 返回新头节点
二分查找（递归版）
def binary_search(arr, target, low, high):
"""在有序数组中查找目标值"""
if low > high: # 未找到
return -1
mid = (low + high) // 2 # 取中间
if arr[mid] == target: # 找到
return mid
elif arr[mid] < target: # 右半部分
return binary_search(arr, target, mid + 1, high)
else: # 左半部分
return binary_search(arr, target, low, mid - 1)
nums = [1, 3, 5, 7, 9, 11, 13, 15]
result = binary_search(nums, 7, 0, len(nums) - 1)
print(result) # 3 — 索引位置
汉诺塔
def hanoi(n, source="A", target="C", aux="B"):
"""汉诺塔问题求解"""
if n == 1: # 基准条件
print(f"将圆盘从 {source} 移到 {target}")
return
hanoi(n - 1, source, aux, target) # 把上面 n-1 个移到辅助柱
print(f"将最大的圆盘从 {source} 移到 {target}")
hanoi(n - 1, aux, target, source) # 再把 n-1 个从辅助柱移到目标柱
hanoi(3) # 7 步
目录遍历（文件系统）
import os
def list_files(directory, prefix=""):
"""递归列出目录下所有文件"""
try:
entries = os.listdir(directory)
except PermissionError:
return
for entry in sorted(entries):
full_path = os.path.join(directory, entry)
print(prefix + entry)
if os.path.isdir(full_path):
list_files(full_path, prefix + " ") # 递归进入子目录
list_files(".") # 列出当前目录
Python 的递归深度限制
sys.setrecursionlimit()
import sys
print(sys.getrecursionlimit()) # 默认 1000
# 可以修改递归深度限制（不推荐随意改大）
sys.setrecursionlimit(2000)
# ⚠️ 过大可能导致栈溢出崩溃
递归 vs 迭代的权衡
| 特性 | 递归 | 迭代 |
|---|---|---|
| 代码可读性 | ✅ 简洁优雅 | ❌ 可能复杂 |
| 运行效率 | ❌ 有调用开销 | ✅ 更快 |
| 内存使用 | ❌ 每层压栈 | ✅ 常数空间 |
| 深度限制 | ❌ 默认 1000 | ✅ 无限制 |
| 调试难度 | ❌ 难跟踪 | ✅ 容易 |
# 示例：斐波那契对比
# 递归版本
def fib_recursive(n):
if n <= 1: return n
return fib_recursive(n - 1) + fib_recursive(n - 2)
# 迭代版本（更高效）
def fib_iterative(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
print(fib_iterative(500)) # 可以处理很大数字
# fib_recursive(500) 会栈溢出或超时
递归的优化：记忆化（Memoization）
问题：重复计算
import time
start = time.time()
print(fibonacci(40)) # 耗时很长！因为大量重复计算
end = time.time()
print(f"用时：{end - start:.2f}s") # 可能需要几十秒
优化一：functools.lru_cache
from functools import lru_cache
@lru_cache(maxsize=None)
def fibonacci_cached(n):
if n <= 1:
return n
return fibonacci_cached(n - 1) + fibonacci_cached(n - 2)
start = time.time()
print(fibonacci_cached(40)) # 瞬间完成！
end = time.time()
print(f"用时：{end - start:.4f}s")
优化二：手动实现记忆化
def fibonacci_memo(n, memo={}):
if n in memo: # 命中缓存
return memo[n]
if n <= 1: # 基准条件
return n
result = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
memo[n] = result # 保存结果
return result
print(fibonacci_memo(100)) # 即时输出
装饰器封装通用记忆化
def memoize(func):
"""通用记忆化装饰器"""
cache = {}
def wrapper(*args):
if args not in cache:
cache[args] = func(*args)
return cache[args]
wrapper.cache = cache # 可访问缓存内容
return wrapper
@memoize
def expensive_computation(x):
total = sum(range(x * 1000000))
return total
print(expensive_computation(5)) # 第一次：慢
print(expensive_computation(5)) # 第二次：瞬间！（命中缓存）
递归常见问题排查
陷阱一：用 = 代替 ==
# ❌ 错误：赋值不是比较
x = 5
if x = 5: # SyntaxError!
print("等于 5")
# ✅ 正确
if x == 5:
print("等于 5")
陷阱二：链式比较的正确性
# ✅ Python 支持数学意义上的链式比较
x = 5
print(0 < x < 10) # True — 等价于 (0 < x) and (x < 10)
print(5 < x < 10) # False — 不等价于 (5 < x) and (x < 10)
# 而是 (5 < 5) and (5 < 10) → False and True → False
# 这在数值范围检查中非常有用
score = 85
if 0 <= score <= 100:
print("有效分数")
陷阱三：可变默认参数
# ❌ 不要用列表/字典做默认参数
def append_item(item, target=[]):
target.append(item)
return target
# 第一次调用正常
append_item(1) # [1]
# 第二次调用会保留上一次的结果！
append_item(2) # [1, 2] ← 意外结果
# ✅ 正确做法
def append_item(item, target=None):
if target is None:
target = []
target.append(item)
return target
陷阱四：浮点数比较
# ❌ 不要直接用 == 比较浮点数
a = 0.1 + 0.2
b = 0.3
print(a == b) # False! 因为 0.1 + 0.2 = 0.30000000000000004
# ✅ 使用容差比较
import math
print(math.isclose(a, b)) # True
实战：表达式求值器
def evaluate_expression(expr):
"""递归解析简单数学表达式（支持 + - * / 和括号）"""
expr = expr.strip()
if not expr:
raise ValueError("空表达式")
# 尝试解析数字
try:
return float(expr.replace(' ', ''))
except ValueError:
pass
# 寻找最低优先级运算符（+ 或 -）
depth = 0
for i, ch in enumerate(expr):
if ch == '(':
depth += 1
elif ch == ')':
depth -= 1
elif depth == 0 and ch in '+-':
left = expr[:i].strip()
right = expr[i+1:].strip()
if ch == '+':
return evaluate_expression(left) + evaluate_expression(right)
else:
return evaluate_expression(left) - evaluate_expression(right)
# 找 * 或 /
depth = 0
for i, ch in enumerate(expr):
if ch == '(':
depth += 1
elif ch == ')':
depth -= 1
elif depth == 0 and ch in '*/':
left = expr[:i].strip()
right = expr[i+1:].strip()
if ch == '*':
return evaluate_expression(left) * evaluate_expression(right)
else:
return evaluate_expression(left) / evaluate_expression(right)
# 没有运算符，返回数字
return float(expr)
# 测试
print(evaluate_expression("2 + 3 * 4")) # 14
print(evaluate_expression("(2 + 3) * 4")) # 20
print(evaluate_expression("((1 + 2) * (3 + 4))")) # 21
总结
本文讲解了递归的核心知识：
- 递归原理 — 基准条件 + 递归步骤
- 经典案例 — 阶乘、斐波那契、二叉树、汉诺塔、链表
- 深度限制 — 默认 1000，可用 sys.setrecursionlimit() 调整
- 递归 vs 迭代 — 可读性 vs 性能的取舍
- 记忆化优化 — @lru_cache、手动缓存、通用装饰器
- 调试技巧 — 检查基准条件、缩小方向、边界情况
- 实战应用 — 表达式求值器、目录遍历等
下一篇文章将深入讲解高级特性：切片、迭代与列表生成式。
本文是 Python 教程系列的第十七篇。