递归函数例子详解：递归终止条件和调用栈怎么理解

递归，是函数在执行过程中直接或间接调用自身。它常用于处理具有“整体由更小的同类问题组成”这一特点的任务，例如遍历树形结构、计算阶乘、搜索嵌套数据。

递归代码有时很短，但理解和写对它需要同时关注两件事：函数如何把问题逐步缩小，以及缩小到什么情况时应该停止。第二件事尤其重要。终止条件不完整，函数可能无限调用；递归过程没有朝终止条件推进，也会造成同样的问题。

本文使用 Python 3 说明递归的基本概念、调用栈、适用场景、边界处理和常见错误。示例可以复制到 Python 3 环境中运行。

一、什么是递归函数

先看一个计算正整数阶乘的递归函数。正整数 n 的阶乘记作 n!，例如 5! = 5 × 4 × 3 × 2 × 1。它可以写成下面的关系：

• 0! = 1
• n! = n × (n - 1)!，当 n > 0

对应的 Python 实现是：

def factorial(n):
    if n < 0:
        raise ValueError("n 必须是非负整数")
    if n == 0:
        return 1
    return n * factorial(n - 1)


print(factorial(5))  # 120

函数 factorial 调用了自己，但调用参数从 n 变成了 n - 1。当参数到达 0 时，函数直接返回 1，不再继续调用。这一条直接返回的分支就是终止条件，也常叫基本情况（base case）。

二、递归函数的两个必要部分

一个正常工作的递归函数，通常包含下面两部分。

1. 终止条件：说明什么时候直接得到结果

终止条件应覆盖问题中不需要继续拆分的情况。阶乘的终止条件是 n == 0。处理链表时，终止条件可能是当前节点为空；遍历树时，可能是当前节点不存在或为 None。

如果没有终止条件，函数会不断调用自己，直到运行环境无法继续创建调用栈帧。即使写了终止条件，如果它没有覆盖合法输入，也仍可能出错。例如阶乘函数只处理了 n == 0，而输入一个负数时，参数会变成 -1、-2、-3，永远到不了 0。

2. 递归步骤：让问题朝终止条件推进

递归调用必须把当前问题转化为更小或更接近终止条件的子问题。阶乘中的 n - 1 会逐步降低参数；计算列表元素和时，可以每次处理一个元素，让待处理列表越来越短。

可以用三个问题检查递归步骤：

1. 每次调用是否在解决一个比当前问题更小的问题？
2. 这个变化是否能在有限步内到达终止条件？
3. 每次调用是否正确合并了子问题的结果？

三、调用栈是怎么工作的

函数调用时，运行环境需要记录这次调用的参数、局部变量，以及调用结束后应该从哪里继续执行等信息。这些信息通常保存在调用栈中的栈帧里。普通函数会创建栈帧，递归调用也一样；递归并不会让旧调用消失，而是把新的调用压到栈上。

以 factorial(3) 为例，调用过程可以概括为：

1. factorial(3) 发现参数不是 0，需要计算 3 * factorial(2)，于是暂停等待子调用的结果。
2. factorial(2) 需要计算 2 * factorial(1)，同样暂停。
3. factorial(1) 需要计算 1 * factorial(0)，继续调用。
4. factorial(0) 命中终止条件，返回 1。
5. 调用逐层返回：factorial(1) 得到 1，factorial(2) 得到 2，最终 factorial(3) 得到 6。

可以把过程简写为：

factorial(3)
  等待 3 * factorial(2)
    等待 2 * factorial(1)
      等待 1 * factorial(0)
        返回 1
      返回 1 * 1 = 1
    返回 2 * 1 = 2
  返回 3 * 2 = 6

递归既有“不断深入”的阶段，也有“逐层返回”的阶段。很多初学者只看到函数重复调用，却忽略了每个调用都在等待子调用完成。若递归深度很大，等待中的栈帧也会很多，因此递归可能消耗调用栈资源。

四、适用场景：数据本身具有层次结构

递归特别适合数据结构天然由子结构组成的情况。树是典型例子：一个节点可以有多个子节点，而每个子节点本身又是一棵更小的树。使用递归遍历时，代码结构往往与数据结构的定义相吻合。

下面的函数计算二叉树所有节点的值之和。节点没有子节点时，其左右子树为空，递归在这里终止。

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


def sum_tree(node):
    if node is None:
        return 0
    return node.value + sum_tree(node.left) + sum_tree(node.right)


tree = Node(
    10,
    left=Node(5, Node(2), Node(3)),
    right=Node(7, None, Node(1)),
)

print(sum_tree(tree))  # 28

这里的终止条件是 node is None，它表示当前子树为空，贡献值为 0。递归步骤分别处理左子树和右子树，再把两边的结果与当前节点值相加。

递归也常用于目录结构、语法树、组织架构、嵌套 JSON 等层级数据。但需要注意：这些结构未必总是一棵真正的树。例如对象之间可能互相引用，目录中可能存在符号链接，导致结构形成环。遇到可能有环的数据，不能只靠“遍历子节点”而不做记录，否则可能反复访问同一对象。

