尾调用优化(TCO)为何要求递归调用为函数最后一步且直接返回？

TCO核心要求的底层原因 #

函数执行时，操作系统会在调用栈上为每个函数分配独立的栈帧，存储当前函数的局部变量、返回地址、寄存器上下文等数据，只有当函数完全执行完毕准备返回时，对应的栈帧才会被弹出释放。
TCO的本质是消除不必要的栈帧占用：如果递归调用是当前函数的最后一个操作，且递归返回的结果直接作为当前函数的返回值，说明当前函数已经没有任何后续逻辑需要执行，当前栈帧里的所有数据都不再有用，编译器/解释器就可以直接复用当前栈帧给新的递归调用，或者提前释放当前栈帧后再执行递归调用，这样无论递归多少次，调用栈的大小都稳定在O(1)，不会出现栈溢出问题。
反之如果递归调用后还有其他操作要执行，当前栈帧的数据（比如局部变量、后续要执行的指令地址）还要被用到，就无法被提前释放，自然也就做不到TCO。 #

给出代码的TCO适配性判断 #

第一段代码（你认为符合TCO的示例） #

int factorial(int num) {
  if (num == 1 || num == 0)
    return 1;
  return num * factorial(num - 1);
}

这段代码实际不符合TCO优化要求，很多人会误以为return语句后接函数调用就是尾调用，这是常见误区：这里递归调用factorial(num-1)返回后，还需要执行和num的乘法运算，才能得到当前函数的最终返回值，当前栈帧必须保留num的值等待递归返回后做计算，无法被提前释放。
符合TCO要求的阶乘递归实现需要引入累加器，把乘法运算前置到递归调用前完成：

// 尾递归实现，递归结果直接返回
int factorial_tail(int num, int accumulator) {
  if (num <= 1) return accumulator;
  return factorial_tail(num - 1, num * accumulator);
}

// 对外调用接口
int factorial(int num) {
  return factorial_tail(num, 1);
}

第二段代码 #

#include <stdio.h>
int factorial(int num) {
  if (num == 1 || num == 0)
    return 1;
  int temp = num * factorial(num - 1);
  printf("%d", temp);
  return temp;
}

这段代码完全不满足TCO要求，原因如下：

• 递归调用factorial(num-1)之后，还有乘法赋值、printf打印两个额外操作要执行，当前栈帧必须保留num的值、打印指令的地址等数据，无法被复用或提前释放
• 递归调用的结果没有被直接返回，经过了中间变量存储、I/O操作后才返回，不符合TCO的核心规则

规则简化理解 #

你给别人解释的时候可以这么说：TCO的前提是「调用完递归函数，当前函数就没有任何事情要做了，直接把递归的结果当自己的结果返回」，只要还剩哪怕一步运算、一次打印、一个赋值，当前函数的栈帧就还有用，就没法优化。

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