递归追踪逻辑疑问：为何递归调用耗时标注为T(n-1)而非T(n)

你对时间复杂度函数T(n)的概念理解存在偏差，该讲解的标注是正确的。
首先明确核心定义：T(k)表示该递归函数接收输入规模为k的参数时，完整运行的总耗时，它不是函数本身的固定耗时属性，数值会随输入规模的变化而变化。

具体到递归标注的逻辑：

• 外层标注的T(n)，指代当前递归函数接收输入规模为n的参数时，整体运行的总耗时
• 函数内部调用同一个递归函数时，传入的参数规模已经缩减为n-1，这个子调用的运行耗时自然对应输入规模为n-1时的耗时T(n-1)，而非T(n)

举个简单的递归阶乘示例更易理解：
假设我们实现递归函数fact(k)用于计算k的阶乘，逻辑为k * fact(k-1)，边界条件为k=1时返回1：

• 输入k=5时，完整运行fact(5)的总耗时为T(5)
• fact(5)内部调用的是参数为4的fact(4)，这个子调用的耗时就是T(4)
• 以此类推即可得到递推式：T(n) = 常数级运算耗时 + T(n-1)，和参考图中的标注逻辑完全一致。

内容的提问来源于stack exchange，提问作者NAMAN VERMA