C语言栈与递归：双递归函数为何输出非预期数字序列？

#include <stdio.h>

void fun(int a) {
    if (a > 0) {
        fun(a / 10);
        printf("%d", a % 10);
        fun(a / 10);
    }
}
int main() {
    fun(12345);
    return 0;
}

运行上述代码的实际输出为：1213121412131215121312141213121，和“开头递归就不会执行打印”的直觉不符，本质是对C语言函数调用和递归执行逻辑的误解，结合栈帧原理的解释如下：

C语言的函数调用基于调用栈实现，每次调用一个函数，都会在栈顶压入一个独立的栈帧，存储当前函数的局部变量、执行断点位置、返回地址等信息；被调用函数执行完毕后，对应栈帧弹出，回到上一层函数的断点位置继续执行剩余代码。递归调用本质就是函数自己调用自己，完全遵循这个规则，不会出现“调用了自身就永远不回头执行后续代码”的情况。

对应到fun函数，只要传入参数a>0，每一层的执行顺序是固定的三步，前一步完全执行结束才会走下一步：

• 第一步：递归调用fun(a/10)，等待该调用全部执行完成并返回
• 第二步：执行printf打印当前参数a的个位（即a%10的结果）
• 第三步：再次递归调用fun(a/10)，等待该调用全部执行完成并返回，当前层函数结束，弹栈回到上一层

这个执行逻辑和二叉树的中序遍历完全一致，我们可以从小参数开始推演，很容易找到输出规律：

1. 当传入a=0：不满足判断条件，直接返回，无任何输出
2. 当传入a=1：先调用fun(0)无输出，打印1，再调用fun(0)无输出，最终输出1
3. 当传入a=12：先调用fun(1)输出1，打印2，再调用fun(1)输出1，最终输出121
4. 当传入a=123：先调用fun(12)输出121，打印3，再调用fun(12)输出121，最终输出1213121
5. 当传入a=1234：先调用fun(123)输出1213121，打印4，再调用fun(123)输出1213121，最终输出121312141213121

按照这个规律递推到a=12345时，就会先执行fun(1234)输出左半段121312141213121，再打印5，最后再执行fun(1234)输出右半段121312141213121，拼接起来就是实际运行得到的结果。

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