Big Theta (Θ) время работы рекурсивных функций

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 и распечатать результат

Bar делает то же самое без печати, только декремент и вызов Foo

Это уровень 3 рекурсии, попробуйте использовать небольшое количество и следовать за потоком, как 4

-бара получает 4, корпус базы он равен 0, 4 больше 0, поэтому он будет продолжаться, он вызовет foo (4) (rem что foo - это рекурсивный вызов, который будет печатать от 4 до 0 =>, каждый раз уменьшая число на 1) -And bar снова вызывается, на этот раз с n-1 = 4 -1 = 3, со значением 3 , он назовет foo (3) и тот же

Когда вы встретите базу данных в баре, 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; 
}