作者：李晓辉

联系方式：

1. 微信：Lxh_Chat

2. 邮箱：939958092@qq.com

上一篇我们学习了 Python 的嵌套函数、闭包和 lambda 表达式，知道了如何封装函数逻辑、保存外围作用域中的变量，以及使用简洁的函数处理数据。

今天，我们再来学习一种比较有意思的函数：递归函数。

先想一个问题：如果让你计算 5!，也就是 5 的阶乘，你会怎么做？

很简单，就是：

5! = 5 × 4 × 3 × 2 × 1

如果计算 10!，我们仍然可以按照这个规律计算。

但如果一个问题本身就可以拆成一个更小的同类问题，能不能让函数调用自己，逐步解决问题呢？

这就是递归的基本思路。

递归不仅可以用来计算阶乘，还可以用于遍历目录、处理树形结构、解析嵌套数据等任务。不过，递归也有自己的使用条件。如果设计不当，程序可能会无限调用自身，最终触发异常。

这篇文章，我们就从最简单的例子开始，把递归函数讲清楚。

什么是递归函数

所谓递归函数，就是在函数内部直接或间接调用自身的函数。

先看一个简单的例子：

def countdown(n):
    if n <= 0:
        print("倒计时结束")
        return

    print(n)
    countdown(n - 1)


countdown(3)

输出结果：

3
2
1
倒计时结束

这段代码是怎么执行的？

当调用 countdown(3) 时，程序首先判断 n 是否小于或等于 0。由于此时 n = 3，条件不成立，因此输出 3，然后调用：

1	countdown(n - 1)

也就是再次调用 countdown(2)。

接下来，程序输出 2，继续调用 countdown(1)。然后输出 1，继续调用 countdown(0)。

这一次，条件 n <= 0 成立，程序输出“倒计时结束”，并通过 return 结束当前函数调用。

整个过程可以用下面的流程图表示：

flowchart TD
    A["调用 countdown(3)"] --> B{"n <= 0 ?"}
    B -->|否| C["输出 n"]
    C --> D["调用 countdown(n - 1)"]
    D --> B
    B -->|是| E["输出倒计时结束"]
    E --> F["return，结束当前调用"]

注意，递归并不是让函数无休止地调用自身。一个正确的递归函数，必须有办法在适当的时候停止。

那么，如何设计一个递归函数呢？

递归的两个关键组成部分

一个典型的递归函数通常包含两个重要部分：

基线条件（Base Case）：当问题已经足够简单时，直接给出结果，不再继续递归。
递归步骤（Recursive Case）：将当前问题转化为一个规模更小、形式相同的子问题。

设计递归时，除了写出这两个部分，还必须确保递归步骤能够逐步接近基线条件。

我们继续通过阶乘来理解。

从阶乘理解基线条件

数学中的阶乘定义如下：

n! = n × (n − 1) × (n − 2) × ⋯ × 1

其中：

0! = 1

根据这个规律，我们可以把阶乘拆解为：

n! = n × (n − 1)!

也就是说，计算 n 的阶乘，可以先计算 n - 1 的阶乘，再乘以 n。

于是，我们可以写出下面的递归函数：

def factorial(n):
    if n <= 1:
        return 1

    return n * factorial(n - 1)


print(factorial(5))

输出结果：

这里有两个关键点。

首先：

1 2	if n <= 1: return 1

这就是基线条件。当 n 小于或等于 1 时，函数直接返回 1，不再继续调用自身。

其次：

1	return n * factorial(n - 1)

这就是递归步骤。函数将当前的阶乘问题拆解为更小的阶乘问题。

例如，计算 factorial(5) 时，程序会依次调用：

factorial(5)
    factorial(4)
        factorial(3)
            factorial(2)
                factorial(1)

当 factorial(1) 返回 1 后，之前暂停的函数调用才会依次完成计算。

可以把这个过程分成两个阶段：

