数据结构与算法 / 系统课时
递归的调用模型
递归的调用模型
递归函数会先沿着更小的子问题不断展开,再按相反顺序返回并组合结果。本课通过阶乘的调用轨迹说明终止条件、栈帧、返回顺序,以及递归深度为何会直接影响空间消耗。
学习目标
- 识别递归函数的终止条件、推进过程与结果组合
- 按顺序分析调用展开和返回过程
- 估算递归的时间复杂度与调用栈空间
递归如何执行
一个正确的递归函数通常包含三部分:终止条件给出最小问题的直接答案;递归推进把当前问题转成更小的同类问题;结果组合在子调用返回后构造当前结果。推进过程必须持续接近终止条件,否则会无限递归。
以 factorial(4) 为例,程序先依次调用 factorial(3)、factorial(2) 和 factorial(1)。到达终止条件后,返回值再按相反顺序计算为 1、2、6、24。调用方向与返回方向相反,是理解递归的关键。

栈帧与空间开销
每次函数调用都会创建独立栈帧,用来保存本次参数、局部变量、返回地址和尚未完成的操作。factorial(4) 等待子调用时,必须保留参数 4,并记住返回后还要乘以 4;因此上层调用不会在进入下一层后消失。
当最大递归深度为 时,调用栈通常需要 额外空间。即使代码没有显式创建数组或集合,也不能据此判断空间复杂度为 。递归过深还可能超过语言运行时的栈深度限制。
主示例
下面的 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复杂度与正确性检查
阶乘每层只产生一个规模减一的子调用,共调用 次,因此时间复杂度为 ,栈空间为 。对分支递归,不能只看深度,还要计算每层产生的调用数量;例如朴素斐波那契会重复计算大量相同状态。
检查递归时,可依次确认函数语义是否固定、参数是否单调接近终止条件、最小输入是否被覆盖、返回值是否正确组合。公共入口还应负责拒绝非法输入,避免递归逻辑承担无关职责。
按自己的节奏,确认真正理解。