瞭解遞歸和遞減

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, 

在復發，你要記住，每次調用一個函數在其內部，在某個時刻，這個調用將返回，並且以下語句將正常執行。構建/理解遞歸函數的一種好方法是將它看作不是一組「獨立」做事情的陳述，而是將它看作是做一些工作的整個指令。這樣，如果您可以先寫出函數的規範，那麼您就知道如何在其內部重用它，以及它是否安全。