Почему понимание этого примера рекурсии так сложно воплотить в интуицию?

Question

Мне сложно понять этот код. Я полностью понимаю, почему foo () печатает эти значения, но я просто не могу понять, почему bar () печатает их в обратном порядке. Может кто-нибудь, пожалуйста, как-нибудь объяснить это так, чтобы я мог чувствовать это интуитивно или, по крайней мере, дать мне указание, куда go, чтобы достичь отпущения грехов.

#include<iostream>
using namespace std;

void bar(int a){
    cout<<"bar: "<<a<<endl;
}

void foo(int a){
    if(a>0){
        a -=1;
        cout<<"foo: "<<a<<endl;
        foo(a);
        bar(a);
    }else{
        cout<<"Foo exited"<<endl;
    }
}

int main(){
    foo(10);
}

[Output]:
foo: 9
foo: 8
foo: 7
foo: 6
foo: 5
foo: 4
foo: 3
foo: 2
foo: 1
foo: 0
Foo exited
bar: 0
bar: 1
bar: 2
bar: 3
bar: 4
bar: 5
bar: 6
bar: 7
bar: 8
bar: 9

Answer 1

Рекурсию лучше всего понимать, если вы не пытаетесь «запустить весь колл-стэк в своей голове». Представьте себе абстракции:

1. Вы печатаете n
2. Вы go на один уровень вниз
3. После возвращения вы печатаете n снова

Таким образом, выход «одного уровня» будет (например, для foo(10)):

Foo 9
output of foo(9)
Bar 9

Устранить еще один уровень, заполнив частичный вывод foo (9)

Foo 9
Foo 8
output of foo(8)
Bar 8
Bar 9

Этот паттерн продолжается до тех пор, пока мы не достигнем конца рекурсии.

Код может выглядеть как последовательный foo();bar(); (который он есть), но foo() первый спуск, который приводит к bar() существованию вызывается непосредственно перед подъемом стека вызовов.

Answer 2

Вызовы следующие (ограничены 5 уровнями):

foo(5)
    foo(4)
        foo(3)
            foo(2)
                foo(1)
                    foo(0)
                    bar(0)
                bar(1)
            bar(2)
         bar(3)
     bar(4)
bar(5)

Answer 3

Это все из-за стека (который является тезкой этого сайта, кстати). Стек - это то, как язык программирования знает, как вернуться туда, где он был после выхода из функции (или метода или подпрограммы и т. Д. c ...). Каждый вызов функции добавляется (помещается в) в стек (вместе с параметрами, передаваемыми в функцию ... здесь это не важно). Стек - это две вещи, это и имя объекта, содержащего данные, и имя класса, который их определяет (что будет важно узнать позже). Значение, добавленное в стек, является указателем на то, откуда был сделан вызов; просто чтобы прояснить, это указывает не на определение функции, а на строку, вызвавшую функцию. Когда программа возвращается из этих функций (поскольку вы использовали return или подразумеваемый возврат прямо перед фигурными скобками), она извлекает стек, чтобы она знала, куда переместить указатель инструкции на следующую.

В вашем примере, foo () помещается в стек 11 раз (в последний раз, когда он просто печатает выходную строку), прежде чем bar () вообще помещается, потому что bar () следует после foo () и foo. () вызывается второй раз (и третий вызов, четвертый вызов и т. д.) перед вызовом первого бара (). Каждый из этих вызовов будет увеличивать и выводить значение, а затем pu sh еще один foo () в стеке. После того, как все функции foo () были вызваны, но до того, как какой-либо из них был удален из стека, функция foo () выполняет каждый pu sh bar () в стеке (это следующая строка после рекурсивной строки), подождите для бара (n) до fini sh, а затем они выходят, что приводит нас к предыдущей рекурсии. Поскольку эти функции foo () были помещены в стек в прямом порядке, и они рекурсивно перед вызывают bar (), они извлекают bar () из стека в обратном порядке (помните, что стек является данными FILO структура). Вот почему он, кажется, ведет обратный отсчет; хотя на самом деле это просто показывает результаты в обратном порядке. Кстати, bar () не обязательно должен существовать, чтобы это работало так: вы могли бы просто добавить cout сразу после рекурсивного вызова foo (), и он бы работал так же.

Каждый раз, когда вы делаете рекурсию, вы должны думать о стеке, потому что он быстро заполняется, и когда это происходит, ваша программа обработает sh. Это cra sh на самом деле хорошая вещь, потому что в противном случае все приложение просто зависнет. Это звучит не намного лучше, но позволяет вам начать жить раньше, так что это здорово. Кроме того, вы, вероятно, обнаружите, что избегать того, что здесь происходит, обычно хорошо, если только вы не хотите, чтобы bar () вызывалась в обратном порядке foo (). В общем, гораздо проще следовать рекурсии, если рекурсия находится в конце рекурсивной функции, когда это возможно.

Answer 4

Представьте себе, что вызовы выполняются для различных функций, а затем, какая функция сначала попадает в строку cout<<"foo: "<<a<<endl;? И какая из этих мнимых функций сначала вызывает bar()?

Первый вызов вызывает только bar() после того, как все остальные вызовы уже возвращены!

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

void foo(int a){
    if(a>0){
        a -=1;
        cout<<"foo: "<<a<<endl;
        // foo(a); // inline this...
        if(a>0){
            a -=1;
            cout<<"foo: "<<a<<endl;
            // foo(a); // inline this again
            if(a>0){
                a -=1;
                cout<<"foo: "<<a<<endl;
                foo(a); // and turtles all the way down...
                bar(a);
            }else{
                cout<<"Foo exited"<<endl;
            }
            bar(a);
        }else{
            cout<<"Foo exited"<<endl;
        }
        bar(a);
    }else{
        cout<<"Foo exited"<<endl;
    }
}

Answer 5

Вы пробовали запустить программу в отладчике? Было бы показано, что поток никогда не достигнет функции бара, пока функция foo не была вызвана рекурсивно 11 раз. «Стек» в этой точке содержит 10 экземпляров указателя инструкций, указывающих на функцию бара, а также локальные значения a. Стек разматывается снизу вверх (стек = LIFO последним первым вышел). Имеет ли это смысл?

Если этого не произойдет, то непременно запустите его в отладчике, следя за значениями стека (указатель инструкции и локальные переменные).