flowchart TD
    A["factorial(5)"] --> B["5 × factorial(4)"]
    B --> C["4 × factorial(3)"]
    C --> D["3 × factorial(2)"]
    D --> E["2 × factorial(1)"]
    E --> F["基线：factorial(1) = 1"]
    F --> G["返回并计算：2 × 1 = 2"]
    G --> H["计算：3 × 2 = 6"]
    H --> I["计算：4 × 6 = 24"]
    I --> J["计算：5 × 24 = 120"]

需要特别注意，递归调用并不意味着前一个函数调用已经彻底结束。它会等待后续调用返回结果，再继续执行剩余的计算。

为什么基线条件如此重要

假设我们不小心漏掉了基线条件：

def factorial(n):
    return n * factorial(n - 1)


print(factorial(5))

这段代码会不断调用自身：

factorial(5)
factorial(4)
factorial(3)
factorial(2)
factorial(1)
factorial(0)
factorial(-1)
factorial(-2)
...

由于没有停止条件，n 会不断减小，程序永远无法通过正常的递归逻辑返回结果。

最终，Python 通常会抛出：

Traceback (most recent call last):
  File "<python-input-0>", line 5, in <module>
    print(factorial(5))
          ~~~~~~~~~^^^
  File "<python-input-0>", line 2, in factorial
    return n * factorial(n - 1)
               ~~~~~~~~~^^^^^^^
  File "<python-input-0>", line 2, in factorial
    return n * factorial(n - 1)
               ~~~~~~~~~^^^^^^^
  File "<python-input-0>", line 2, in factorial
    return n * factorial(n - 1)
               ~~~~~~~~~^^^^^^^
  [Previous line repeated 991 more times]
RecursionError: maximum recursion depth exceeded

这也说明，基线条件并不是可有可无的优化，而是递归逻辑的重要组成部分。

递归的实际用途：遍历 Linux 目录

阶乘适合用来理解递归原理，但在日常运维工作中，我们很少需要自己编写阶乘计算程序。

那么，递归在 Linux 运维中有什么用途？

想象一下，你需要检查某个目录下面的文件。目录中可能还有子目录，而子目录内部又可能包含其他目录。

例如：

/var/log/
├── nginx/
│   ├── access.log
│   └── error.log
├── app/
│   ├── app.log
│   └── archive/
│       └── old.log
└── messages

如果只检查 /var/log/ 当前目录下的文件，就会遗漏子目录中的日志。

一种解决思路是：检查当前目录，再用相同的方法检查每一个子目录。

这正是递归擅长处理的问题。

Python 的 pathlib 提供了路径操作功能，我们可以结合 is_dir() 判断目录，使用 iterdir() 获取当前目录的直接子项。

下面用一个简化示例演示递归遍历目录：

from pathlib import Path


def list_files(directory):
    path = Path(directory)

    for item in path.iterdir():
        if item.is_dir():
            list_files(item)
        else:
            print(item)


list_files("/var/log")

运行后，程序会逐步检查 /var/log 及其子目录，并输出找到的文件路径。

这里的核心代码是：

1 2	if item.is_dir(): list_files(item)

如果当前项目是一个目录，就再次调用 list_files()，处理这个子目录。

每一次递归调用，处理的都是新的子目录。只要目录结构有限且遍历过程能够正常完成，递归就会随着目录层级的深入而逐步返回。

这个示例用于说明递归的原理。实际处理生产环境目录时，还需要考虑权限不足、符号链接、目录内容变化等问题；对于非常深的目录结构，使用 Path.rglob() 或 os.walk() 等现成接口往往更合适。

运维场景中，什么时候适合递归

除了遍历目录，递归还适合处理具有层级关系的数据，例如：

目录与文件：递归处理多层目录结构。
树形配置：遍历具有父子关系的配置项。
嵌套数据：处理多层嵌套的字典或列表。
依赖关系：沿着依赖关系逐层处理子任务。

不过，并不是所有重复操作都适合递归。

例如，需要依次检查 100 台服务器的 CPU 使用率时，通常直接使用 for 循环更容易理解和维护：

