递归函数的大θ（Θ）运行时间

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; 
}