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.
https://en.wikipedia.org/wiki/Recursion_(computer_science)
This is the 4th post in the Exercises in Programming Style focus series.Other posts include:
- Introducing Exercises in Programming Style
- Exercises in Programming Style, stacking things up
- Exercises in Programming Style, Kwisatz Haderach-style
- Exercises in Programming Style, recursion (this post)
- Exercises in Programming Style with higher-order functions
- Composing Exercises in Programming Style
- Exercises in Programming Style, back to Object-Oriented Programming
- Exercises in Programming Style: maps are objects too
- Exercises in Programming Style: Event-Driven Programming
- Exercises in Programming Style and the Event Bus
- Reflecting over Exercises in Programming Style
- Exercises in Aspect-Oriented Programming Style
- Exercises in Programming Style: FP & I/O
- Exercises in Relational Database Style
- Exercises in Programming Style: spreadsheets
- Exercises in Concurrent Programming Style
- Exercises in Programming Style: sharing data among threads
- Exercises in Programming Style with Hazelcast
- Exercises in MapReduce Style
- Conclusion of Exercises in Programming Style
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
|
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.