为什么理解这个递归示例如此难以凭直觉？

Question

我很难理解这段代码。我完全理解为什么 foo() 打印这些值，但我无法理解为什么 bar() 反向打印这些值。任何人都可以请无论如何解释这一点，以便我可以直观地感受到它，或者至少给我一个方向以达到赦免。

#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. 你往下一层
3. 返回后再次打印 n

因此，“单一级别”的输出将是（例如 for 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

您是否尝试过在调试器中运行该程序？它将显示流程永远不会到达 bar 函数，直到 foo 函数被递归调用 11 次。该点的“堆栈”包含指向 bar 函数的指令指针的 10 个实例以及 a 的本地值。堆栈从下往上展开（堆栈 = LIFO 后进先出）。那有意义吗？

如果没有，那么一定要在调试器中运行它，同时观察堆栈值（指令指针和局部变量）。