Python 中的递归

学习目标

理解递归的基本原理与核心组成部分
掌握编写递归函数的关键要素：基础情况与递归情况
能够实现经典的递归算法（如阶乘、斐波那契数列）
区分尾递归与非尾递归，并了解其性能差异
明确递归与循环的适用场景及优缺点
避免因递归深度过大导致的栈溢出问题

什么是递归

递归是一种编程技术，指函数在执行过程中调用自身，将复杂问题分解为规模更小但结构相同的子问题，直至达到最简单的情形（称为“基础情况”）。递归特别适用于具有自相似结构的问题，例如：

数学计算（阶乘、幂运算）
树和图的遍历
分治算法（如快速排序、归并排序）
文件系统目录遍历

基本结构

一个正确的递归函数必须包含两个关键部分：

def recursive_function(parameters):
    if base_case_condition:        # 基础情况（终止条件）
        return base_result
    else:                          # 递归情况（缩小问题规模）
        return recursive_function(modified_parameters)

基础情况：防止无限递归的出口条件
递归情况：函数调用自身，参数向基础情况靠近

经典递归示例

示例 1：计算阶乘

阶乘定义：n! = n × (n-1)!，且 0! = 1

def factorial(n):
    # 基础情况
    if n == 0:
        return 1
    # 递归情况
    return n * factorial(n - 1)

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

执行过程（简化）：
factorial(5) → 5 * factorial(4) → 5 * 4 * factorial(3) → … → 5 * 4 * 3 * 2 * 1 * 1

示例 2：斐波那契数列

斐波那契定义：F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(10))  # 输出：55

注意：此实现时间复杂度为 O(2ⁿ)，效率较低。实际项目中应使用记忆化或迭代优化。

递归的类型

1. 非尾递归

递归调用不是函数的最后一步，调用返回后还需进行额外计算。

def nontail_fact(n):
    if n <= 1:
        return 1
    return n * nontail_fact(n - 1)  # 乘法在递归返回后执行

每次递归都会在调用栈中保留上下文，内存消耗随深度线性增长。

2. 尾递归

递归调用是函数的最后一步操作，无需保存额外状态。

def tail_fact(n, acc=1):
    if n == 0:
        return acc
    return tail_fact(n - 1, acc * n)  # 所有计算在调用前完成

理论上可被编译器优化为循环（称为“尾递归优化”），节省栈空间。
但 Python 解释器不支持尾递归优化，因此尾递归在 Python 中仍会消耗栈空间。

递归/循环

特性	递归	循环（迭代）
可读性	对天然递归问题更直观、简洁	逻辑可能更复杂
内存消耗	每次调用占用栈帧，深度大时易栈溢出	通常只使用常量级额外空间
性能	函数调用开销较大	通常更快
适用场景	树 / 图遍历、分治、回溯等	简单重复任务、已知迭代次数的问题

示例对比：阶乘的迭代实现

def factorial_iter(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

在 Python 中，优先考虑迭代，除非问题结构天然适合递归。

何时应避免使用递归

问题可用简单循环解决（如累加、遍历列表）
递归深度可能很大（Python 默认递归限制约 1000 层）
```
import sys
print(sys.getrecursionlimit())  # 查看当前限制
```
性能敏感场景（函数调用开销不可接受）
存在大量重复子问题（如朴素斐波那契），应改用动态规划或记忆化

递归最佳实践

始终明确基础情况，确保递归能终止
验证参数是否向基础情况收敛（如 n-1 最终会到 0）
对深度不确定的问题，考虑改用栈模拟递归

使用 functools.lru_cache 缓存结果，避免重复计算：

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci(n):
    if n < 2:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

重点总结

递归 = 基础情况 + 递归情况
必须保证每次递归都使问题规模缩小，最终到达基础情况
Python 不优化尾递归，深层递归可能导致 RecursionError
递归代码简洁但可能低效，需权衡可读性与性能
对重复子问题，应结合记忆化提升效率
在大多数情况下，迭代是更安全、高效的选择

思考题

为什么 Python 不实现尾递归优化？这与语言设计哲学有何关联？
如何将一个深度未知的递归算法（如遍历文件夹）安全地转换为迭代版本？
除了 @lru_cache，你还能想到哪些方法可以优化递归函数的性能？