1. 引言
在本文中，我们将探讨如何将递归函数转换为迭代形式。我们将介绍适用于尾递归和头递归的转换方法，以及一种可以将任意递归转换为迭代算法的通用技术。
递归在许多问题中都非常自然，尤其是那些具有递归结构的问题。它将问题分解为更小的子问题，递归地解决这些子问题，并将结果组合起来。这种方式使递归函数更易于阅读、理解和维护。
然而，递归也有其缺点。每次递归调用都会向调用栈添加一个新的栈帧，如果输入非常大，可能导致栈溢出（Stack Overflow）错误。此外，递归函数在内存和时间复杂度上可能比对应的迭代版本更高。
我们来看一个经典的例子：斐波那契数列的递归和迭代实现。
algorithm FibonacciRec(n):
// INPUT
// n = 斐波那契序列中的位置（自然数）
// OUTPUT
// 第 n 个斐波那契数
if n in {1, 2}:
return 1
else:
return FibonacciRec(n - 1) + FibonacciRec(n - 2)
algorithm FibonacciIter(n):
// INPUT
// n = 斐波那契序列中的位置（自然数）
// OUTPUT
// 第 n 个斐波那契数
f1 <- 1
f2 <- 1
m <- 2
while m < n:
fnew <- f2 + f1
f1 <- f2
f2 <- fnew
m <- m + 1
return f2
递归版本 FibonacciRec(n) 更符合斐波那契数列的定义：
$$ F_n = \begin{cases} 1, & n \in {1, 2}, \ F_{n-1} + F_{n-2}, & n > 2 \end{cases} $$
但递归实现会导致栈溢出错误，且其时间复杂度为指数级，而迭代版本为线性时间。因此，有时我们需要将递归算法转换为迭代形式。
✅ 结论：递归可读性强但性能差，迭代性能好但可读性差。根据场景选择合适的方式。
2. 尾递归函数的转换
尾递归是一种特殊的递归形式：函数在递归调用之后不再做任何计算，直接返回递归调用的结果。这类函数最容易转换为迭代形式。
尾递归通常具有如下结构：
algorithm SolveTailRecursive(problem, accumulator):
// INPUT
// problem = 要解决的问题实例
// accumulator = 存储部分解的变量
// OUTPUT
// solution = 问题的完整解或失败标识
if BaseCase(problem):
apply base-case update
return accumulator
else:
update accumulator
reduce problem to subproblem
return SolveTailRecursive(subproblem, accumulator)
2.1. 对应的迭代版本
我们可以将其转换为以下迭代结构：
algorithm SolveTailIterative(problem):
// INPUT
// problem = 要解决的问题实例
// OUTPUT
// solution = 问题的完整解或失败标识
accumulator <- initialize
while not BaseCase(problem):
update accumulator
reduce problem to subproblem
problem <- subproblem
apply base-case update
return accumulator
2.2. 转换规则总结
- 初始化累加器（accumulator）；
- 使用“非基例条件”作为循环条件；
- 将递归体（除递归调用外）作为循环体；
- 循环结束后处理基例更新；
- 返回累加器值。
2.3. 示例：阶乘计算
原始尾递归实现：
algorithm FactorialTail(n, accumulator):
if n == 0:
return accumulator
else:
return FactorialTail(n - 1, n * accumulator)
转换为迭代版本：
algorithm FactorialIterative(n):
accumulator <- 1
while n > 0:
accumulator <- n * accumulator
n <- n - 1
return accumulator
✅ 小结：尾递归很容易转换为迭代形式，且代码简洁高效。
3. 通用转换方法
并非所有递归都是尾递归。有些递归在函数体的开头调用自身（头递归），有些则在多个位置调用自己，甚至嵌套调用。对于这类递归，我们需要一种通用转换方法。
3.1. 递归函数的一般形式
algorithm SolveRecursive(problem):
if BaseCase(problem):
return base-case solution
else:
for each recursive call:
execute NRCB (非递归代码块)
extract subproblem_i
subsolution_i <- SolveRecursive(subproblem_i)
combine subsolution_1 ... subsolution_m
return combined solution
3.2. 执行图（Execution Graph）
每个递归调用都对应一个帧（Frame），包含参数、局部变量和返回值。整个递归过程构成一个隐式的有向图，节点是帧，边表示调用关系。
我们可以通过模拟调用栈的方式，用迭代来实现递归。
3.3. 深度优先遍历 + 栈模拟
我们可以使用栈来模拟递归调用栈，实现递归函数的迭代版本：
algorithm SolveIter(problem):
start <- CreateFrame(problem)
stack <- [start]
while stack not empty:
frame <- pop from stack
if has unvisited child:
edge <- get next edge
execute NRCB
push frame back
push child
else:
solution <- get return value
pass to parent
return get return value of start
3.4. 实现细节
- 每个帧应包含参数、局部变量、子问题、返回地址等；
- 使用
get_next_child()来获取下一个子帧； - 使用
get_return_value()来决定返回值； - 使用
pass_to_parent()将结果传递给父帧。
3.5. 示例：双递归函数
考虑如下函数：
function f(n):
if n <= 1:
return 1
else:
a <- f(n - 1)
b <- floor(n / 2)
c <- f(b)
d <- a * b + 1
return d
我们为其定义帧结构、子节点生成逻辑、返回值处理逻辑，并用栈模拟递归过程。
3.6. 可读性与语义保留
虽然这种方法可以实现任意递归的迭代版本，但代码通常不够简洁，可读性差。不过，执行图中仍保留了部分递归结构语义，便于理解。
4. 为什么需要转换递归为迭代？
- 性能优化：递归调用涉及栈帧创建与销毁，开销大；迭代则使用固定栈帧，效率更高；
- 避免栈溢出：递归深度过大时容易导致栈溢出；
- 语言限制：某些语言（如 Python）对递归深度有限制；
- 内存效率：递归占用更多内存，而迭代更节省资源。
✅ 转换优势总结：
- 内存效率更高；
- 性能更优；
- 更适合处理大规模输入；
- 避免栈溢出风险。
5. 小结
本文介绍了如何将递归函数转换为迭代形式，重点讲解了尾递归和通用递归的转换方法。
- 尾递归可轻松转换为迭代形式，代码简洁高效；
- 对于任意递归，我们可以通过模拟调用栈的方式实现其迭代版本；
- 虽然转换后的代码可读性较差，但在性能和稳定性方面有显著提升；
- 掌握递归到迭代的转换技巧，是处理大规模数据和构建高性能系统的重要能力。
⚠️ 注意：转换应根据实际需求进行，优先考虑可读性和维护性。