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

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

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 

Answer 2

所以foo（3）是：

 foo(2) print 2 foo(1) 

foo（2）是：

 foo(1) print 1 foo(0) 

foo（1）是：

 foo(0) print 0 foo(-1) 

现在foo（0）和foo（-1）都是no-ops，所以foo（1）是：

 print 0 

从那以后foo（2）是：

 print 0 print 1 

foo（3）是：

 print 0 print 1 print 2 print 0 

这为您提供了观察到的输出。

Answer 3

这是预期的产出。 下一个函数调用被推送到堆栈，并且在前一个函数调用返回之前不会执行printf语句。

 foo(3) --> foo(2) --> foo(1) --> foo(0) 

现在x不是> = 1，所以不再有函数调用，而foo（0）会弹出堆栈。 执行来自foo（1）的printf语句，0（因为x值递减）转到stdout。 另一个foo（）调用：

 foo(3) --> foo(2) --> foo(1) --> foo(-1) // ^^ second foo() call from foo(1) 

当前输出：

 0 

这没什么。 foo（-1）和foo（1）弹出堆栈。
现在printf从foo（2）调用，1进入stdout。

叫foo（0）。

 foo(3) --> foo(2) --> foo(0) // ^^ second foo() call from foo(2) 

当前输出：

 01 

foo（0）什么也不做，然后pop的foo（0）和foo（2）。

现在我们在foo（3）。 打印2并调用foo（1）。

 foo(3) --> foo(1) // ^^ second foo() call from foo(3) 

当前输出：

 012 

foo（1）调用foo（0）然后打印0然后调用foo（-1）。 现在所有剩余的foo都弹出了堆栈，输出时得到0120。

@haccks – 看这个程序。 有调用foo（-1）。

 #include  void foo(int); int main() { foo(3); return 0; } void foo(int x) { if (x >= 1) { printf("executing foo with x = %d\n",x-1); foo(--x); printf("original output: %d\n", x); printf("executing foo with x = %d\n",x-1); foo(--x); } } 

输出：

 executing foo with x = 2 executing foo with x = 1 executing foo with x = 0 original output: 0 executing foo with x = -1 original output: 1 executing foo with x = 0 original output: 2 executing foo with x = 1 executing foo with x = 0 original output: 0 executing foo with x = -1