MATLAB递归函数的调用过程与终止条件

递归函数是指在执行过程中直接或间接调用自身的函数。它适合表达“一个问题可以拆成若干个规模更小、结构相同的问题”的计算过程，例如阶乘、树形结构遍历和分治搜索。递归写法有时比循环更贴近问题的定义，但并不天然更快，也不天然更安全。要写好 MATLAB 递归函数，关键是说清楚每次调用怎样缩小问题、什么时候停止，以及输入异常或深度过大时如何处理。

本文从 MATLAB 的函数调用过程讲起，再通过可运行示例说明基例、递归步骤、参数校验和递归深度限制。示例均可保存为对应的 .m 文件运行；若使用脚本中的局部函数，应注意 MATLAB 版本和文件组织方式。

一、递归调用时发生了什么

以函数 f 调用自身为例，执行到递归调用语句时，MATLAB 会开始一次新的函数调用。每次调用都有各自的输入参数、局部变量和执行位置。新调用返回后，执行会回到上一层调用中递归语句之后的位置。若调用链为 f(4)、f(3)、f(2)、f(1)，程序先逐层深入，再从最深层开始逐层返回。

可以把调用过程分为两段：

1. 向下展开：每次调用处理一个规模更小的子问题，并继续调用自身。
2. 向上返回：到达停止条件后，不再递归，返回结果；上一层取得该结果，完成自己的计算后再返回。

这种调用关系需要 MATLAB 保存尚未完成的调用状态。调用层数增加，会占用更多运行时资源；递归太深时可能触及 MATLAB 的递归调用限制，也可能受到可用内存等因素影响。因此，递归函数不仅要逻辑正确，还必须有明确、可达的停止条件。

二、写递归函数的两个组成部分

一个正确的递归定义通常至少包含以下两部分。

1. 基例：明确什么时候停止

基例（也称终止条件或边界条件）描述无需继续拆分的情形，并直接给出结果。以阶乘为例，数学定义规定 0! = 1，因此 n = 0 可以作为基例。缺少基例、基例条件写错，或者递归过程永远到不了基例，都可能导致递归不断加深，直到报错或耗尽资源。

2. 递归步骤：让子问题严格变小

递归步骤把当前问题转化为一个或多个同类子问题。必须能说明每次调用如何接近基例。例如计算 n! 时，将 n 变为 n - 1；二分搜索则每次把搜索区间缩小一半。

一种实用的检查方法是定义一个“规模指标”，例如正整数参数 n、区间长度，或尚未访问的节点数。每次递归调用都应使该指标减小，并且最终能够达到基例。仅仅“参数看起来变了”并不够：若参数在两种状态之间来回变化，仍然不会终止。

三、示例一：递归计算阶乘

下面的函数接收非负整数，返回其阶乘。它同时展示了参数校验、基例和递归步骤。

function y = factorialRecursive(n)
%FACTORIALRECURSIVE 使用递归计算非负整数 n 的阶乘。

    validateattributes(n, {'numeric'}, ...
        {'real', 'scalar', 'finite', 'integer', 'nonnegative'}, ...
        mfilename, 'n');

    if n == 0
        y = 1;
        return
    end

    y = n * factorialRecursive(n - 1);
end

保存为 factorialRecursive.m 后，可以在命令窗口运行：

factorialRecursive(0)
factorialRecursive(5)

结果分别为 1 和 120。执行 factorialRecursive(5) 时，调用链依次为：

factorialRecursive(5)
  -> 5 * factorialRecursive(4)
       -> 4 * factorialRecursive(3)
            -> 3 * factorialRecursive(2)
                 -> 2 * factorialRecursive(1)
                      -> 1 * factorialRecursive(0)
                           -> 1

最深层返回 1 后，上一层依次计算 1、2、6、24、120。这里的 return 用于在基例处直接结束当前函数调用，不会结束整个 MATLAB 会话，也不会跳过其他尚在等待返回的调用层。

