递归调用前的语句在递推阶段从外层到内层依次执行，用于预处理子问题；语句位置决定遍历顺序，关键要区分问题拆解与结果合成时机。
递归调用前的语句在“递推阶段”执行
递归函数每次进入自身时，先执行调用前的代码，再进入下一层递归。这些语句会从外层到内层依次执行，构成“向下拆解”的过程。
常见错误现象：误以为这些语句会在所有递归结束后才运行；实际它们在栈帧压入过程中就已执行完毕。
- 适用于需要“预处理”子问题的场景，比如打印当前层级、记录路径、剪枝判断
- 若语句依赖形参值（如
n），它的值随递归深度递减（如factorial(n-1)前的cout ） - 性能上无额外开销，但若含复杂计算或 I/O，会随递归深度线性放大
递归调用后的语句在“回归阶段”执行
只有当最深层递归返回后，上一层函数才会继续执行调用之后的语句。它们从最内层向外逐层触发，构成“向上组装结果”的过程。
常见错误现象：忘记回归阶段语句可能根本不会执行——如果递归没走到终止条件（比如漏写 if 或逻辑错），程序直接栈溢出，后续语句零机会运行。
立即学习“C++免费学习笔记（深入）”；
- 适用于结果合并、状态回溯、资源清理（如释放局部对象）
- 能访问到下层递归的返回值，比如
return n * factorial(n-1)中的乘法必须放在调用后 - 注意：若函数声明为
void且无显式return，回归阶段语句仍会执行，但无法利用返回值
同一函数里前后语句的执行顺序不可互换
把本该在回归阶段做的操作（如累加、拼接字符串）错放到递归调用前，会导致逻辑完全错误——它操作的是原始输入，而非子问题解。
例如斐波那契中，return fib(n-1) + fib(n-2) 必须把加法放在两次调用之后；若写成 int s = fib(n-1) + fib(n-2); return s; 看似等价，但本质仍是回归阶段语义。
- 调试时可用计数器或缩进打印验证：递推阶段缩进递增，回归阶段缩进递减
- 尾递归优化（Tail Call Optimization）只对“调用后无其他操作”的函数生效；一旦调用后还有语句，编译器无法优化，栈深度仍随输入线性增长
- C++ 标准不强制要求尾递归优化，
g++ -O2可能优化简单尾调用，但含局部变量或异常处理的函数大概率失效
容易被忽略的细节：void 函数的回归阶段依然存在
即使函数返回 void，只要它有递归调用，控制流一样经历递推→终止→回归三阶段。回归阶段的语句（如日志、状态重置）仍会执行，只是没有返回值可接收。
典型坑点：在 void traverse(Node* root) 中，写 traverse(root->left); cout val; traverse(root->right); 是中序遍历；若把 cout 放到第一次调用前，就变成前序——顺序差异全由语句位置决定，和返回类型无关。
真正危险的不是语句放前后，而是混淆了“问题拆解时机”和“结果合成时机”。递推阶段负责缩小问题，回归阶段负责重建答案；跨过这个分界去动数据，八成要修半夜。
