递归函数rec执行结果解析：输入"1234"的输出推导请求

先把问题中的递归函数代码贴出来：

void rec(char *s) {
    if (s[0] == 0) return;

    rec(s + 1);

    printf("%c", s[0]);
    
    rec(s + 1);

    printf("X");
}

我们可以用f(s)来表示调用rec(s)时产生的输出内容，从最短的子串开始逐步推导，这样更容易理清递归流程：

1. 空串f("")：触发终止条件if (s[0] == 0)，直接返回，无任何输出。

2. 单字符串f("4")：

   • 第一步：调用rec("")，无输出；
   • 第二步：打印字符'4'；
   • 第三步：再次调用rec("")，无输出；
   • 第四步：打印'X'；
     最终输出：4X

3. 双字符串f("34")：

   • 第一步：调用rec("4")，输出4X；
   • 第二步：打印字符'3'；
   • 第三步：再次调用rec("4")，输出4X；
   • 第四步：打印'X'；
     拼接后输出：4X + 3 + 4X + X = 4X34XX

4. 三字符串f("234")：

   • 第一步：调用rec("34")，输出4X34XX；
   • 第二步：打印字符'2'；
   • 第三步：再次调用rec("34")，输出4X34XX；
   • 第四步：打印'X'；
     拼接后输出：4X34XX + 2 + 4X34XX + X = 4X34XX24X34XXX

5. 目标串f("1234")：

   • 第一步：调用rec("234")，输出4X34XX24X34XXX；
   • 第二步：打印字符'1'；
   • 第三步：再次调用rec("234")，输出4X34XX24X34XXX；
   • 第四步：打印'X'；
     最终拼接结果：4X34XX24X34XXX + 1 + 4X34XX24X34XXX + X = 4X34XX24X34XXX14X34XX24X34XXXX

这个结果和讲师给出的输出完全一致。递归的核心是先逐层深入到最底层的子问题（空串），再从底层往上依次执行后续的打印逻辑，每一层都会重复执行两次下层递归+一次当前字符打印+一次X打印。

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