validateattributes 会检查参数是否为实数、标量、有限值、整数且非负。这样可以避免负数导致递归向更小的负数继续运行，也能拒绝向量、复数、NaN 等不符合本函数定义的输入。即便输入类型正确，阶乘的结果仍可能超过数值类型的表示范围；参数验证并不能保证结果始终精确或有限。需要处理大整数时，应另行选择适合的数值表示和算法。

四、参数限制与输入校验

递归函数的参数限制来自具体算法和 MATLAB 函数的输入要求，并不存在一条适用于所有递归函数的统一规则。编写函数时，至少要明确以下问题：

• 形状：参数应为标量、向量、矩阵还是其他结构？例如，上面的阶乘函数只接受标量。
• 数值范围：是否允许负数、零、非整数或无穷值？这些取值会不会破坏递归步骤？
• 数据类型：函数是否支持整数类型、浮点数、逻辑值或自定义对象？不要默认不同类型具有相同运算行为。
• 规模：输入长度或递归深度是否会过大？除调用深度外，还应考虑每层操作的时间与内存成本。

示例中的 validateattributes 是 MATLAB 提供的输入检查工具。也可以使用条件判断并通过 error 报告不符合要求的输入。对于需要稳定接口的函数，明确拒绝不支持的参数通常优于让错误一路传到深层调用后才出现。

较新版本的 MATLAB 还支持使用 arguments 代码块声明输入验证规则。是否使用它，应结合项目所需 MATLAB 版本；如果代码要在旧版本运行，应先确认该版本支持所用语法。无论采用哪种校验方式，参数检查都不能替代基例，也不能自动证明递归一定终止。

五、示例二：递归二分搜索

二分搜索适用于已经按升序排列的数值向量。每一步检查中间元素，并丢弃不可能包含目标值的一半区间。以下函数返回目标值在向量中的一个位置；若未找到，则返回 0。

function index = binarySearchRecursive(data, target)
%BINARYSEARCHRECURSIVE 在升序向量 data 中递归查找 target。
% 找到时返回一个位置；未找到时返回 0。

    validateattributes(data, {'numeric'}, ...
        {'real', 'vector', 'finite'}, mfilename, 'data');
    validateattributes(target, {'numeric'}, ...
        {'real', 'scalar', 'finite'}, mfilename, 'target');

    if any(diff(data) < 0)
        error('binarySearchRecursive:UnsortedInput', ...
            'data 必须按升序排列。');
    end

    index = searchRange(data, target, 1, numel(data));
end

function index = searchRange(data, target, left, right)
    if left > right
        index = 0;
        return
    end

    middle = floor((left + right) / 2);

    if data(middle) == target
        index = middle;
    elseif target < data(middle)
        index = searchRange(data, target, left, middle - 1);
    else
        index = searchRange(data, target, middle + 1, right);
    end
end

保存为 binarySearchRecursive.m 后运行：

data = [2 4 7 9 12 18];
binarySearchRecursive(data, 9)
binarySearchRecursive(data, 8)

查找 9 返回其位置；查找 8 返回 0。对空向量，初始左右边界为 1 和 0，因此会立即命中 left > right 的基例。每次递归都把区间缩小，直到找到目标值或区间为空。

这个实现有明确的前提：输入必须是有限实数向量，并按升序排列。它使用 == 比较浮点数，只适合目标值与数组元素按该比较规则完全相等的场景。若数据来自浮点计算、目标值可能有舍入误差，应根据问题定义设计容差比较，而不是机械地使用固定容差。若输入含有重复元素，函数返回其中一个匹配位置，但不保证是第一个或最后一个。

示例在入口处使用 diff 检查排序，能让前提违规时尽早报错；但这次检查本身需要遍历数据。对极大数组或已由上游保证排序的场景，是否每次重复检查，应按接口可靠性和性能要求权衡。

六、示例三：遍历树形数据

树结构天然适合递归处理：访问一个节点后，再分别处理它的子节点。下面的例子用 MATLAB 结构体表示树，每个节点包含 value 和 children 字段，后者是子节点结构体数组。函数返回按先序遍历得到的节点值。

