递归混淆

Question

大家好，我很难理解递归函数调用，就在我以为我已经理解它们的时候，我看到一个问题让我意识到我错了我无法理解程序的流程

#include <stdio.h>
void fun(int n)
{   
    if(n>0)
    {   
        fun(--n);
        printf("%d\n",n);
        fun(--n);
    }
}   
int main(void) {
    int a;
    a=3;
    fun(a);
    return 0;
}

Answer 1

我认为造成混淆的原因是您假设每次调用函数 fun() 都使用相同的 "n"。事实上，情况并非如此，因为在 C 语言中，参数是按值传递的。也就是说，当 fun(3) 调用 fun(2) 时，会创建一个新的 n - 特定于 fun(2) 的一个实例。因此，在 fun(2) 中调用 fun(3) 之后， n 的值是 2，而不是 -1。

因此您应该期待...

fun(1) 打印 0
fun(2) 打印 1
fun(3) 打印 2
fun(1)（从第二次调用 fun(2) 调用）打印 0

就是这样。

Answer 2

让我们试着用案例n=2来理解它，然后你应该能够概括。

fun (2):

里面发生了什么（流量）：

1) n=2: if(n>0) 为真，调用 fun(--n) 时 n 设置为值 1，原因是 --；（见下面的步骤）。

2) n=1: 现在 n=1：再次 if(n>0) 为真并且 fun(--n) 与 n=0 一起调用。请参阅下面的步骤。

3) n=0: 现在 n=0; if(n>0) 是假的，所以我们 return.

我认为这是你的困惑。从第 3 步开始，您 被抛回 在 第 2 步（不是第 1 步）。在 fun(--n) 调用之后，您实际上在第 2 步中被抛出 - 因此由于递减，printf 被调用的值为 n=0。然后再次在同一个地方（在 printf 之后）用值 n=-1 调用 fun(--n) 但是，它也会退出 - 最终你会在开始时被抛出。

Answer 3

这是当 n = 3

时对您的函数的函数调用

f(3)
.f(2) [1]
..f(1) [1]
...f(0) [1]
...Print 0
...f(-1) [2]
..Print 1
..f(0) [2]
.Print 2
.f(1) [2]
..f(0) [1]
..Print 0
..f(-1)[2]

其中.表示堆栈的深度，1和2指定是从循环还是第二次递归调用。

因为

f(3)

变成

f(2)
print 2
f(1)

这又变成了

f(1)
print 1
f(0)
print 2
f(0)
print 0
f(-1)

最后变成

f(0)
print 0
f(-1)
print 1
f(0)
print 2
f(0)
print 0
f(-1)

当 n <= 0

时删除所有 f(n)

print 0
print 1
print 2
print 0

Answer 4

程序的输出可以通过迭代扩展函数调用和删除条件来理解；以伪代码的方式，这可以按如下方式完成。

fun(3)

可以展开为以下

if(3>0)
{   
    fun(2);
    printf("%d\n",2);
    fun(1);
}

在接下来的步骤中，如果 if 条件的计算结果为 false，则省略该条件。

fun(1);
printf("%d\n",1);
fun(0);
printf("%d\n",2);
fun(0);
printf("%d\n",0);
fun(-1);

可以省略带有非正参数的对 fun 的调用，因为它们不会生成任何输出。

fun(1);
printf("%d\n",1);
printf("%d\n",2);
printf("%d\n",0);

进一步扩展产生以下序列。

fun(0);
printf("%d\n",0);
fun(-1);
printf("%d\n",1);
printf("%d\n",2);
printf("%d\n",0);

这可以再次简化为以下序列。

printf("%d\n",0);
printf("%d\n",1);
printf("%d\n",2);
printf("%d\n",0);

总的来说，输出如下。

我希望这能回答你的问题；但是，它没有提供一种直观的方式来描述生成的输出。

Answer 5

我会画一个 "call tree" 来帮助可视化程序。

函数有那些部分

decrement n, call, print, decrement n, call

现在你可以画这个了：

                  0                 -1
            1->0,   print 0, 0->-1,                   0
      2->1,                            print 1, 1->0,                 1->0, .....
3->2,                                                   print 2, 2->1, .....

从左下角开始，每次调用向上一行。程序从左到右执行，可以清楚的看到打印数字的顺序。

Answer 6

要了解递归流程，您可以使用如下所示的几个 printf 来检测您的代码。这将使用缩进显示功能流的顺序。

#include <stdio.h>

void printSpace(int num)
{
    while(num > 0)
    {
        printf(" ");
        num--;
    }
}

int NumSpace = 0;
void fun(int n)
{   
    printSpace(NumSpace);
    printf("fun(%d)\n", n);
    NumSpace += 4;
    if(n>0)
    {   
        fun(--n);
        printSpace(NumSpace);
        printf("%d\n",n);
        fun(--n);
    }
    NumSpace -= 4;
}   
int main(void) {
    int a;
    a=3;
    fun(a);
    return 0;
}


Result:
fun(3)
    fun(2)
        fun(1)
            fun(0)
            0
            fun(-1)
        1
        fun(0)
    2
    fun(1)
        fun(0)
        0
        fun(-1)

希望对您有所帮助。

Answer 7

这是发生了什么（伪代码）：

   n = 3
   fun(3);
      n = 2
      fun(2); // first fun(--n)
         n = 1
         fun(1); // first fun(--n)
            n = 0
            fun(0); // first fun(--n)
               return;
            print 0
            n = -1
            fun(-1); // second fun(--n)
               return;
            return;
         print 1
         n = 0
         fun(0); // second fun(--n)
            return;
         return;
      print 2
      n = 1
      fun(1); // second fun(--n)
         n = 0
         fun(0); // first fun(--n)
            return;
         print 0
         n = -1
         fun(-1); // second fun(--n)
            return;
         return;
      return;
   return;

Answer 8

尽可能避免递归代码。正如您通过这个简单的示例所看到的，理解程序的流程可能很困难。想象一下在非常复杂的代码中发现错误是什么感觉。对于那些认为这值得投反对票的人......在 20 年的 C 编码中，我发现很少有真正需要它的场合。

递归混淆

Recursive Confusion

c

recursion

function