Python函数递归案例如何递归执行

本文目录导读：

1. 基础递归示例：阶乘计算
2. 递归执行流程图解
3. 斐波那契数列递归
4. 经典递归案例：汉诺塔
5. 递归执行的核心原理
6. 递归的关键要素
7. 实际应用：文件系统遍历

我来通过几个经典的递归案例,详细解释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）

每次递归调用都会：

1. 压栈：将当前函数的状态（参数、局部变量、返回地址）压入调用栈
2. 执行：执行新的函数实例
3. 出栈：函数执行完毕，从栈中弹出，返回结果

# 可视化递归调用栈
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(".")  # 列出当前目录所有文件

递归执行的本质：

1. 栈数据结构：每次调用都压栈，返回时出栈
2. 分而治之：将大问题分解为小问题
3. 基本情况：必须要有终止条件
4. 递推关系：需要能推导出解决方案

何时使用递归：

• 问题天然具有递归结构（树、图、分治等）
• 代码简洁性比性能更重要
• 问题规模可控，不会导致栈溢出

何时避免递归：

• 性能要求高，递归开销大
• 递归深度可能很大
• 可以使用迭代简单解决的问题