Recursive functions without stack overflow in Kotlin

[robinpokorny]

While Recursion and Looping are theoretically interchangeable, they differ in two main areas: developer experience and space-time footprint.

In my (FP-biased) opinion, recursion almost always has a better DevX. But it has some performance penalty, which comes down to using the call stack.

To fight that, one might use tail call optimised recursion. For that Kotlin has the tailrec modifier. Yet, not all recursive functions can be (easily) transformed to it. And, you could still reach the end of the stack (StackOverflowError).

Side note: I was quite sad that the tail call optimisation was dropped from node.js (yep, it was there at one point).

This is where the deep recursive functions in Kotlin come into play. It's a built-in utility that uses the heap instead of the stack for the recursion. The use is rather straightforward.

Here is an example of an in-order traversal of a binary tree from my Exercism solution:

val inOrder = DeepRecursiveFunction<Node<T>?, List<T>> { node ->
    if (node == null) emptyList<T>()
    else callRecursive(node.left) + listOf(node.data) + callRecursive(node.right)
}

For more details see the deep recursive functions in Kotlin 1.7 announcement.

So, this is quite handy and I expect I'll use this during the upcoming Advent of Code!