1. 简介
在本篇教程中，我们将讲解什么是尾递归（Tail Recursion），并探讨它相较于非尾递归（Non-Tail Recursion）的优势。尾递归是一种特殊的递归形式，它在函数调用栈中可以被优化，从而节省内存并避免栈溢出问题。
2. 递归简介
简单来说，递归函数是指调用自身的函数。我们来看一个用于数组求和的递归函数示例：
algorithm RecursiveSum(x):
// INPUT
// x = [x_1, x_2, ..., x_n] - the array to sum
// OUTPUT
// The sum x_1 + x_2 + ... + x_n
if x is empty:
// the base case
return 0
else:
// the recursive call
return x_n + RecursiveSum([x_1, x_2, ..., x_{n-1}])
上述函数中，RecursiveSum([x_1, x_2, ..., x_n]) 会调用 RecursiveSum([x_1, x_2, ..., x_{n-1}])，直到递归到数组为空时返回 0。这个过程存在三个问题：
- 递归深度可能导致栈溢出
- 在到达 base case 后才开始计算
- 每次递归都占用额外的栈空间
2.1 遍历问题
第一个问题是栈溢出风险（Stack Overflow）。如果递归层级太深，程序可能耗尽调用栈空间，导致崩溃。比如处理非常大的输入时就容易发生。
第二个问题是计算延迟。递归函数在到达 base case 前不做任何计算，所有操作都延迟到递归返回时进行。例如下面这个例子：
\begin{aligned}
SUM([1,3,5]) & = 5 + SUM([1,3]) \\
& =5 + \left(3 + SUM([1])\right) \\
& = 5 + \left(3 + \left(1 + SUM([\ ])\right)\right) \\
& = 5 + \left(3 + \left(1 + 0\right)\right) \\
& = 5 + \left(3 + 1\right) \\
& = 5 + 4\\
& = 9
\end{aligned}
可以看到，数组被遍历了两次：一次是递归到底，一次是回溯计算。效率较低 ❌
2.2 内存消耗
第三个问题是内存占用过高。每次递归调用都会在调用栈上新增一个帧（frame），保存局部变量和参数。比如下面这个函数：
algorithm DownloadAndSum(u):
// INPUT
// u = the URLs url_1, url_2, ..., url_n pointing to the elements x1, x2, ..., xn of the array we want to sum
// OUTPUT
// The sum of x1 + x2 + ... + xn
if u is empty:
return 0
else:
data_n <- download the data from url_n
x_n <- process data_n
return x_n + DownloadAndSum([url_1, url_2, ..., url_{n-1}])
每次递归下载并处理一个 1GB 的数据，但调用栈上保留了所有中间帧，导致内存占用极高 ⚠️
3. 尾递归 vs 非尾递归
上面两个问题的根源在于 SUM 和 DownloadAndSum 都是非尾递归函数。那么，什么是尾递归？
✅ 尾递归函数是指在函数体中最后一个操作是返回一个递归调用的函数。
非尾递归函数在返回前还需要对递归结果做额外处理，比如加法、乘法、逻辑判断等。而尾递归函数直接返回递归调用的结果，因此可以复用当前栈帧，避免栈溢出和内存浪费。
3.1 改写为尾递归版本
原函数：
algorithm SUM(x, s):
// INPUT
// x = the array to sum
// s = the current partial sum
// OUTPUT
// The sum x_1 + x_2 + ... + x_n
if x is empty:
return s
else:
return SUM([x_1, x_2, ..., x_{n-1}], s + x_n)
调用方式为 SUM([1,3,5], 0)，执行过程如下：
\begin{aligned}
SUM([1,3,5], 0) & = SUM([1,3], 5) \\
& = SUM([1], 8)) \\
& = SUM([\ ], 9) \\
& = 9 \\
\end{aligned}
这种写法避免了回溯，计算在递归过程中完成，每个调用只保留当前状态，非常适合尾递归优化 ✅
3.2 注意事项
并非所有函数都能转换为尾递归。例如：
return x_n + RecursiveSum(...);
这种写法在递归返回后还需要执行加法，因此无法进行尾调用优化。
4. 从尾递归到迭代算法
尾递归的本质是：函数调用可被编译器优化为 GOTO 跳转。我们可以将尾递归函数转换为等价的迭代版本。
以 SUM 为例，转换为 GOTO 版本如下：
algorithm SUM(x, s):
s <- 0
// sum loop
if n = 0:
return s
else:
s <- s + x_n
n <- n - 1
GOTO sum loop
return s
进一步转换为 while 循环版本：
algorithm Sum(x):
// INPUT
// x = the array to sum
// OUTPUT
// The sum x_1 + x_2 + ... + x_n
s <- 0
while n > 0:
s <- s + x_n
n <- n - 1
return s
可以看到，尾递归和迭代是等价的。尾递归本质上就是一种结构化的 GOTO。
5. 总结
✅ 尾递归函数的优势：
- 可以被编译器优化，复用调用栈帧
- 避免栈溢出
- 减少内存开销
- 计算在递归过程中完成，无需回溯
⚠️ 注意事项：
- 必须保证函数的最后一步是返回递归调用的结果
- 不是所有递归都可以改写为尾递归
- Java 编译器目前不支持尾递归优化，但 Scala、Kotlin、Erlang 等语言支持
如果你在编写递归函数时遇到栈溢出或内存问题，可以尝试将其改写为尾递归形式，或使用迭代替代。这样可以提升程序的健壮性和性能 ✅