有人可以解释一下这种类型的递归是如何工作的吗? [英] Can someone please explain me how this type of recursion works?

问题描述

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

I came across this problem in recursion. I can't figure out how it works. I understand the basics of recursion but this totally confuses me. Please help.

main() { 
    foo(3); 
}

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

我以为这个程序不会打印任何东西，但它会打印 0120 .

I thought this program wouldn't print anything but it prints 0120 .

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

Doesn't the first call to foo(--3) i.e foo(2) jump to the beginning of the function and recur till 3 decrements to 0?

请解释这是如何工作的.

推荐答案

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

The first call to foo() can be explained using a recursion tree:

  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.最后得到输出:

First, the left sub-tree will be evaluated and will print 012 and then the right sub-tree will be evaluated and will print 0. Finally you get the output:

0120

这篇关于有人可以解释一下这种类型的递归是如何工作的吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！