了解递归和递减

Question

嗨有人可以解释这段代码吗？

#include <stdio.h> 

int main(){ 

    void myfunc(int x){ 
     printf (" [%d]",x); 
     printf ("M here 1\n"); 
     if (x > 0) myfunc(--x); 
     printf ("M here 2\n"); 
     printf (" %d,\n",x); 
    } 
    myfunc(5); 
} 

输出到来是：

[5]M here 1 
[4]M here 1 
[3]M here 1 
[2]M here 1 
[1]M here 1 
[0]M here 1 
0,M here 2 [0] 
0,M here 2 [1] 
1,M here 2 [2] 
2,M here 2 [3] 
3,M here 2 [4] 
4,M here 2 [5] 

不过，我被困在如何

0,M here 2 [0] 
0,M here 2 [1] 
1,M here 2 [2] 
2,M here 2 [3] 
3,M here 2 [4] 
4,M here 2 [5] 

是不是应该在

0,M here 2 [0] 

Answer 1

已停止难道它不应该存在吗？ pped at

不，不应该。递归调用返回后，函数继续执行该行之后的行。

---

让我们通过myfunc的excuction走路的时候输入是2。之后你可以推断它为更高的价值。当函数被调用时2，您可以：

printf (" [%d]",2); 
printf ("M here 1\n"); 
myfunc(1);    // Since 2 > 0 
printf ("M here 2\n"); 
printf (" %d,\n",1); // You get 1 here since x is decremented. 

当函数被调用时1，你

printf (" [%d]",1); 
printf ("M here 1\n"); 
myfunc(0);    // Since 1 > 0 
printf ("M here 2\n"); 
printf (" %d,\n",0); // You get 0 here since x is decremented. 

当函数被调用时0，你

printf (" [%d]",0); 
printf ("M here 1\n"); 
// No more recursion since the input is 0 
printf ("M here 2\n"); 
printf (" %d,\n",0); // You get 0 here since x is NOT decremented. 

现在，如果您将递归调用展平，您将获得：

printf (" [%d]",2); 
printf ("M here 1\n"); 

    printf (" [%d]",1); 
    printf ("M here 1\n"); 

     printf (" [%d]",0); 
     printf ("M here 1\n"); 
     printf ("M here 2\n"); 
     printf (" %d,\n",0); 

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

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

这很容易明白为什么会产生输出：

[2]M here 1 
    [1]M here 1 
    [0]M here 1 
M here 2 
    0, 
M here 2 
    0, 
M here 2 
    1, 

Answer 2

这里是你的代码，我只改在主函数传递给myfunc参数和标记不同的线路，以便更容易解释会发生什么情况：

#include <stdio.h> 

int main(){ 

    void myfunc(int x){ 
    printf (" [%d]",x);  // [1] 
    printf ("M here 1\n"); // [2] 
    if (x > 0)    // [3] 
     myfunc(--x);   // [4] 
    printf ("M here 2\n"); // [5] 
    printf (" %d,\n",x);  // [6] 
    } 

    myfunc(2);     // [7] 
} 

这是发生了什么事。在第一列中，代码的哪一行被执行，中间一列是执行的上下文，最后一行是当前上下文中的值x。

       Context    Value of x 

[7] Call myfunc(2)    Main function   N/A 
|        
+-> [1] print     1st call to myfunc 2 
    [2] print     1st call    2 
    [3] x > 0 is true   1st call    2 
    [4] x := x - 1    1st call    1 
    [4] Call myfunc(x)   1st call    1 
    |       
    +-> [1] print    2nd call to myfunc 1 
     [2] print    2nd call    1 
     [3] x > 0 is true  2nd call    1 
     [4] x := x - 1   2nd call    0 
     [4] Call myfunc(x)  2nd call    0 
     | 
     +-> [1] print   3rd call to myfunc 0 
      [2] print   3rd call    0 
      [3] x > 0 is false 3rd call    0 
      [5] print   3rd call    0 
      [6] print   3rd call    0 
      Retun    3rd call    0 
      | 
      <-+ 
     [5] print    2nd call to myfunc 0 
     [6] print    2nd call    0 
     Retun     2nd call    0 
     | 
     <-+ 
    [5] print     1st call to myfunc 1 
    [6] print     1st call    1 
    Return      1st call 

如果你把所有的被称为x的相应值的版画，你会得到：

[1] print 2   
[2] print 2  > [2]M here 1 
[1] print 1   
[2] print 1  > [1]M here 1 
[1] print 0   
[2] print 0  > [0]M here 1 
[5] print 0  > M here 2 
[6] print 0  > 0, 
[5] print 0  > M here 2 
[6] print 0  > 0, 
[5] print 1  > M here 2 
[6] print 1  > 1, 

在复发，你要记住，每次调用一个函数在其内部，在某个时刻，这个调用将返回，并且以下语句将正常执行。构建/理解递归函数的一种好方法是将它看作不是一组“独立”做事情的陈述，而是将它看作是做一些工作的整个指令。这样，如果您可以先写出函数的规范，那么您就知道如何在其内部重用它，以及它是否安全。