谁能解释一下这个递归代码到底是如何工作的，以及程序堆栈或内存中一步一步发生了什么？

Question

关闭。这个问题需要多问 focused 。目前不接受答案。

---

想要改进此问题吗？更新问题，使其仅关注一个问题 editing this post .

已关闭 7 年前。

Improve this question

这是我的代码:

#include <stdio.h>

void fun(int n)
{
    if(n > 0)
    {
        fun(n-1);
        printf("%d ", n);
        fun(n-1);
    }
}

int main()
{
    fun(4);
    return 0;
}

这段代码的输出是1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 。但我无法理解递归调用之间到底发生了什么，何时执行 print 语句以及 n 的值是多少每次通话时。我是编码初学者，请逐步解释。

Answer 1

如果您从更接近递归基本情况的情况开始，就会更容易理解正在发生的情况。假设您的 main 中有 fun(0)。在 fun 的主体内会发生这种情况:

void fun(int n)
{
    if(n > 0) //this is false, so function does nothing
    {
        fun(n-1);
        printf("%d ", n);
        fun(n-1);
    }
}

现在如果您的 main 中有 foo(1) 该怎么办？

void fun(int n)
{
    if(n > 0) //this is true, lets execute the block
    {
        fun(n-1); //call fun(0), this does nothing
        printf("%d ", n); //print value 1
        fun(n-1);//call fun(0) again, does nothing
    }
}

所以你可以看到 fun(1) 将打印值 1，fun(2) 怎么样？

void fun(int n)
{
    if(n > 0) 
    {
        fun(n-1);        //call fun(1), prints 1
        printf("%d ", n);//print value 2
        fun(n-1);        //call fun(1), prints 1
    }
}

如您所见，foo(2) 将打印“1 2 1”，类似地 foo(3) 将打印 1 2 1 3 1 2 1

堆栈如何建立和展开非常有趣，您应该坐下来拿着笔和纸弄清楚这一点。

这称为纯结构递归，递归的每一步都更接近基本情况。