这个递归函数的Big theta运行时间

Question

我需要一点帮助来弄清楚这个函数的Big-Theta运行时间。

int recursive(int n) { 

    sum = 0; 
    for (int i = 1; i <= n; i++) 
     sum++ 
    if (n > 1) 
     return sum + recursive(n-1); 
    else 
     return n; 
} 

我知道这个功能的运行时间是如何会是什么，如果在函数中的for循环是不大，但是环扔我了一点点。有什么建议？

Answer 1

• 如果只是for循环，而不是递归，则函数将是O(n)。
• 如果它只是递归的，并且没有for循环，它也将是O(n)。
• 但是，它做n递归步骤（我们知道这是O(n)）和它有在每个n步骤的O(n)for循环。

所以......有帮助吗？