基于递归树计算递归函数fun3的时间复杂度及树高（负输入场景）

咱们一步步拆解这个问题，先明确函数的行为，再用递归树法推导时间复杂度，最后说清楚递归树高度的计算逻辑。

首先看原函数代码：

public static void fun3(int i) { 
    if(i<10) { 
        fun3(i+1); 
        fun3(i+2); 
        System.out.println(i); 
    } 
}

当输入参数i为负数时，i < 10的条件会一直成立，直到递归参数增长到10及以上才终止（这里你提到的“i向负方向无限增长”应该是笔误，实际递归参数是越来越大的，直到触发终止条件）。你给出的递推式T(n)=T(n+1)+T(n+2)+O(9)可以简化为T(n)=T(n+1)+T(n+2)+O(1)（O(9)属于常数时间，等价于O(1)），其中T(n)代表输入为n时的时间复杂度；当n >=10时，T(n)=O(1)（不进入递归分支，仅做条件判断，时间固定）。

一、递归树的构建逻辑 #

以输入m（m <10，比如m=-2）为例，递归树的结构如下：

• 根节点：对应fun3(m)，时间消耗为O(1)
• 第一层子节点：fun3(m+1)和fun3(m+2)，共2个节点，每个消耗O(1)
• 第二层子节点：
  • fun3(m+1)的子节点是fun3(m+2)、fun3(m+3)
  • fun3(m+2)的子节点是fun3(m+3)、fun3(m+4)
• 以此类推，所有叶子节点都是fun3(k)（k >=10），这些节点不再递归，消耗O(1)

二、递归树高度的计算方法 #

递归树的高度指的是从根节点到最远叶子节点的路径边数。
对于输入m（m <10），最远的叶子节点出现在一直走+1分支的路径上：
m → m+1 → m+2 → ... → 9 → 10
这条路径需要走10 - m步（每步参数+1，从m到10总共需要10 - m次递增），所以递归树的高度为：

高度 = 10 - m

比如输入m=-2时，高度是10 - (-2) =12，对应路径从-2到10的12条边。

三、时间复杂度推导（递归树法） #

时间复杂度是递归树所有节点的时间消耗总和，每个节点的消耗都是O(1)，因此我们只需要统计总节点数的增长趋势。

观察节点数的规律：
设f(k)为输入k时的总节点数，那么递推关系为：

f(k) = 1 + f(k+1) + f(k+2) （1是当前节点，加上两个子树的节点数）
边界条件：f(k)=1 当 k >=10

这是反向的斐波那契递推，我们可以令d = 10 - k（d是正整数，代表输入k到终止条件的距离），则递推式变为：

g(d) = 1 + g(d-1) + g(d-2)
边界条件：g(0)=1（对应k=10），g(-1)=1（对应k>=11）

这个递推式的解和斐波那契数列直接相关，其增长速度是指数级的，具体为Θ(φ^d)，其中φ≈1.618是黄金分割比。

代入d=10 - m，总节点数的增长趋势为Θ(φ^(10 - m))，因此时间复杂度为：

O(φ^(10 - m)) （φ≈1.618）

当m是负数时，10 - m等于10 + |m|，所以时间复杂度也可以写成O((1.618)^(|m|))，本质是随着输入负数的绝对值增大，时间消耗呈指数爆炸。

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