从递归到迭代：以阶乘函数为例

1. 概述

递归和迭代是编程中重复执行代码的两种基本方式。虽然递归在某些场景下有其独特优势，但在实际开发中，迭代方式往往更受青睐，因为它在性能和内存占用方面更优。

本文将通过一个经典的阶乘函数示例，讲解如何将递归函数转换为迭代函数，重点使用尾递归优化方法，帮助你在面对复杂递归逻辑时也能游刃有余地进行重构。

2. 递归与迭代的区别

递归和迭代是实现重复逻辑的两种基本方式：

递归（Recursion）：函数调用自身来执行重复逻辑。适用于结构清晰、可自然拆分的问题，如树遍历、阶乘计算等。
迭代（Iteration）：通过 for、while 等循环结构重复执行代码块，控制流更直观，内存效率更高。

✅ 建议：除非递归逻辑特别清晰且不会导致栈溢出，否则优先使用迭代。

3. 将递归函数转换为尾递归函数

尾递归是一种特殊的递归形式，其递归调用是函数的最后一步操作。这种结构可以被编译器优化为迭代，从而避免栈溢出。

3.1. 转换步骤

将普通递归转换为尾递归的核心思路是引入累加器（Accumulator）：

找出非尾递归调用的位置
分析该调用与返回值之间的操作（如乘法）
引入一个累加器参数，保存中间结果
将非尾递归调用改为尾递归调用
重复上述步骤，直到所有递归调用都是尾调用

3.2. 将尾递归转换为迭代

一旦函数是尾递归的，就可以按如下步骤转换为迭代：

理解函数逻辑
确保所有递归调用都是尾调用
使用一个无限循环包裹函数体
将尾递归调用替换为参数更新 + continue
清理代码，去除冗余部分

4. 示例：阶乘函数

我们以阶乘函数为例，演示完整的转换过程。

4.1. 原始递归实现

public static int factorial(int n) {
    if (n < 2) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

这是一个典型的非尾递归函数。问题在于：return n * factorial(n - 1); 中，递归调用不是最后一步，而是返回后再进行乘法运算。

4.2. 改造为尾递归

我们在函数中引入一个累加器参数 acc，保存中间结果：

public static int factorial(int n, int acc) {
    if (n < 2) {
        return acc;
    } else {
        return factorial(n - 1, n * acc);
    }
}

初始调用为 factorial(n, 1)。这样，每次递归调用都变成了尾调用，递归栈不再增长。

4.3. 改写为迭代版本

接下来我们将其转换为迭代版本：

public static int factorialIterative(int n) {
    int acc = 1;
    while (n > 1) {
        acc *= n;
        n--;
    }
    return acc;
}

✅ 优点：只使用一个栈帧，避免了栈溢出问题，效率更高。

4.4. 栈帧对比图示

下面展示了三种实现方式在计算 3! 时的栈帧变化：

递归方式：
尾递归方式：
迭代方式：

⚠️ 结论：尾递归虽然逻辑上是递归，但在支持尾调用优化的语言中，可以做到与迭代相同的栈空间占用。Java 不支持尾调用优化，所以实际开发中建议直接使用迭代。

5. 复杂递归函数的转换策略

对于更复杂的递归逻辑，可以考虑以下方法：

Trampoline（蹦床）：手动控制递归调用顺序，避免栈溢出
Continuation-Passing Style（CPS）：将后续操作作为参数传递给递归函数，实现控制流的转换

✅ 注意：这些方法更适合函数式语言（如 Scala、Clojure），Java 中实现起来较为繁琐。

6. 总结

通过本文你学会了：

递归与迭代的基本区别
如何将普通递归转换为尾递归
如何将尾递归改写为迭代
阶乘函数的完整转换过程
为什么在 Java 中应避免深层递归

✅ 推荐实践：在实际项目中遇到递归逻辑时，优先尝试将其转换为迭代版本，尤其是处理大数据或深度不确定的场景。这不仅能提升性能，还能避免潜在的 StackOverflowError。

Persistence

REST

Security