Python递归指函数在运行过程中再次调用自身。它适合能拆成同类、规模更小的子问题的场景，例如阶乘、树形结构遍历。写递归时通常要同时想清楚两件事：何时停止（基线条件），以及如何把规模缩小后再调用自己。

阶乘的递归写法

n 的阶乘可以定义成 n 乘以 (n-1) 的阶乘，并规定 1 的阶乘是 1。后半句就是基线，前半句就是递归步骤：

Python 递归求阶乘示例运行
def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)

print(factorial(5))    # 120

两个关键部分

  • 基线条件：规模小到可以直接给出答案，不再调用自身。缺了它，调用会一直叠下去，最终触发 RecursionError。
  • 递归步骤：把当前问题化成规模更小的同类问题，再调用自己，并在返回后组合出当前答案。

factorial(4) 怎么展开

调用会先一路深入到基线，再带着返回值往回乘。左侧是递推拆小，右侧是回溯汇总：

递推：把问题拆小 回溯：结果一路带回 factorial(4) = 4 × factorial(3) factorial(3) = 3 × factorial(2) factorial(2) = 2 × factorial(1) factorial(1) → 基线：返回 1 触发回溯 返回 1 返回 2 返回 6 返回 24
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 却从负数开始）会导致结果错误或无法终止。
  • 深度过大时优先改成循环、显式栈或分治加缓存，而不是只靠提高递归上限。