控制流如何與這些多次調用遞歸函數？

Question

#include<stdio.h> 
void display(int n) 
{ 
    if(n) 
    { 
     display(n-1);    
     printf("display 1\n"); 
     display(n-1); 
     printf("display 2 "); 
    } 
} 

int main() 
{ 
    display(5); 
    return 0; 
} 

控制如何在display_1和display_2之間切換？

這兩個調用之間的關係是什麼？它們在這裏如何工作？

我非常熟悉使用遞歸的因子程序。但是在這裏我很困惑，以判斷display_1是否會撥打display_2，反之亦然。

代碼的輸出：

Answer 1

有多種可能性，探討的控制流程（只要沒有多線程或多處理這是不是在這種情況下）。

一個選項是在調試器中逐步執行您的示例代碼。另一個選項可能是「printf」調試。對於這一點，我添加了一些printf() s到您的一部開拓創新代碼：

#include <stdio.h> 

void display(int n, int depth) 
{ 
    printf("%*sdisplay(%d) entered\n", depth * 4, "", n); 
    if (n) { 
    printf("%*s1st call display(%d)\n", depth * 4, "", n - 1); 
    display(n - 1, depth + 1);    
    printf("display 1\n"); 
    printf("%*s2nd call display(%d)\n", depth * 4, "", n - 1); 
    display(n - 1, depth + 1); 
    printf("display 2\n"); 
    } 
    printf("%*sleaving display(%d)\n", depth * 4, "", n); 
} 

int main(void) 
{ 
    /* 
    printf("call display(5)\n"); 
    display(5, 0); 
    */ 
    printf("call display(2)\n"); 
    display(2, 1); 
    return 0; 
} 

編譯和執行上ideone：

call display(2) 
    display(2) entered 
    1st call display(1) 
     display(1) entered 
     1st call display(0) 
      display(0) entered 
      leaving display(0) 
display 1 
     2nd call display(0) 
      display(0) entered 
      leaving display(0) 
display 2 
     leaving display(1) 
display 1 
    2nd call display(1) 
     display(1) entered 
     1st call display(0) 
      display(0) entered 
      leaving display(0) 
display 1 
     2nd call display(0) 
      display(0) entered 
      leaving display(0) 
display 2 
     leaving display(1) 
display 2 
    leaving display(2) 

另外，我用縮進以可視化的遞歸深度。 那麼，現在還不清楚嗎？

因此，display()每次調用使得兩個遞歸下降（如果n尚未0），其中被叫display()再次使得兩個遞歸下降（如果n尚未0）等等（直到遞歸的終止）。

這種模式非常類似的常見應用是計算Fibonacci number。

樹形結構的遍歷是該模式的另一個類似應用（在Tree traversal中提到）。在binary tree的情況下，每個步驟有兩種可能的遞歸調用。 （在一般的樹中，有多少遞歸調用，因爲節點有孩子。）