Kotlin: Tail recursion for mutually recursive functions

Question

Suppose I write code as follows:

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 works for single-function recursion, but no more complicated. I also see a warning that no tail calls were found where the tailrec keyword is tailrec . Perhaps this is too complicated for compilers?

Answer 1

What you are looking for is the “right tail calls”. The JVM does not support them, so you need trampolines .

A proper tail call clears the memory of its own function (parameters, local variables) before jumping (instead of calling) into a function called the tail. Thus, a function called a tail can return directly to its calling function-calling. Infinite mutual recursion is possible. (In functional languages, this is one of the most important functions.)

To enable the correct tail calls in assembler, you need a command to geto to a routine / method called through a pointer. OOP needs calls (storage location to go back to the stack and then go) to the procedure / method that is referenced through a pointer.

You can emulate the right tail calls with a trampoline design pattern, maybe there is some support through the library. A trampoline is a while loop that calls a function that returns a link to the next function, which returns a link to the next ...

Answer 2

According to wikipedia https://en.wikipedia.org/wiki/Tail_call :

tail call is a subprogram call executed as the final action of a procedure. If calling the tail can cause the same routine to be called again in the call chain, the routine is called tail recursive

So, your case is not tail recursion by definition. Here is what warns.

Currently, the compiler cannot optimize this, mainly because it is a very rare situation. But I'm not sure even Haskel will optimize this.

Answer 3

Here is the implementation of the @comonad trampoline proposal. He works!

 import kotlin.reflect.KFunction typealias Result = Pair<KFunction<*>?, Any?> typealias Func = KFunction<Result> tailrec fun trampoline(f: Func, arg: Any?): Any? { val (f2,arg2) = f.call(arg) @Suppress("UNCHECKED_CAST") return if (f2 == null) arg2 else trampoline(f2 as Func, arg2) } fun odd(n: Int): Result = if (n == 0) null to false else ::even to n-1 fun even(n: Int): Result = if (n == 0) null to true else ::odd to n-1 fun main(args:Array<String>) { System.out.println(trampoline(::even, 9999999)) }