控制流如何与这些多次调用递归函数？

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的情况下，每个步骤有两种可能的递归调用。 （在一般的树中，有多少递归调用，因为节点有孩子。）