Big Theta (Θ) время выполнения рекурсивных функций
У меня проблемы с попыткой понять время выполнения. Любая помощь приветствуется!
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;
}
Решение
Foo печатает число, которое вы передаете, и будет делать x—, пока не станет 0, если вы передадите 5, оно напечатает 543210, так что вы можете назвать его декрементом n на 1 и распечатать результат
Бар делает то же самое без печати, только уменьшая и вызывая foo
Это 3 уровня рекурсии, попробуйте использовать небольшое число и следовать за потоком, как 4
-Bar получает 4, регистр основания равен 0, 4 больше 0, поэтому он будет продолжен, он вызовет foo (4) (напомним, что foo является рекурсивным вызовом, который выведет 4 в 0 => 43210, уменьшив число на 1 каждый раз)
-А бар вызывается снова, на этот раз с n-1 = 4 -1 = 3, со значением 3 он вызовет foo (3) и тот же
Когда вы встретите базу case в баре, n == 0, вы перестанете вызывать другие функции, и эта функция вернет возвращаемое значение, вы можете напечатать в screnn, но это не означает, что функция завершается, она ожидала, пока другие значения return, когда он возвращает, он печатает 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;
}
Другие решения
Других решений пока нет …
detector