Jun 2, 2019 / EXERCISE, PROGRAMMING, STYLE

Exercises in Programming Style, recursion

This week’s post will be back to fundamentals, as the constraint is to use recursion:

Recursion in computer science is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem (as opposed to iteration). The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.

— Wikipedia
https://en.wikipedia.org/wiki/Recursion_(computer_science)

This is the 4^th post in the Exercises in Programming Style focus series.Other posts include:

Principles of recursion

I already wrote about recursion in the context of applying Functional Programming's approach to the Dijkstra algorithm. Let’s go into the details of its implementation. A recursive function should provide two branches:

A stop branch that returns the final result
A branch that calls the function itself with different arguments

Here’s a simple implementation of the factorial function:

fun fact(n: Int): Int {
    var result = 1
    for (i in 1..n) {
        result *= i
    }
    return result
}

fact(5)

In traditional imperative programming, functions use local variables to accumulate temporary computations. In recursive functions, those variables are replaced by function parameters.

The recursion equivalent of the previous function is the following:

private fun recurseFact(acc: Int, n: Int): Int =
    if (n == 1) acc                                  (1)
    else recurseFact(acc * n, n - 1)                 (2)

fun fact(n: Int) = recurseFact(1, n)                 (3)

fact(5)

1	Stop branch
2	Self-call branch
3	Same as the previous function signature

Note that acc parameter plays the same role as the result local variable in the imperative example.

The following is the function from the exercise. It applies the exact same principles as described in the factorial example:

fun words(rest: List<String>,
                  stopwords: List<String>,
                  words: List<String>): List<String> {
    return if (rest.isEmpty()) words
    else {
        val split = split(rest.last(), stopwords, listOf())
        words(rest.dropLast(1), stopwords, words + split)
    }
}

Issues with recursion

While the recursion code is much more concise than the imperative one, it suffers from a huge issue: function calls are pushed on the thread’s call stack. The infamous StackOverflowError is thrown when the call stack’s size is exceeded.

While the stack size can be set at startup time, it’s nonetheless finite in size.

Command-line options to manage the stack size

-Xss: Standard JVM Hotspot option
-XX:ThreadStackSize: Proprietary option subject to change without notice

To cope with such an issue, Kotlin (and Scala) offers a compiler trick: while the source code is recursive, the compiled bytecode is implemented with standard loops. There are two requirements:

The recursive function call must be the last one. This is called tailed recursion.
The modifier tailrec must be added to the function signature

The words() function above is tail-recursive, hence it’s quite easy to add the tailrec keyword. It can be updated accordingly, so that it will never overflow.

On the opposite, the following function is not tail-recursive because there are two calls using recursion. Hence, the bytecode cannot be optimized.

fun <T> quicksort(list: List<Pair<T, Int>>): List<Pair<T, Int>> =
    if (list.size <= 1) list
    else list.random().let { pivot ->
        val below = filter(list, listOf()) { it.second <= pivot.second }
        val above = filter(list, listOf()) { it.second > pivot.second }
        quicksort(below - pivot) + pivot + quicksort(above)
    }

Conclusion

In general, recursion is a tough nut to crack at first. However, migrating one’s code to use recursion is a simple recipe: just move the local variables to accumulator parameters. The hardest part is to make recursive functions tail-recursive to avoid to overflow the stack. Some functions allow it, some do not.

The complete source code for this post can be found on Github.

Follow @nicolas_frankel

Exercises in Programming Style, recursion

Principles of recursion

Issues with recursion

Conclusion

Exercises in Programming Style with higher-order functions

Exercises in Programming Style, Kwisatz Haderach-style