本文目录导读：
我来通过几个经典的递归案例,详细解释Python函数的递归执行过程。
基础递归示例：阶乘计算
def factorial(n):
print(f"进入递归: n = {n}")
# 基本情况（递归终止条件）
if n == 1:
print(f"到达基本情况: factorial(1) = 1")
return 1
# 递归调用
result = n * factorial(n - 1)
print(f"返回: factorial({n}) = {n} * factorial({n-1}) = {result}")
return result
# 测试
print("最终结果:", factorial(4))
执行过程输出：
进入递归: n = 4
进入递归: n = 3
进入递归: n = 2
进入递归: n = 1
到达基本情况: factorial(1) = 1
返回: factorial(2) = 2 * factorial(1) = 2
返回: factorial(3) = 3 * factorial(2) = 6
返回: factorial(4) = 4 * factorial(3) = 24
最终结果: 24递归执行流程图解
factorial(4)
├── 4 > 1, 继续递归
├── 调用 factorial(3)
│ ├── 3 > 1, 继续递归
│ ├── 调用 factorial(2)
│ │ ├── 2 > 1, 继续递归
│ │ ├── 调用 factorial(1)
│ │ │ └── 返回 1
│ │ └── 返回 2 * 1 = 2
│ └── 返回 3 * 2 = 6
└── 返回 4 * 6 = 24斐波那契数列递归
def fibonacci(n):
# 基本情况
if n <= 1:
return n
# 递归调用：F(n) = F(n-1) + F(n-2)
return fibonacci(n-1) + fibonacci(n-2)
# 带执行追踪的版本
def fibonacci_trace(n, depth=0):
indent = " " * depth
print(f"{indent}计算 fibonacci({n})")
if n <= 1:
print(f"{indent}返回 {n}")
return n
left = fibonacci_trace(n-1, depth+1)
right = fibonacci_trace(n-2, depth+1)
result = left + right
print(f"{indent}返回 {left} + {right} = {result}")
return result
print("计算 fibonacci(4):")
fibonacci_trace(4)
执行过程输出：
计算 fibonacci(4)
计算 fibonacci(3)
计算 fibonacci(2)
计算 fibonacci(1)
返回 1
计算 fibonacci(0)
返回 0
返回 1 + 0 = 1
计算 fibonacci(1)
返回 1
返回 1 + 1 = 2
计算 fibonacci(2)
计算 fibonacci(1)
返回 1
计算 fibonacci(0)
返回 0
返回 1 + 0 = 1
返回 2 + 1 = 3经典递归案例：汉诺塔
def hanoi(n, source, target, auxiliary):
"""
将n个盘子从source移动到target，使用auxiliary作为辅助
"""
if n == 1:
print(f"移动盘子 1: {source} -> {target}")
return
# 将n-1个盘子从source移到auxiliary
hanoi(n-1, source, auxiliary, target)
# 将最大的盘子移到target
print(f"移动盘子 {n}: {source} -> {target}")
# 将n-1个盘子从auxiliary移到target
hanoi(n-1, auxiliary, target, source)
print("3层汉诺塔解决方案:")
hanoi(3, 'A', 'C', 'B')
递归执行的核心原理
1 调用栈（Call Stack）
每次递归调用都会：
- 压栈：将当前函数的状态（参数、局部变量、返回地址）压入调用栈
- 执行：执行新的函数实例
- 出栈：函数执行完毕，从栈中弹出，返回结果
# 可视化递归调用栈
import sys
sys.setrecursionlimit(1000)
def trace_recursion(n, depth=0):
"""递归调用栈追踪"""
indent = "│ " * depth
if depth == 0:
print("调用栈开始:")
if n == 0:
print(f"{indent}└── base case: n=0, 返回1")
return 1
print(f"{indent}├── push: n={n}, 准备递归")
result = n * trace_recursion(n-1, depth+1)
print(f"{indent}├── pop: n={n}, 返回 {n} * {n-1}! = {result}")
return result
print("递归调用栈追踪 (n=3):")
trace_recursion(3)
执行过程：
调用栈开始:
├── push: n=3, 准备递归
│ ├── push: n=2, 准备递归
│ │ ├── push: n=1, 准备递归
│ │ │ └── base case: n=0, 返回1
│ │ ├── pop: n=1, 返回 1 * 0! = 1
│ ├── pop: n=2, 返回 2 * 1! = 2
├── pop: n=3, 返回 3 * 2! = 6递归的关键要素
1 四要素
def recursion_template(parameter):
# 1. 基本情况（终止条件）
if base_case_condition:
return base_case_value
# 2. 递推关系（逻辑处理）
# 3. 缩小问题规模
# 4. 递归调用
smaller_result = recursion_template(smaller_parameter)
return combine(smaller_result, parameter)
2 常见错误与优化
# ❌ 没有终止条件的无限递归
def bad_recursion(n):
return n + bad_recursion(n-1) # 会无限递归下去
# ✅ 正确写法
def good_recursion(n):
if n <= 0:
return 0
return n + good_recursion(n-1)
# ❌ 重复计算（如斐波那契）
def fib_slow(n):
if n <= 1:
return n
return fib_slow(n-1) + fib_slow(n-2) # 大量重复计算
# ✅ 使用记忆化优化
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_fast(n):
if n <= 1:
return n
return fib_fast(n-1) + fib_fast(n-2)
实际应用：文件系统遍历
import os
def list_files(directory, indent=0):
"""递归遍历文件夹"""
prefix = " " * indent
try:
items = os.listdir(directory)
except PermissionError:
return
for item in items:
item_path = os.path.join(directory, item)
if os.path.isfile(item_path):
print(f"{prefix}📄 {item}")
elif os.path.isdir(item_path):
print(f"{prefix}📁 {item}/")
list_files(item_path, indent + 1)
# 使用示例
# list_files(".") # 列出当前目录所有文件
递归执行的本质：
- 栈数据结构：每次调用都压栈，返回时出栈
- 分而治之：将大问题分解为小问题
- 基本情况：必须要有终止条件
- 递推关系：需要能推导出解决方案
何时使用递归：
- 问题天然具有递归结构（树、图、分治等）
- 代码简洁性比性能更重要
- 问题规模可控，不会导致栈溢出
何时避免递归：
- 性能要求高，递归开销大
- 递归深度可能很大
- 可以使用迭代简单解决的问题
