Kotlin: Tail recursion for mutually recursive functions

Question

Suppose I write code like this:

tailrec fun odd(n: Int): Boolean =
        if (n == 0) false
        else even(n - 1)

tailrec fun even(n: Int): Boolean =
        if (n == 0) true
        else odd(n - 1)

fun main(args:Array<String>) {
    // :( java.lang.StackOverflowError
    System.out.println(even(99999))
}

How do I get Kotlin to optimize these mutually recursive functions, so that I can run main without throwing a StackOverflowError? The tailrec keyword works for single-function recursion, but nothing more complicated. I also see a warning that no tail-calls are found where the tailrec keyword is used. Perhaps this is too hard for compilers?

Answer 1

By wikipedia https://en.wikipedia.org/wiki/Tail_call :

a tail call is a subroutine call performed as the final action of a procedure. If a tail call might lead to the same subroutine being called again later in the call chain, the subroutine is said to be tail-recursive

So your case is not a tail recursion by definition. That't what the warning says.

Currently there is no way compiler will optimise that, mostly because it is a very rare situation. But I am not sure that even Haskel optimises that away.

Answer 2

What you are looking for are "proper tail calls". The JVM does not support those, so you need trampolines.

A proper tail call cleans up the memory of its own function (parameters, local variables) before jumping (instead of calling) to the tail called function. That way the tail called function can return directly to its caller-caller-function. Infinite mutual recursion is possible. (In functional languages this is one of the most important features.)

To allow proper tail calls in assembler you would need a command to jump (goto) to a routine/method that is referred to via pointer. OOP needs calls (stores location to jump back to on the stack and then jumps) to a routine/method that is referred to via pointer.

You can emulate proper tail calls with the trampoline design pattern, maybe there is some support via library. The trampoline is a while loop that calls a function which returns a reference to the next function which returns a reference to the next...