目录
前言
尾递归（Tail Recursion）是递归函数的一种特殊形式，在递归调用中，递归调用是函数中的最后一个操作，即递归调用的结果直接作为函数的返回值，且在递归调用之后没有额外的操作需要执行。
在尾递归中，递归函数不需要在调用栈中保留当前的函数状态，因为递归调用是函数中的最后一步。这样，编译器或解释器可以优化递归调用，将其转换为迭代形式，从而避免递归带来的深度栈消耗问题。这种优化被称为尾递归优化（Tail Call Optimization, TCO）。
一、尾递归示例
以计算阶乘为例。先看一个非尾递归的阶乘函数：
int factorial(int n) {
if (n == 1)
return 1;
return n * factorial(n - 1);
}在上面的非尾递归实现中，factorial(n - 1) 的返回值会乘以 n，然后返回给上一层调用。这意味着在每次递归调用时，当前调用的状态（比如 n 的值）需要保留在栈中，直到递归调用返回。这就导致了递归的深度增长，消耗栈空间。
下面是一个尾递归的版本：
int factorial_tail(int n, int result = 1) {
if (n == 1)
return result;
return factorial_tail(n - 1, n * result);
}在这个尾递归版本中，递归调用 factorial_tail(n - 1, n * result) 是函数的最后一个操作，没有其他操作需要在递归调用后执行，因此不需要保留当前函数的状态。编译器可以对它进行优化，将其转换为一个循环，避免了递归调用深度的问题。
二、尾递归的特点
- 递归调用是函数中的最后一个操作。
- 不需要在递归调用后进行额外的计算。
- 编译器或解释器可以通过优化减少函数调用的栈帧。
三、尾递归优化的优势
- 减少栈空间消耗：尾递归优化将递归转换为迭代形式，消除了函数调用的栈帧开销，避免了栈溢出的问题。
- 提高性能：通过减少不必要的栈帧保存和恢复，尾递归优化可以提高递归函数的执行效率。
四、尾递归与非尾递归的区别
- 非尾递归：在递归调用后有额外的操作需要执行，因此递归调用前的状态必须保留在栈中，递归深度较大会导致栈溢出。
- 尾递归：递归调用是最后的操作，当前状态不需要保留，可以直接覆盖栈帧或转换为循环，避免栈溢出。