c - 对递归函数的多次调用的控制流程如何？

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():

#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 的情况下，每步有两个可能的递归调用。 (在一般的树中，节点有多少个子节点就有多少个递归调用。)