GESP 四级 · GESP 202312 C++ 四级 第 17 题

用递归法求 $n$ 的阶乘，时间复杂度是 $O(n)$。

这题核心就是数递归调用的次数。拿到题先想：递归定义是什么？从 n 到 1 中间会执行几次函数体？每次函数体里做了啥？把调用次数乘上单次操作耗时，就是总复杂度。别被阶乘结果那个巨大的数吓到，那是值，不是时间。

学生最容易把“阶乘的值”和“算阶乘花的时间”搞混。看到 n! 就下意识觉得是指数级，其实那是结果大小。另外，很多人一看到递归就脑补成指数爆炸，忘了看单次递归干了什么。如果单次是常数操作，哪怕递归很深，总时间也是线性的。还有一种坑是混淆时间复杂度和空间复杂度，空间确实是 O(n) 因为栈帧，但题目问的是时间，别把两个概念串一起就错了。

【考点】递归｜阶乘｜时间复杂度分析

这道题考查的是递归算法的时间复杂度计算，属于 GESP C++ 四级算法模块的基础内容。命题人特意选“阶乘”这个经典场景，就是为了区分考生是否真正理解“递归调用次数”与“单次递归耗时”这两个概念。

我们先回顾一下阶乘的递归定义：n! = n × (n-1)!，终止条件是 n=1 时返回 1。现在关键是数清楚：从 n 开始递归，一直到 1，中间一共执行了多少次函数体？答案是 n 次。因为每次调用都会把 n 减 1，从 n 到 1 正好 n 步，每步都进入了一次函数执行。

接下来看每次函数体里做了什么。函数体里只有一行乘法运算 n = n * n!，这是一个常数时间操作，记作 O(1)。既然一共调用了 n 次，每次都是 O(1)，那总时间就是 n × O(1) = O(n)。这就是递归复杂度分析的通法：总时间 = 调用层数 × 每层操作复杂度。

这里有个大坑：阶乘的结果 n! 本身是指数级增长的，但这和计算它需要多少时间完全是两码事。题目问的是“求阶乘”这个过程耗时多少，不是问“阶乘的值有多大”。很多同学看到 n! 就下意识觉得是指数级，把结果大小当成了时间复杂度，这是典型的混淆概念。

再补充一个细节：递归的空间复杂度确实是 O(n)，因为每层调用都要占一个栈帧，n 层就是 O(n)。但题目明确问的是时间复杂度，别把时间、空间串一起就错了。命题人还暗藏一个陷阱：如果你只背“递归就是指数级”这种结论而不理解本质，就会掉进这个坑。其实递归快不快，关键看单次递归干了什么。

如果题目改成“用迭代法求 n 的阶乘，时间复杂度是 O(n)？”，答案依然正确，因为迭代也是 n 次乘法。如果改成“递归求阶乘的空间复杂度”，那就变成 O(n) 了。刷到类似题先问自己：考的是时间还是空间？递归调用次数还是单次操作耗时？

【考频与趋势】 从题库数据看，“函数与递归”这个知识点在 GESP 四级里考过 26 题，是四级里考得最多的函数相关考点。逐年分布上，2023 年考了 13 题，2024 年 18 题，2025 年 21 题，呈现稳步上升趋势，说明命题组对递归的理解考察越来越重视。四级共考过 40 题，其中递归占了不小比例，属于高频常考点。

【预测】 基于数据趋势，未来 GESP 四级继续考递归相关题目概率很大，可能会在“递归复杂度分析”“递归与迭代的对比”“递归空间复杂度”等角度出题。但仅凭现有数据还不足以精准预测具体题型变化，暂无足够依据预测更细致的命题方向。