含两次递归调用的C语言递归函数运行原理求解

完整代码 #

#include<stdio.h>
void fun(int x)
{
  if(x > 0)
  {
     fun(--x);
     printf("%d\t", x);
     fun(--x);
  }
}
 
int main()
{
  int a = 4;
  fun(a);
  return 0;
}

核心执行规则 #

每次进入fun(x)调用后，只要满足x>0，就严格按以下顺序执行三步操作，前一步完全执行完毕才会进入下一步：

• 第一步：x先自减1，触发第一次递归调用，等该递归调用的所有子逻辑全部执行完成后再往下走
• 第二步：打印当前栈帧中存储的x值
• 第三步：x再次自减1，触发第二次递归调用，等该递归调用的所有子逻辑全部执行完成后，当前fun(x)调用才算结束

注意：C语言函数参数为值传递，每个递归调用的栈帧中存储的是独立的x副本，不同调用的x值互不干扰

初始参数a=4的完整执行流程 #

我们按调用栈的进出顺序逐步推导：

1. 调用fun(4)，x=4>0，x自减为3，触发fun(3)
2. 进入fun(3)，x=3>0，x自减为2，触发fun(2)
3. 进入fun(2)，x=2>0，x自减为1，触发fun(1)
4. 进入fun(1)，x=1>0，x自减为0，触发fun(0)
5. 进入fun(0)，不满足x>0，直接返回，回到fun(1)
6. 执行fun(1)的打印逻辑，输出0；x自减为-1，触发fun(-1)直接返回，fun(1)执行结束，回到fun(2)
7. 执行fun(2)的打印逻辑，输出1；x自减为0，触发fun(0)直接返回，fun(2)执行结束，回到fun(3)
8. 执行fun(3)的打印逻辑，输出2；x自减为1，触发fun(1)
9. 进入新的fun(1)调用，重复步骤4~6的逻辑，输出0，fun(1)执行结束，回到fun(3)，fun(3)执行结束，回到fun(4)
10. 执行fun(4)的打印逻辑，输出3；x自减为2，触发fun(2)
11. 进入新的fun(2)调用，重复步骤3~7的逻辑，依次输出0、1，fun(2)执行结束，回到fun(4)，fun(4)执行结束，程序退出

最终输出结果为：0 1 2 0 3 0 1

第二次递归调用的逻辑说明 #

你之前的认知是正确的，递归调用会先入栈，到基线条件后出栈执行，而第二次递归和第一次递归的执行逻辑完全一致，只是触发时机在打印语句之后：当前调用的第一次递归所有子逻辑全部执行完成、完成打印之后，才会创建新的递归调用栈帧，这个新的调用同样会遵循「入栈到基线条件→出栈执行」的规则，直到它的所有子逻辑全部执行完，当前的函数调用才会出栈结束。

内容的提问来源于stack exchange，提问作者akoluacik