1

I want to do a factorial of a BigInteger (in Kotlin). With a tail recursion I get StackOverFlow error when I try to do 9000! . With a non-recursive function I can do that ... but I'm very curious how to avoid this kind of error.

Here is my code: 

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))}")
}
Vadim Kotov
  • 8,084
  • 8
  • 48
  • 62
Andrei Paciurca
  • 433
  • 7
  • 17
  • Possible duplicate of [How to increase the Java stack size?](https://stackoverflow.com/questions/3700459/how-to-increase-the-java-stack-size) – konsolas Sep 04 '17 at 14:26

1 Answers1

6

This is a problem that must solved at the language level, because the JVM does not optimize tail recursion.

Fortunately, the Kotlin language provides a tailrec modifier for exactly this purpose, so you can simply write tailrec fun instead of fun. The compiler will convert tail calls inside a tailrec function into loops, which should get rid of the stack overflow you are experiencing.

fredoverflow
  • 256,549
  • 94
  • 388
  • 662