Kotlin 中计算给定数字的阶乘

1. 简介

阶乘（Factorial）是一个常见的数学运算，表示从 1 到给定正整数 n 所有整数的乘积，记作 *n!*，其定义为：

n! = n × (n−1) × (n−2) × … × 2 × 1

例如：5! = 5 × 4 × 3 × 2 × 1 = 120。

本文将介绍在 Kotlin 中如何通过递归和循环两种方式实现阶乘计算。虽然问题本身不复杂，但在实际开发中，这类小函数常常成为性能或栈溢出的“踩坑”点，值得我们认真对待。

2. 使用递归计算阶乘

递归是一种函数调用自身的编程技巧，非常适合表达具有自相似结构的数学定义。阶乘天然具备递归特性：

n! = n × (n−1)!

其中 (n−1)! 又可继续展开，直到达到边界条件 0! = 1 或 1! = 1。

下面是对应的 Kotlin 实现：

fun factorialRecursive(n: Int): Int {
    require(n >= 0) { "n must be positive" }
    return if (n <= 1) {
        1
    } else {
        n * factorialRecursive(n - 1)
    }
}

✅ 关键点解析：

使用 require(n >= 0) 做前置校验，避免负数输入 ❌
基准条件（base case）是 n <= 1，返回 1，防止无限递归
否则返回 n * factorialRecursive(n - 1)，体现递归关系

为了验证正确性，编写单元测试：

@Test
fun `Should calculate a factorial recursively`() {
    val result = factorialRecursive(7)
    assertEquals(7 * 6 * 5 * 4 * 3 * 2 * 1, result, "7! should be exactly 5040")
}

2.1. 尾递归优化（tailrec）

普通递归在处理大数时容易触发 Stack Overflow Error，因为每次调用都会在调用栈中压入一个新帧。

Kotlin 提供了 tailrec 关键字支持尾递归优化——编译器会将其自动转换为等价的循环，从而避免栈溢出。

⚠️ 要使用 tailrec，必须满足：

函数只有一个递归调用
且该调用必须是函数的最后一个操作

为此，我们需要引入一个累加器（accumulator）来传递中间结果：

tailrec fun factorialTailRecursive(n: Int, accumulator: Int = 1): Int {
    return if (n <= 1) {
        accumulator
    } else {
        factorialTailRecursive(n - 1, n * accumulator)
    }
}

✅ 优势分析：

tailrec 让递归拥有接近循环的性能
代码仍保持函数式风格，逻辑清晰
编译器会在字节码层面将其优化为 while 循环

配套测试用例：

@Test
fun `Should calculate a factorial tail-recursively`() {
    val result = factorialTailRecursive(6)
    assertEquals(6 * 5 * 4 * 3 * 2 * 1, result, "6! should be exactly 720")
}

📌 提示：可以通过反编译生成的 .class 文件确认是否被优化成了循环结构。

3. 使用循环计算阶乘

对于追求性能和稳定性的场景，迭代法（循环）通常是更安全的选择，尤其是在无法确定输入范围的情况下。

以下是基于 for 循环的实现：

fun factorialIterative(n: Int): Int {
    var result = 1
    for (i in 1..n) {
        result *= i
    }
    return result
}

✅ 优点总结：

时间复杂度 O(n)，空间复杂度 O(1)
不依赖调用栈，完全避免栈溢出风险
易于理解和调试

测试用例如下：

@Test
fun `Should calculate a factorial iteratively`() {
    val result = factorialIterative(5)
    assertEquals(5 * 4 * 3 * 2 * 1, result, "5! should be exactly 120")
}

⚠️ 注意事项：

所有版本均使用 Int 类型，当 n > 12 时会发生整数溢出（overflow）
如需支持更大数值，建议改用 Long 或 BigInteger

示例修正（支持大数）：

import java.math.BigInteger

fun factorialBig(n: Int): BigInteger {
    require(n >= 0)
    return (1..n).map { BigInteger.valueOf(it.toLong()) }.reduce { acc, i -> acc.multiply(i) }
}

4. 总结

方法	可读性	内存效率	安全性	推荐场景
普通递归	✅ 高	❌ 差	❌ 低（栈溢出）	教学演示、小数据量
尾递归 (`tailrec`)	✅ 高	✅ 好	✅ 中高	函数式偏好 + 编译优化保障
迭代（循环）	✅ 中	✅ 最佳	✅ 最高	生产环境、大数据量

📌 经验建议：

学习阶段可用普通递归理解概念
实际项目优先考虑 tailrec 或直接使用循环
处理可能的大输入时务必使用 BigInteger 防止溢出

示例代码已托管至 GitHub：https://github.com/baeldung/kotlin-tutorials/tree/master/kotlin-math

Persistence

REST

Security

1. 简介

2. 使用递归计算阶乘

2.1. 尾递归优化（tailrec）

3. 使用循环计算阶乘

4. 总结