What's different of these tailrec funtions on kotlin

Question

I'm practicing recursion in Kotlin and got other results when running 2 functions below:

tailrec fun fac1(n: Long): BigInteger {
    if(n == 1L)
        return BigInteger.ONE
    else
        return n.toBigInteger() * fac1(n-1)
}
println("fac1(10000) = ${fac1(10000)}")

result of fac1(10000): Exception in thread "main" java.lang.StackOverflowError

tailrec fun fac2(n: Long, a: BigInteger = BigInteger.ONE): BigInteger {
    return if(n == 1L) a else fac2(n -1, a * n.toBigInteger())
}
println("fac2(10000) = ${fac2(10000)}")

fac2(10000) can execute and return results : fac2(10000) = 284625968091705451890.....

Can someone explain to me the difference between these 2 functions and why function 2 can execute while function 1 is not?

Answer 1

These functions are relying on a concept called tail recursion, signalled by the tailrec modifier. Tail recursion allows a recursive function to call itself indefinitely without filling up the stack. It relies on the fact that the recursive call (the bit where the function calls itself) is the last call in the method. For more on how and why this works, consider reading some of the Wikipedia entry on tail calls. Here's a small excerpt:

When a function is called, the computer must "remember" the place it was called from [...] so that it can return to that location [...] once the call is complete. Typically, this information is saved on the call stack [...]. For tail calls, there is no need to remember the caller – instead, tail call elimination makes only the minimum necessary changes to the stack frame before passing it on, and the tail-called function will return directly to the original caller.

The problem with your first function is that it's not really tail recursive. For a function to be tail recursive, calling itself must be the very last thing it does.

But to execute the line n.toBigInteger() * fac1(n-1), you first have to execute fac1(n-1), and then multiply it by n.toBigInteger(). That means that the last thing the function does is the multiplication, not the call to fac1.

When you compile this code, the compiler should warn you that the tailrec modifier is ineffective here. My compiler gives me this warning:

A function is marked as tail-recursive but no tail calls are found

Because the function isn't tail recursive, it must allocate a new stack frame every time it recursively calls itself. The call stack has limited size, and will eventually become full, leading to a StackOverflowError.

The second function solves this problem by rewriting the function so that the call to fac2 really is the last call in the method. That allows it to properly use tail recursion, meaning that the stack does not fill up.