在 Python 中，递归指函数在执行过程中再次调用自身。它适用于可分解为规模更小、结构相同的子问题，例如阶乘定义或树形目录遍历。编写递归时须同时明确基线条件（何时停止）与递归步骤（如何把问题缩小）。若缺少基线或基线不可达，调用将持续叠加直至触发 RecursionError。本节以阶乘为例说明展开过程，并讨论与循环的取舍及深度限制。
阶乘的递归实现
n 的阶乘可定义为 n 乘以 (n−1) 的阶乘，并规定 1 的阶乘为 1。后者为基线，前者为递归步骤：
def factorial(n):
if n == 1:
return 1
return n * factorial(n - 1)
print(factorial(5)) # 120基线条件与递归步骤
- 基线条件：规模足够小时直接返回结果，不再调用自身。缺少基线时调用将一直叠加，最终引发
RecursionError。 - 递归步骤：将当前问题化为规模更小的同类问题，调用自身并在返回后组合出当前答案。
factorial(4) 的展开
调用先递推至基线，再沿返回链回溯相乘。左侧为递推拆小，右侧为回溯汇总：
factorial(4) 先一路递推到基线 factorial(1)，拿到 1 后再从下往上回溯：1 → 2 → 6 → 24。调用栈先压后弹。
factorial(4)
= 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * (3 * (2 * 1))
= 24
斐波那契数列
每一项为前两项之和，自然出现两次递归调用。下列朴素实现在 n 较大时会重复计算大量子问题，思路清楚但性能较差；工程上常改用循环或缓存：
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
for i in range(8):
print(fib(i), end=" ")
print()递归与循环
| 维度 | 递归 | 循环 |
|---|---|---|
| 表达 | 贴近分治、树形定义 | 须自行维护状态变量 |
| 开销 | 每次调用占一层栈帧，过深可能溢出 | 通常开销更小 |
| 适用 | 目录树、表达式树、分治 | 多数线性重复任务 |
递归深度上限
CPython 默认将递归深度限制在大约一千层，超出则抛出 RecursionError。可用 sys.setrecursionlimit 调大，但深度过大往往表明应改进算法，而非仅提高限额：
import sys
sys.setrecursionlimit(5000)目录树遍历
子目录内仍可包含子目录，结构本身适合递归。用 os 列出当前层，遇目录再调用自身，可遍历整棵树：
import os
def walk(dir_path, depth=0):
for item in os.listdir(dir_path):
full = os.path.join(dir_path, item)
print(" " * depth + item)
if os.path.isdir(full):
walk(full, depth + 1)
walk(".")注意事项
- 缺少基线条件，或基线永远达不到，将导致无法终止的递归。
- 基线条件错误（例如阶乘使用
n == 0却从负数调用）可能导致错误结果或无法终止。 - 深度过大时优先改为循环、显式栈或带缓存的分治，而非仅提高递归上限。
本节说明了 Python 中递归的组成与常见用法。下一节介绍类与对象：__init__、self 及实例方法。