请求解析模拟Merge Sort拆分逻辑的递归程序输出结果

嘿，我来帮你一步步拆解这段递归程序的执行流程，这样你就能清楚每一行输出是怎么来的了！

你的代码 #

#include <iostream>
using namespace std;
void check(int c, int d) {
    cout << "C=" << c << " D=" << d << endl;
    if (c < d) {
        int mid = (c + d) / 2;
        cout << "mid=" << mid << endl;
        check(c, mid);
        check(mid + 1, d);
    }
}
int main() {
    check(0, 5);
    return 0;
}

输出结果 #

C=0 D=5
mid=2
C=0 D=2
mid=1
C=0 D=1
mid=0
C=0 D=0
C=1 D=1
C=2 D=2
C=3 D=5
mid=4
C=3 D=4
mid=3
C=3 D=3
C=4 D=4
C=5 D=5

咱们跟着程序的执行顺序一步步走，递归的核心是先钻透左分支，直到无法拆分，再回头处理每个节点的右分支，完全对应归并排序的拆分逻辑：

1. 初始调用：check(0,5) #

程序从main里的check(0,5)启动：

• 先打印 C=0 D=5
• 因为0 < 5，计算mid=(0+5)/2=2，打印mid=2
• 此时优先执行第一个递归调用check(0,2)，check(3,5)会暂时“排队”，等左分支所有调用完成才会轮到它。

2. 进入左分支：check(0,2) #

• 打印 C=0 D=2
• 0 < 2，计算mid=(0+2)/2=1，打印mid=1
• 继续优先执行check(0,1)，check(2,2)排队等待。

3. 继续深入左分支：check(0,1) #

• 打印 C=0 D=1
• 0 < 1，计算mid=(0+1)/2=0，打印mid=0
• 优先执行check(0,0)，check(1,1)排队等待。

4. 左分支最底层：check(0,0) #

• 打印 C=0 D=0
• 因为0不小于0，不进入if分支，这个函数执行完毕，返回上一层（check(0,1)的调用点）。

5. 处理check(0,1)的右分支：check(1,1) #

• 打印 C=1 D=1
• 不满足c < d，函数执行完毕，返回上一层（check(0,2)的调用点）。

6. 处理check(0,2)的右分支：check(2,2) #

• 打印 C=2 D=2
• 执行完毕，返回最开始的check(0,5)调用点。

7. 终于轮到右分支：check(3,5) #

现在左分支全处理完了，开始执行之前排队的check(3,5)：

• 打印 C=3 D=5
• 3 < 5，计算mid=(3+5)/2=4，打印mid=4
• 优先执行check(3,4)，check(5,5)排队等待。

8. 深入check(3,5)的左分支：check(3,4) #

• 打印 C=3 D=4
• 3 < 4，计算mid=(3+4)/2=3（整数除法，7/2取整为3），打印mid=3
• 优先执行check(3,3)，check(4,4)排队等待。

9. check(3,4)的左分支底层：check(3,3) #

• 打印 C=3 D=3
• 执行完毕，返回check(3,4)的调用点。

10. 处理check(3,4)的右分支：check(4,4) #

• 打印 C=4 D=4
• 执行完毕，返回check(3,5)的调用点。

11. 处理check(3,5)的右分支：check(5,5) #

• 打印 C=5 D=5
• 执行完毕，整个递归流程彻底结束。

总结一下：递归就是“先拆左，拆到最小单元再回头拆右”，你之前理解到mid=0的部分，就是左分支拆到最底层的过程，之后的输出都是逐层返回处理每个节点的右分支，直到所有区间都拆成单个元素为止——这正是归并排序拆分阶段的核心逻辑！

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