有人可以解释一下这种类型的递归是如何工作的吗？

Question

我在递归中遇到了这个问题.我无法弄清楚它是如何工作的.我理解递归的基础知识但这完全让我感到困惑.请帮忙.

main() { 
    foo(3); 
}

void foo(int x) {
    if (x >= 1) {
        foo(--x);
        printf("%d", x);
        foo(--x);
    }
}

我认为这个程序不打印任何东西,但它打印0120.

是不是第一次调用foo( - 3)即foo(2)跳转到函数的开头并重复直到3递减到0？

请解释这是如何工作的.

Answer 1

第一次调用foo()可以使用递归树来解释:

  prints (in reverse order)

    2 <----------  foo(3)
                  /      \
    1 <----- foo(2)       foo(1) -----> 0
             /   \        /     \
    0 <-- foo(1) foo(0)  foo(0)  foo(-1)
         /    \ 
      foo(0)   foo(-1)

首先,将评估左子树并打印012,然后将评估右子树并打印0.最后你得到输出:

0120