遞歸函數的大θ（Θ）運行時間

Question

我無法理解運行時。任何幫助將非常感激！

int foo(int x) { 
    if (x <= 0) return x; 
    cout << x; 
    return foo (x-1); 
} 

void bar(int n) { 
    if (n <= 0) return; 
    cout << foo (n) << endl; 
    bar (n-1); 
    cout << n; 
} 

int main() { 
int n; 
cin >> n; 
bar(n); 
return 0; 
} 

Answer 1

foo是打印你經過數，它會做x--直至爲0，如果傳遞5它將打印，這樣就可以把它稱爲減1 n和打印結果

酒吧在做同樣的不打印，僅遞減和調用foo

這是一個3遞歸級別，儘量使用小數目，並按照流程，像4

-Bar得到4，案例庫它是0,4是大於0所以它會繼續，它會調用foo（4）（rem enber foo是一個遞歸調用，將打印4到0 =>，每次遞減1） - 再次調用bar，這次使用n-1 = 4 -1 = 3，值爲3 ，它會調用foo（3）和相同的

當你在bar中遇到case base時，n == 0你將停止調用其他函數，這個函數將得到返回的值，你可以在screnn上打印它，但它並不意味着該函數結束，它正在等待其他值返回，當它返回時它打印調用它的n，所以它將是1234，也就是說，值1,2,3和4是值一次輸入一個條並打印foo的結果的值（對於4,3,2,1），因爲它是您所得到的

int foo(int x) { //Decrementing by one and printing the value 
    // If x reaches 0 exit (you need an exit in a recursion) 
    if (x <= 0) return x; 
    // Print the value x (the first time x will be the n, the second n-1) 
    cout << x; 
    // Call the same function in we are but with x-1 value 
    return foo (x-1); 
} 
// It will produce foo(4)=>foo(3)=>foo(2)=>foo(1) and foo(0) 
// foo(0) will break the recursion and finish here (only prints) 

// It is where main calls and enters n is the value you type 
void bar(int n) { 
    // Case base to break recursion when it reaches 0 
    if (n <= 0) return; 
    // Here is the code that prints the line that foo will make 
    cout << foo (n) << endl; 
    // Here you will call the same function but with n-1, like foo does 
    bar (n-1); 
    // When all the recursion above is over you will get here 
    // In the stack you will have done n calls into here with n-x 
    // So every one will print the value of n that in the paremeter 
    // when the call was make 
    cout << n; 
}