数据结构与算法 / 系统课时

递归的调用模型

递归的调用模型

递归函数会先沿着更小的子问题不断展开,再按相反顺序返回并组合结果。本课通过阶乘的调用轨迹说明终止条件、栈帧、返回顺序,以及递归深度为何会直接影响空间消耗。

学习目标

  • 识别递归函数的终止条件、推进过程与结果组合
  • 按顺序分析调用展开和返回过程
  • 估算递归的时间复杂度与调用栈空间

递归如何执行

一个正确的递归函数通常包含三部分:终止条件给出最小问题的直接答案;递归推进把当前问题转成更小的同类问题;结果组合在子调用返回后构造当前结果。推进过程必须持续接近终止条件,否则会无限递归。

以 factorial(4) 为例,程序先依次调用 factorial(3)、factorial(2) 和 factorial(1)。到达终止条件后,返回值再按相反顺序计算为 1、2、6、24。调用方向与返回方向相反,是理解递归的关键。

递归调用栈展开与返回

栈帧与空间开销

每次函数调用都会创建独立栈帧,用来保存本次参数、局部变量、返回地址和尚未完成的操作。factorial(4) 等待子调用时,必须保留参数 4,并记住返回后还要乘以 4;因此上层调用不会在进入下一层后消失。

当最大递归深度为 nn 时,调用栈通常需要 O(n)O(n) 额外空间。即使代码没有显式创建数组或集合,也不能据此判断空间复杂度为 O(1)O(1)。递归过深还可能超过语言运行时的栈深度限制。

主示例

下面的 Java 程序在进入和返回每一层时打印日志,以便观察两个方向。

java
public class RecursionCallModelDemo {

    public static void main(String[] args) {
        int n = 4;
        int result = factorial(n);
        System.out.println("factorial(" + n + ") = " + result);
    }

    private static int factorial(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("n must be non-negative");
        }

        System.out.println("enter n = " + n);

        // 0! 和 1! 都是最小问题,直接返回 1。
        if (n <= 1) {
            System.out.println("return n = " + n + ", value = 1");
            return 1;
        }

        int childResult = factorial(n - 1);
        int result = n * childResult;
        System.out.println("return n = " + n + ", value = " + result);
        return result;
    }
}

编译并运行:

bash
javac RecursionCallModelDemo.java
java RecursionCallModelDemo

预期输出:

text
enter n = 4
enter n = 3
enter n = 2
enter n = 1
return n = 1, value = 1
return n = 2, value = 2
return n = 3, value = 6
return n = 4, value = 24
factorial(4) = 24

复杂度与正确性检查

阶乘每层只产生一个规模减一的子调用,共调用 nn 次,因此时间复杂度为 O(n)O(n),栈空间为 O(n)O(n)。对分支递归,不能只看深度,还要计算每层产生的调用数量;例如朴素斐波那契会重复计算大量相同状态。

检查递归时,可依次确认函数语义是否固定、参数是否单调接近终止条件、最小输入是否被覆盖、返回值是否正确组合。公共入口还应负责拒绝非法输入,避免递归逻辑承担无关职责。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

递归的调用模型

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通