递推关系T(n)=T(T(n-1))+1的求解及对应算法时间复杂度计算

首先结合运行结果验证可得，该递推存在通用解：T(n) = n。
验证逻辑：
你给出的代码中边界存在笔误（若严格按n<1返回1的逻辑，n=1会触发无限递归），结合运行结果Algo(3)=3，修正边界为T(0)=0后代入递推式：
右边 = T(T(n-1)) + 1 = T(n-1) + 1 = (n-1) + 1 = n = 左边，完全匹配。

我们用函数调用次数衡量时间复杂度（每次调用对应一次printf，和运行结果的打印数量完全对应），设C(n)为调用Algo(n)的总次数：

• 每次调用Algo(n)，首先计入自身1次调用
• 接着需要先调用Algo(n-1)获取返回值，计入C(n-1)次调用
• 再将上一步的返回值作为参数调用Algo，因为已经证明返回值为n-1，所以再计入C(n-1)次调用

因此得到调用次数的递推式：

C(n) = 2*C(n-1) + 1

边界条件C(1)=1（n=1时直接返回，仅1次调用），解该递推式：
两边加1得 C(n) + 1 = 2*(C(n-1) + 1)，这是首项为C(1)+1=2的等比数列，通项为C(n) +1 = 2^n，即C(n) = 2^n -1。
你给出的n=3的运行结果对应调用次数为2^3 -1=7，和打印的节点数量完全匹配。

最终该算法的时间复杂度为 O(2ⁿ)，属于指数级复杂度。

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