用 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 让编译器检查是否可优化;不能只靠函数自己调用自己就认定是尾递归。
不提供本页未测量的速度比较。
整理范围与出处
本次依据下方版本资料整理说明与示例;历史导入资料的来源状态单独列示,不将技术参考认作原作者信息。原始发布日期与地址保留。