五、把递归改写为可观察的过程

当递归逻辑难以理解时，可以临时打印参数，观察每次调用的状态。下面的版本在进入函数时输出缩进，缩进深度对应当前递归深度：

def factorial_with_trace(n, depth=0):
    indent = "  " * depth
    print(f"{indent}进入 factorial({n})")

    if n < 0:
        raise ValueError("n 必须是非负整数")
    if n == 0:
        print(f"{indent}命中终止条件，返回 1")
        return 1

    result = n * factorial_with_trace(n - 1, depth + 1)
    print(f"{indent}factorial({n}) 返回 {result}")
    return result


print("最终结果：", factorial_with_trace(3))

depth 只是为了展示调用层级，不是递归算法必须具备的参数。调试信息能帮助区分“调用还在深入”与“已经开始返回”，但生产代码通常不应无节制地输出日志，特别是在输入规模较大时。

六、边界条件：先定义输入范围，再定义递归

递归函数不能只考虑“典型输入”。要先明确函数允许接受什么，再决定哪些情况返回结果、哪些情况报错。阶乘通常定义在非负整数上，因此负数应明确拒绝。若使用 Python，布尔值也是整数类型的子类，True 可以通过部分整数检查；如果业务不接受布尔值，就应单独排除。

def factorial_checked(n):
    if isinstance(n, bool) or not isinstance(n, int):
        raise TypeError("n 必须是整数")
    if n < 0:
        raise ValueError("n 必须是非负整数")

    if n == 0:
        return 1
    return n * factorial_checked(n - 1)


print(factorial_checked(6))  # 720

对不同问题，边界定义也不同。处理列表时要考虑空列表；查找树节点时要考虑空树；处理数字区间时要明确区间是否包含端点；处理可选参数时要区分“未传入”和“传入空值”。边界条件不是为了应付报错而随手添加的分支，而是函数定义的一部分。

还要确认递归步骤不会越过终止条件。例如按区间二分时，递归边界和区间开闭规则必须匹配；若采用闭区间 [left, right]，应在 left > right 时处理空区间。边界不一致可能导致遗漏元素，也可能让区间长期不缩小。

七、常见错误与排查方法

错误一：忘记写终止条件

def broken(n):
    return broken(n - 1)

这个函数无论传入什么值都会继续调用自身。应补充对合法边界的处理，并确认其他输入会逐步到达该边界。

错误二：有终止条件，但参数没有靠近它

def broken_countdown(n):
    if n == 0:
        return
    broken_countdown(n + 1)

函数虽然写了 n == 0，但参数不断增大，起始值不为零时到不了终止条件。递归步骤应改为朝边界推进，例如倒数时使用 n - 1，并妥善处理负数起点。

错误三：子调用结果没有参与计算

def broken_sum(n):
    if n == 0:
        return 0
    broken_sum(n - 1)
    return n

这里调用了 broken_sum(n - 1)，却丢弃了返回值，因此它并没有把子问题的结果合并起来。计算 1 到 n 的和，应写成 n + broken_sum(n - 1)。

错误四：返回值类型不一致

假设树遍历函数在遇到空节点时返回 None，而非空节点时返回整数和，之后执行加法就会出错。每个递归分支都应该遵守同一套返回值约定。空树求和返回 0，空列表拼接返回空列表，都是常见的单位结果设计。

错误五：误以为递归一定更简洁或更快

递归不一定优于循环。对于简单计数、处理大规模线性序列等任务，循环通常更直接，也不需要为每一步创建递归栈帧。递归的价值在于让程序结构贴合问题结构，而不是减少代码行数。

八、递归深度、参数限制与性能

递归深度指从最外层调用到最深层调用之间的层数。深度通常取决于输入规模和算法设计，而不是只取决于函数写了多少行。处理长度为 n 的单链表时，朴素递归遍历可能产生约 n 层调用；平衡树的递归遍历深度通常与树高相关。

Python 对解释器栈深度有保护限制。达到限制时通常会抛出 RecursionError，其具体可用深度受运行环境、调用链和解释器设置等因素影响，不应把某个固定数值当作所有程序都安全的参数上限。可以通过下面的代码查看当前递归限制：

import sys

print(sys.getrecursionlimit())

sys.setrecursionlimit() 可以调整 Python 解释器的递归限制，但这不是通用的“修复递归”办法。将限制设得过高，并不代表底层栈空间足够；在某些环境中，不安全地提高限制可能导致解释器崩溃。应先评估算法深度，必要时改用循环、显式栈，或减少递归深度。

其他语言的行为和限制也不完全相同。是否进行尾调用优化、栈空间大小以及溢出时的表现，取决于语言规范、实现和运行环境。不能因为某种语言或某个运行环境看起来允许较深递归，就默认所有平台都不会溢出。