function values = preorderValues(node)
%PREORDERVALUES 对树节点进行先序遍历。
% 节点结构：node.value 为数值，node.children 为子节点结构体数组。

    if ~isstruct(node) || ~isscalar(node) || ...
            ~isfield(node, 'value') || ~isfield(node, 'children')
        error('preorderValues:InvalidNode', ...
            'node 必须是包含 value 和 children 字段的标量结构体。');
    end

    if ~isnumeric(node.value) || ~isscalar(node.value)
        error('preorderValues:InvalidValue', ...
            'node.value 必须是数值标量。');
    end

    if ~isstruct(node.children)
        error('preorderValues:InvalidChildren', ...
            'node.children 必须是结构体数组。');
    end

    values = node.value;

    for k = 1:numel(node.children)
        values = [values, preorderValues(node.children(k))]; %#ok<AGROW>
    end
end

可用以下代码构造并遍历一棵小树：

leafA = struct('value', 2, 'children', struct([]));
leafB = struct('value', 3, 'children', struct([]));
branch = struct('value', 1, 'children', [leafA, leafB]);
preorderValues(branch)

结果为 [1 2 3]。叶节点的 children 是空结构体数组，循环不执行，函数只返回当前节点值；这就是该表示法下的叶节点边界。递归处理的子节点数量可以是零个或多个。

这个示例便于理解递归结构，但用数组拼接不断扩大 values，对很大的树可能产生额外内存分配。实际处理大数据时，可以使用预分配、迭代遍历或其他更合适的数据结构。还要注意，真实数据若允许节点之间形成环（例如通过句柄对象或引用关系），就不再是普通的有限树；遍历时需要记录已访问节点，避免循环访问。单纯依靠“对子节点递归”不能自动处理环。

七、递归终止条件的常见错误

错误一：完全没有基例

函数每次都调用自身，却没有任何直接返回结果的分支，会持续增加调用深度。最简单的防护是在写代码前先列出最小输入和对应结果，再检查正常输入经过多少步能到达它。

错误二：基例不可达

例如，函数预期从正数递减到零，却在递归时误写为 n + 1。即使代码中存在 n == 0，运行路径也可能永远碰不到它。应逐步检查递归参数的变化方向，并覆盖边界输入测试。

错误三：只在返回阶段改变状态

若停止条件依赖某个值，而这个值要等递归返回后才更新，可能会使向下展开的调用始终无法停止。终止所依赖的条件应能在调用子问题的过程中逐步改善，或者通过其他可靠机制保证有限调用。

错误四：边界条件漏掉等号或空输入

区间算法容易混淆闭区间和半开区间。二分搜索若使用闭区间 [left, right]，空区间判断应与递归更新方式一致。改变一个边界的加减一，却忘记同步修改基例，可能造成漏查、重复调用或不终止。对空数组、单元素数组和边界目标值应单独测试。

错误五：把业务上的“停止”误当成递归结束

如果问题要求遇到某个结果后停止遍历，函数应在相应分支返回，并让上层调用知道是否继续；只停止当前层的循环，可能仍会回到父层并处理其他分支。停止规则应覆盖整个调用链，而不只是局部循环。

八、递归深度限制与实际边界

MATLAB 提供根对象属性 RecursionLimit，用于限制递归深度。可以在命令窗口查看当前设置：

get(0, 'RecursionLimit')

也可以按需要调整，例如：

oldLimit = get(0, 'RecursionLimit');
set(0, 'RecursionLimit', 200);

RecursionLimit 是 MATLAB 对递归深度的运行时限制设置，不是对输入规模的通用安全保证。提高它不等于程序就能安全完成：深层调用仍会消耗资源，而且递归函数可能因错误逻辑永远无法终止。将限制调低也不能修复逻辑缺陷，只会让过深调用更早失败。

