這個遞歸函數的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循環。

所以......有幫助嗎？