The beauty of recursion

March 02, 2019 3 minutes reading time Development kotlin fp

One of the first books I read on functional programming was Programming in Haskell by Graham Hutton. Within the very first pages, he presented a version of the Quicksort algorithm:

qsort []     = []
qsort (x:xs) = qsort ys ++ [x] ++ qsort zs
               where
                 ys = [a | a <- xs, a <= x]
                 zs = [b | b <- xs, b > x]

Wow! I really was struck by its beauty.

One part of what impressed me there was that you could read it almost like prose and how easy it was to understand once you know the syntax a little:

• the result of qsort on an empty list results in an empty list
• for everything else the list is split in its head element x and the remaining elements xs (the s indicates the plural, the x’s are normally more than one element)
• the x and the xs are then used to calculate the result, using these two definitions:
  • first ys is calculated by taking all the elements from xs that are less or equal to x
  • zs are all the other elements, those that are greater than x
• the result is qsort of all elements except x that and are less or equal to x, combined with the element x, and then combined with qsort of all elements that are greater than x (I’m not using the terms ys and zs here, but what they stand for)

What was even more impressive was that the entire process unfolded in front of my mind’s eye. Looking at the code seemed to be enough to grasp the essence of it. That was the day I fell in love with recursion.

What I recognized was that qsort will not perform well if the list is already in order: the partitioning will result in an empty list (the ys) and all the remaining elements (the zs). The depth of the recursive calls will thereby be approximately the number of elements in the list, n. In the best case, the elements will be evenly distributed between ys and zs, thereby having a depth in the order of log(n).

Be warned: although recursion can make algorithms easier to understand, it has its downsides. For every recursive call, a new stack frame is created. With many recursive calls, this can easily consume all your stack space and you might run out of it.

You can use tail-recursive functions and some languages can optimize stack space usage by replacing the current stack frame with the new one resulting from the call. That’s possible because no information left within the current stack frame is needed when the function call returns. It’s easily recognizable by the fact that the return value is only one recursive function call and nothing else. But even though your calls are tail-recursive might not save you, because the platform does not support the optimization, e.g. stable Node.js as of now. In Kotlin on the JVM, this is not a problem, because it supports proper tail-call optimization.

I rewrote the recursive Quicksort in Kotlin. Separating the list in its head and tail is not as elegant. You could use destructuring for that, but then an intermediate Pair will be created. It uses an extension function (part of Kotlin’s standard library) that can partition a list more easily:

fun <T : Comparable<T>> qsort(list: List<T>): List<T> = when {
    list.isEmpty() -> list
    else -> {
        val x = list.first()
        val xs = list.drop(1)
        // Alternative: val (x, xs) = list.first() to list.drop(1)
        val (ys, zs) = xs.partition { a -> a <= x }
        qsort(ys) + x + qsort(zs)
    }
}

The Haskell version of qsort looks nicer.

Recursion might not be your best bet when it comes to performance or production readiness, but it’s a beautiful device for understanding.