修改前应先确认自己的算法确实需要相应深度，并在受控环境中测试；脚本或程序若修改了全局根对象属性，应考虑在结束时恢复原值，避免影响同一 MATLAB 会话中的其他代码。对于预计可能产生很深调用链、或递归深度与输入规模线性增长的问题，通常应评估改用循环、显式栈或其他算法，而不是单纯提高限制。

具体能达到的调用深度还会受到 MATLAB 版本、每层调用的内容和可用系统资源等因素影响。不要把某个环境中的实测深度当作所有机器和版本都适用的保证。尤其不要依赖“刚好接近限制”的输入规模作为算法设计边界。

九、什么时候适合用递归，什么时候改用循环

递归比较适合以下情况：

• 问题定义本身具有递归结构，例如树的子树、嵌套表达式或分治问题。
• 子问题的数量和规模容易描述，基例清晰，调用深度通常可控。
• 递归写法能显著简化逻辑，且性能测试表明符合需求。

若递归只是在反复做简单计数或顺序处理，循环通常更直观，也便于控制内存和执行过程。需要深度优先遍历时，可以用显式栈模拟调用过程；这样调用状态存放在程序管理的数据结构中，便于检查和控制，但并不会自动减少问题本身所需的工作量。对于分治算法，还应检查子问题是否重复计算；必要时可使用记忆化或动态规划，避免指数级重复工作。

另一个常见误区是默认 MATLAB 会把尾递归自动转换成循环。编写 MATLAB 代码时，不应依赖尾递归优化来消除调用栈开销；如果深度可能很大，应根据实际调用限制和性能测试选择循环或显式数据结构。

十、递归与安全：不要把它当作防护机制

递归是一种控制流程组织方式，不是安全边界，也不是沙箱。它不会自动验证输入，不会隔离文件、网络或系统操作，也不会阻止恶意或异常输入造成过多计算。若递归函数的输入来自外部文件、用户提交内容或网络数据，应在入口处限制类型、形状、范围和规模，并对调用深度、运行时间和内存消耗作出合理控制。

在解析嵌套数据时，除了检查递归深度，还应考虑循环引用、超长链、极宽分支和重复子问题。仅设置 MATLAB 的递归限制，不能替代对数据结构的验证；仅捕获递归错误，也不能保证函数执行期间没有产生其他影响。需要处理不可信输入时，应把数据校验和资源控制纳入整体设计，并避免让递归代码直接执行输入中包含的命令或表达式。

十一、调试与测试建议

递归函数的测试应覆盖的不只是一个“正常输入”。至少检查以下类型：

• 最小合法输入：例如阶乘的 0、单节点树。
• 边界输入：例如空向量、单元素区间、叶节点。
• 普通输入：确认逐层拆分和返回结果正确。
• 非法输入：负数、非整数、错误形状或不满足排序前提的数据。
• 较大输入：观察运行时间、调用深度和内存开销是否在可接受范围内。

可以在递归调用前后临时加入 disp 或断点，打印当前参数和层级，观察调用怎样展开和返回；调试完成后应移除不必要的输出，以免大量递归日志拖慢运行。必要时可增加一个显式的深度参数用于诊断，但该参数不能代替算法本身的停止条件。

编写完成后，逐条回答三个问题：基例覆盖了哪些输入？每次递归如何缩小问题？是否存在任何输入会绕开基例或导致重复访问？能清楚回答这三点，递归逻辑通常就有了可验证的基础。

总结

MATLAB 递归函数通过一层层函数调用拆解问题，并在基例处停止，再沿调用链返回结果。可靠实现需要同时满足三点：基例明确且可达，递归步骤持续缩小问题，输入限制与算法前提得到检查。还要考虑 MATLAB 的 RecursionLimit、每层调用带来的资源开销，以及递归是否会重复计算或遇到循环结构。

当问题结构适合递归、深度可控且代码更易理解时，递归是有效的表达方式；当调用链可能很深、资源难以预测或循环更直接时，应比较迭代实现、显式栈和动态规划等方案。不要通过盲目提高递归限制来掩盖终止条件错误，也不要把递归当作对不可信输入的安全防护。