servers = ["web-01", "web-02", "db-01"]

for server in servers:
    print(f"正在检查服务器：{server}")

输出

1
2
3

正在检查服务器：web-01
正在检查服务器：web-02
正在检查服务器：db-01

递归更适合处理“当前问题可以拆成更小的同类问题”的情况，而不是简单地把所有循环都改写成函数调用。

递归为什么会消耗调用栈

每调用一次函数，Python 都需要保存这次调用的执行状态，例如局部变量和后续需要执行的代码位置。

递归调用时，前面的函数调用可能还没有返回，新的函数调用又开始了，因此会形成多层调用。

例如：

def countdown(n):
    if n <= 0:
        return

    countdown(n - 1)


countdown(3)

执行过程中，调用关系大致如下：

countdown(3)
    └── countdown(2)
            └── countdown(1)
                    └── countdown(0)

当最深层的调用返回后，外层调用才会依次恢复执行并结束。

如果递归层数过多，就可能超过 Python 的递归深度限制，触发 RecursionError。

递归深度不是越大越好

可以通过 sys.getrecursionlimit() 查看当前解释器的递归深度限制：

1
2
3

import sys

print(sys.getrecursionlimit())

输出结果会因 Python 版本和运行环境而有所不同，常见环境中的默认值通常在 1000 左右。

这个限制不是所有程序都能安全使用的递归层数上限，也不应该简单地认为把限制调大就能解决问题。

对于层数可能非常大的任务，优先考虑是否可以使用循环或其他迭代算法来实现。

例如，计算阶乘也可以使用循环：

def factorial(n):
    if n < 0:
        raise ValueError("n 必须大于或等于 0")

    result = 1

    for number in range(2, n + 1):
        result *= number

    return result


print(factorial(5))

输出结果：

这个版本使用循环逐步累乘，不会因为每个数字都调用一次函数而不断增加递归调用层数。

对于阶乘这样的简单计算，循环通常更加直接；递归的优势则在于某些问题本身就具有明显的递归结构。

编写递归函数时，需要注意什么

写递归时，可以按照下面的思路逐项检查。

第一，明确基线条件。

先问自己：什么情况下，当前问题已经足够简单，可以直接返回结果？

如果想不出明确的停止条件，就不要急着编写递归步骤。

第二，确保问题规模不断缩小。

例如，在阶乘计算中，每次递归都将 n 减少 1。

如果递归调用的参数始终不变，或者不断远离基线条件，就可能导致无限递归。

第三，明确每次递归返回什么。

递归调用通常需要返回一个结果，供上一层调用继续计算。

例如：

1	return n * factorial(n - 1)

这里的 factorial(n - 1) 必须先返回结果，当前调用才能完成乘法运算。

第四，留意递归深度和性能。

递归会产生函数调用开销。对于递归深度很大、或者存在大量重复子问题的算法，需要考虑循环、缓存或其他更合适的实现方式。

第五，先用小数据验证。

例如，测试阶乘时，可以先检查 factorial(0)、factorial(1) 和 factorial(5)，确认基线条件、递归步骤和最终结果都符合预期，再考虑更大的输入。

写在最后

这篇文章，我们从倒计时和阶乘两个例子出发，理解了递归函数的基本原理，并学习了基线条件与递归步骤。

随后，我们通过 Linux 目录遍历的场景，认识了递归在实际开发中的用途，也了解了递归深度限制、RecursionError 以及循环替代方案。

记住一句话：递归的关键，不是函数调用自己，而是把一个问题拆成规模更小、结构相同的子问题，并最终通过基线条件结束递归。

Python 系列(二十四) 搞懂递归函数，从基线条件到实际应用

什么是递归函数

递归的两个关键组成部分

从阶乘理解基线条件

为什么基线条件如此重要

递归的实际用途：遍历 Linux 目录

运维场景中，什么时候适合递归

递归为什么会消耗调用栈

递归深度不是越大越好

编写递归函数时，需要注意什么

写在最后