以下代码的递归关系是什么：

Question

代码如下：

static void fun1(int n)  
{  
   int i = 0;    
   if (n > 1)  
     fun1(n - 1);  
   for (i = 0; i < n; i++)  
     System.out.print(" * ");  
}

我的回答是：

T(n) = { n + 2          : if n <= 1
       { T(n-1) + n + 2 : if n > 1

基本情况包含一项赋值和一项比较（均在常数时间内）以及在线性时间内运行的 for 循环。

递归情况与基本情况相同，递归调用T(n-1)。

这就是为什么我认为我是正确的，但这个问题没有答案，因此不胜感激。

Answer 1

你的回答是正确的，但可以写得更笼统，像这样:

T(n) = T(n-1) + n + const, if n > 1
T(n) = n + const, if n <= 1

这里 const 通常选择值 1，以便于计算，因为这对时间复杂度没有影响。