35、Scala:递归阶乘与输入边界

补齐缺失括号,明确 0 与负数处理以及 BigInt 不能避免递归栈限制。

简明结论

BigInt 避免固定宽度整数溢出,但不自动消除调用栈限制。普通阶乘 `n * factorial(n - 1)` 不是尾递归;不能把它作为大输入下可靠的计算服务。

用 BigInt 就不会出现递归深度问题吗?

BigInt 避免固定宽度整数溢出,但不自动消除调用栈限制。普通阶乘 n * factorial(n - 1) 不是尾递归;不能把它作为大输入下可靠的计算服务。

完整示例

下面采用 Scala 2.13 风格,保存为 FactorialDemo.scala。原文缺少结束括号且错误标为 Java,已修复。

object FactorialDemo {
  def factorial(n: Int): BigInt = {
    require(n >= 0, "n must be non-negative")
    if (n <= 1) BigInt(1)
    else BigInt(n) * factorial(n - 1)
  }
  def main(args: Array[String]): Unit = {
    println(factorial(0))
    println(factorial(5))
  }
}
scalac FactorialDemo.scala
scala FactorialDemo

按逻辑预期输出 1 和 120;负数触发参数错误。本轮只核对语言资料并修复代码,未安装 Scala 编译器执行,不将上述输出记录为实测。

进一步练习

对大输入可考虑循环或带累加器的尾递归,并明确资源上限。尾递归版本应使用 @tailrec 让编译器检查是否可优化;不能只靠函数自己调用自己就认定是尾递归。

不提供本页未测量的速度比较。

整理范围与出处

本次依据下方版本资料整理说明与示例;历史导入资料的来源状态单独列示,不将技术参考认作原作者信息。原始发布日期与地址保留。