Why is understanding this recursion example so difficult to put into intuition?

Question

I have difficulties to understand this code. I can fully understand why foo() is printing that values but I just can't get my head around why bar() is printing those in reverse. Can anyone please anyhow explain this so that I can feel it intuitively or at least give me a direction where to go for to reach the absolution.

#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

Recursion is best understood if you don’t try to „run the whole callstack in your head“. Think in abstractions:

1. You print n
2. You go one level down
3. After you return you print n again

As such the output of a "single level" would be (e.g for foo(10)):

Foo 9
output of foo(9)
Bar 9

Resolving one more level by filling in the partial output of foo(9)

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

This pattern continues until we reach the end of recursion.

The code might look like it is sequential foo();bar(); (which it is) but foo() first descents which leads to bar() being called just before ascending the callstack.