递归也可能带来重复计算。朴素递归计算斐波那契数时，许多子问题会反复求解：

def fib_slow(n):
    if n < 0:
        raise ValueError("n 必须是非负整数")
    if n < 2:
        return n
    return fib_slow(n - 1) + fib_slow(n - 2)

这个实现表达了定义，但会重复计算大量结果。若要保持递归表达，可以使用缓存：

from functools import lru_cache


@lru_cache(maxsize=None)
def fib(n):
    if n < 0:
        raise ValueError("n 必须是非负整数")
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)


print(fib(30))

缓存减少了重复计算，但并不会自动消除递归深度问题。若需要处理非常大的 n，迭代版本通常更合适：

def fib_iterative(n):
    if isinstance(n, bool) or not isinstance(n, int):
        raise TypeError("n 必须是整数")
    if n < 0:
        raise ValueError("n 必须是非负整数")

    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a


print(fib_iterative(30))

九、递归与迭代：何时选择哪一种

递归和迭代都可以重复处理问题，但状态保存方式不同。递归依靠调用栈隐式保存每一层的参数和局部状态；迭代通常使用循环变量、列表或其他显式数据结构保存状态。

可以优先考虑递归的情况包括：

• 问题天然具有树状或嵌套结构，例如树遍历、表达式树计算。
• 问题可以清晰地拆成规模更小的同类子问题。
• 预计递归深度可控，且递归表达更容易验证。

可以优先考虑迭代或显式栈的情况包括：

• 输入规模可能很大，递归深度无法可靠控制。
• 问题本质上是线性重复操作，例如简单计数或顺序扫描。
• 需要精确控制遍历顺序、暂停恢复过程或管理待处理任务。

对于树遍历，递归版本常常更容易读；如果树可能极深，可以用显式栈来避免依赖语言调用栈。两种写法的选择应结合数据规模、语言运行环境、可维护性和性能测试，而不是只凭“递归看起来优雅”。

十、递归与安全：不可信输入需要有界处理

递归本身不是安全机制，也不会自动限制输入。递归处理外部提供的嵌套数据时，如果对方能控制嵌套深度，极深结构可能导致运行缓慢、资源消耗增加或触发递归深度错误。对于服务器、解析器和公开接口，应结合业务要求设置明确的深度、节点数量、数据大小或处理时间限制。

限制应当作用于实际工作量，而不只是限制某一个函数参数。例如处理嵌套列表时，可以同时记录当前深度和已访问节点数；仅限制深度不能阻止一个宽度极大的结构消耗大量时间与内存。具体阈值应依据系统资源、业务输入和测试结果确定，不存在适用于所有应用的统一安全数字。

图结构或对象引用可能包含环。遍历这类数据时，应使用已访问集合识别重复节点，避免陷入循环。目录遍历也需谨慎处理符号链接：如果跟随链接，目录可能通过链接回到已访问位置。可依据需求选择不跟随链接、记录已访问目录标识，或采用其他明确的环路策略。

文件系统操作还涉及权限、路径校验和符号链接等独立安全问题。递归遍历目录并不会自动保证路径安全；当路径来自用户输入时，应使用适合具体操作系统和业务场景的路径处理与权限控制，不能仅靠字符串拼接来假设路径一定处于预期目录中。

如果数据格式本身允许极深嵌套，且必须完整处理，可以考虑非递归解析方式，或采用支持深度限制与资源限制的解析方案。发生 RecursionError 时也不应简单吞掉异常后声称处理成功；应明确报告输入超限、拒绝该输入，或转入经过验证的替代处理流程。

十一、写递归函数的检查清单

动手实现前，可以按下面顺序检查：

1. 明确函数的输入范围、返回值含义和异常情况。
2. 列出最小或最简单的输入，并写清对应返回结果。
3. 写出递归步骤，说明每次调用如何缩小问题。
4. 确认每条递归路径都能在有限步内到达终止条件。
5. 检查递归调用的结果是否被正确使用和合并。
6. 估算最大递归深度与重复计算，考虑输入规模。
7. 对空值、边界值、错误类型和可能的循环结构进行测试。
8. 若输入不可信，增加适合业务的资源和深度限制。

例如阶乘可以测试 0、1、一般正整数、负数、浮点数和布尔值；树遍历可以测试空树、单节点树、不平衡树以及可能共享或循环引用的结构。测试用例应覆盖函数定义中的边界，而不只是验证一个常见结果。

总结

理解递归的关键，不是记住“函数调用自己”这句话，而是看清每次调用如何推进、终止条件何时命中，以及调用栈如何保存尚未完成的工作。终止条件负责停下来，递归步骤负责走向终止条件，返回过程负责把子问题结果合并回当前问题。

递归适合层级结构清晰、子问题定义自然的任务；它并非总比循环简单，也有深度、性能和资源方面的限制。编写时明确输入边界，验证每条路径能够结束，并在处理不可信数据时限制实际资源消耗，才能让递归代码既容易理解，也更可靠。