我想做一个biginteger的阶乘(在kotlin中)。使用尾部递归,当我尝试执行9000!时会出现stackoverflow错误。用一个非递归函数我可以做到。。。但我很好奇如何避免这种错误。
这是我的密码:
import java.math.BigInteger
fun tail_recursion_factorial(n: BigInteger, factorialOfN: BigInteger = BigInteger.valueOf(2)): BigInteger {
return when(n){
BigInteger.ONE -> BigInteger.ONE
BigInteger.valueOf(2) -> factorialOfN
else -> tail_recursion_factorial(n.minus(BigInteger.ONE), n.times(factorialOfN))
}
}
fun non_recursive_factorial(n: BigInteger): BigInteger{
var i: BigInteger = BigInteger.ONE
var factorial: BigInteger = BigInteger.ONE
while (i<=n){
factorial = factorial.times(i)
i = i.plus(BigInteger.ONE)
}
return factorial
}
fun main(args: Array<String>){
print("n == ")
var n = readLine()!!
//recursive
//println("$n! is ${tail_recursion_factorial(BigInteger(n))}")
//non-recursive
println("$n! is ${non_recursive_factorial(BigInteger(n))}")
}
1条答案
按热度按时间nbnkbykc1#
这是一个必须在语言级别解决的问题,因为jvm没有优化尾部递归。
幸运的是,kotlin语言提供了
tailrec
正是为了这个目的,所以你可以简单地写tailrec fun
而不是fun
. 编译器会将tailrec函数中的尾部调用转换为循环,这样就可以消除正在经历的堆栈溢出。