题目

求整数 n(n≥0) 阶乘的算法如下，其时间复杂度是（ ）。

int fact(int n) {
    if (n <= 1) return 1;
    return n * fact(n - 1);
}

错因

A

把"递归"和"对数复杂度"画等号了。 的递归对应"每次递归把问题规模减半"——比如二分查找 mid = (lo+hi)/2，每层规模缩成原来的 1/2，递归深度只有 。

但本题 fact(n) = n * fact(n-1)，每次只把 减 1，递归深度是 n 不是 。规模"减一"和"减半"是两回事，前者线性、后者对数。

C

套用了"递归 + 内层循环"的归并排序模式（外层 次划分 + 内层 次合并 = ）。但本题里每次递归只做一次乘法 n * fact(n-1)，完全没有内层循环。只有真正存在两层（一层 、一层 ）才用得上 。

D

误以为"递归会指数爆炸"。 的递归对应"每层做 次工作 + 递归 层"，比如冒泡。

本题每层工作量只有 （一次乘法），递归层数 层，总开销是 ，不是 。

总解析

逐次展开递归调用：

共发生 次函数调用。每次调用内部只做 1 次比较（n <= 1）+ 1 次乘法 + 1 次返回，工作量是常数级 。

总时间复杂度 = 调用次数 × 每次工作量 = 。

关键区分（这是判断递归复杂度的核心）：

递归形式	每层规模变化	复杂度
f(n) → f(n-1)	减 1
f(n) → f(n/2)	减半
f(n) → f(n-1) + f(n-1)	减 1 但每层 2 倍调用
f(n) → 2 × f(n/2) + O(n)	减半 + 合并	（归并）

最终答案是 B。