Python递归函数完全指南

一、递归函数工作原理

递归函数包含三个关键阶段：

1. 递进阶段：函数不断调用自身直到触发基线条件
2. 基线条件：停止递归的终止条件
3. 回归阶段：从最后一次调用开始逐层返回结果

二、递归函数实现步骤

def recursive_function(parameters):
    # 1. 定义基线条件（终止条件）
    if base_case_condition:
        return base_case_value
        
    # 2. 分解问题为更小的子问题
    modified_parameters = modify(parameters)
    
    # 3. 递归调用自身
    result = recursive_function(modified_parameters)
    
    # 4. 组合结果并返回
    return combine(result)

三、经典递归案例

1. 阶乘计算

def factorial(n):
    # 基线条件：0! = 1
    if n == 0:
        return 1
    # 递归条件：n! = n * (n-1)!
    else:
        return n * factorial(n-1)

print(factorial(5))  # 输出: 120

2. 斐波那契数列

def fibonacci(n):
    # 基线条件
    if n <= 1:
        return n
    # 递归条件：F(n) = F(n-1) + F(n-2)
    else:
        return fibonacci(n-1) + fibonacci(n-2)

for i in range(10):
    print(fibonacci(i), end=" ")  # 输出: 0 1 1 2 3 5 8 13 21 34

3. 文件目录遍历

import os

def scan_directory(path, level=0):
    # 基线条件：空目录
    if not os.listdir(path):
        return
    
    for item in os.listdir(path):
        full_path = os.path.join(path, item)
        print(' ' * level * 4 + '├── ' + item)
        
        # 递归扫描子目录
        if os.path.isdir(full_path):
            scan_directory(full_path, level+1)

scan_directory('/project')

四、递归使用注意事项

• 必须设置明确的基线条件，否则会导致无限递归
• Python默认递归深度限制为1000层（可通过sys.setrecursionlimit()修改）
• 递归可能产生重复计算（斐波那契数列案例尤为明显）
• 对于深度问题，考虑使用迭代法或尾递归优化
• 递归函数应确保每次调用都向基线条件推进

五、递归优化技巧

1. 缓存装饰器：使用@lru_cache存储中间结果
2. 尾递归优化：使递归调用成为函数最后操作
3. 迭代转换：复杂递归可转为栈+循环结构
4. 分治法：将大问题分解为独立子问题（如归并排序）