无终止递归函数为何存在时间复杂度？CLRS习题4.4-8递归式分析疑惑

这问题的核心是：你把CLRS里的数学递归式和没有终止条件的实际代码递归函数搞混了——教材里的递归式默认带有隐含的基准情形，你没意识到这一点，才会觉得矛盾。

先纠正递归树的错误 #

你画的递归树里把T(a)继续展开成T(0)和T(a)，这是错的！在算法教材的递归式约定里：

• 当输入规模小到某个阈值时（这里就是n ≤ a），T(n)是常数时间（Θ(1)），不会再进行递归调用。
• 也就是说，T(a)本身就是基准情形，它的时间复杂度是常数，不会再调用自己。

为什么O(n²)的证明是对的？ #

补上这个隐含的基准情形后，递归树的结构就完全合理了：

• 主分支是n → n-a → n-2a → ... → 最后一个≤a的节点，总共有n/a层左右
• 每一层的时间代价依次是cn, c(n-a), c(n-2a), ..., c*a，这是一个等差数列
• 把所有层的代价加起来，总和是c * (n/a) * (n+a)/2，显然属于Θ(n²)，所以渐近紧确解是O(n²)（同时也是Ω(n²)）

关于“无限递归”的疑问 #

如果真的完全不考虑基准情形，那这个递归式确实会无限循环，时间复杂度是O(∞)——但这不是原题要表达的意思！

CLRS里的递归式是用来描述能正常终止的算法的时间复杂度，所以必然隐含了终止条件。你相当于给原题加了一个“没有基准情形”的额外假设，这就偏离了题目设定。

最后再明确一遍 #

• 教材中的递归式默认有基准：n ≤ a时，T(n)=Θ(1)，停止递归
• T(a)是终止节点，不是递归调用，你的递归树画错了
• O(n²)是基于正确设定的结论，和你假设的“无限递归”情况不冲突

内容的提问来源于stack exchange，提问作者Viktor Skarve