Рекурсия на C++, что возвращение обратной

Question

Вот код:

#include <iostream> 
using namespace std; 
void countdown(int n); 

int main(){ 
    countdown(4); // call the recursive function 
    return 0; 
} 

void countdown(int n){ 
    cout << n << endl; 

    if (n > 0){ 
     countdown(n-1); // function calls itself 
    } 

    cout << n << endl; // intended part of code 
} 

Простой запуск:

4 
3 
2 
1 
0 
0 
1 
2 
3 
4 

Вопрос: почему это рекурсивная функция рассчитывает обратно от 0 до 4, и не останавливаться на 0?

Answer 1

Поскольку вызов функции рекурсии хранится в стеке. Таким образом, когда один вызов функции возвращается, он выплывает из стека, а затем он выполняет следующую строку вызова функции.

void countdown(int n){ 
cout << n << endl; // This line calls 4 3 2 1 0 

if (n > 0){ 
countdown(n-1); // function calls itself 
} 

cout << n << endl;; //This line print 0 1 2 3 4 
} 

Пусть числа до строки кода являются номера строк:

1 void countdown(int n){ 
2 cout << n << endl; // This line calls 4 3 2 1 0 

3 if (n > 0){ 
4 countdown(n-1); // function calls itself 
5 } 

    6 cout << n << endl;; //This line print 0 1 2 3 4 
    7 } 

Suppose countdown is called with n = 2, 
Then, Your stack will initially contain function call with n = 2. 
Because of line 2, 2 gets printed. 
Because of line 4, function with n = 1 gets called. So, now stack has 1|2 
Now because of line 2 again, 1 gets printed. 
Because of line 4, function with n = 0 gets called. So Now stack is 0|1|2 
Line 2 prints 0. 
Line 3 condition fails and so line 4 is not executed. 
Line 6 prints 0. 
Line 7 tells that function execution is over and hence it will pop out of stack. Now stack is 1|2. 
Now, function with n = 1 resumes its operation from line 5. 
So, line 6 makes it print 1. 
line 7 tells that function execution is over and hence it will pop out of stack. Now stack is 2. 
So, function with n =2 resumes its operation from line 5. 
line 6 makes it print 2. 
line 7 tells function execution is over and hence it will pop out of stack. And now it will return to main. 

Answer 2

У вас есть две выходные линии. Удалите последние cout << n << endl. Последняя строка - это то, что подсчитывается, после возвращения из рекурсивного вызова.

Answer 3

Вы печатаете n дважды - перед вызовом функции рекурсивно, а затем снова после того, как он возвращается. Если вы хотите, чтобы напечатать номер отсчет, просто напечатать его один раз:

void countdown(int n) { 
    cout << n << endl; 
    if (n > 0){ 
     countdown(n-1); 
    } 
    // Another cout call was removed here... 
} 

Answer 4

из второго соиЬ только до конца функции coutdown

Answer 5

положить его очень просто, вызов функции - даже ваша собственная функция - не завершает выполнение текущей функции. Рассмотрим следующее:

void countdown() { 
    std::cout << countdown << "\n"; 
} 

int main() { 
    countdown(); 
    std::cout << "main\n"; 
} 

вы не были бы удивлены, что это печатает

countdown 
main 

Также вы будете удивлены, если Вы писали:

int main() { 
    int i = 0; 
    if (i == 0) 
     countdown(); 
    std::cout << "main\n"; 
} 

Мы можем также просто показать, что рекурсивный функция обратного отслеживания через его пункты вызова следующим образом:

#include <iostream> 

void countdown(int n) { 
    std::cout << "countdown(" << n << ") entry\n"; 
    if (n == 0) 
     countdown(n + 1); 
    std::cout << "countdown(" << n << ") exit\n"; 
} 

int main() { 
    std::cout << "main entry\n"; 
    countdown(0); 
    std::cout << "main exit\n"; 
} 

live demo

выходы:

main entry 
countdown(0) entry 
countdown(1) entry 
countdown(1) exit 
countdown(0) exit 
main exit