I didn’t realize it until I noticed the trending topic on Twitter, but Saturday, November 23 was Fibonacci Day. That gave me an opportunity to drag out one of my favorite old jokes:
For those unaware or who don’t remember, the Fibonacci series starts with 0 and 1, and then each subsequent number is the sum of the previous two. The Fibonacci numbers are thus 0, 1, 1, 2, 3, 5, 8, 13, …. By the definition, the “zeroth” Fibonacci number F0 = 0, the first F1 = 1, the second F2 = 1, the third F3 = 2, and so on.
(Note the gag only works in the U.S., because we express our dates as month/day/year rather than day/month/year like the rest of the world. For us, November 23 is 11/23, thus Fibonacci day, ha ha. Sorry about the US-centric approach. On the other hand, there’s no 23rd month, so the rest of the world would miss out on Fibonacci day, and that would be sad.)
Naive Recursive Implementation
The Fibonacci algorithm is a classic example of a recursive function, expressed as Fn = Fn-1 + Fn-2:
fib(n) = fib(n - 1) + fib(n - 2)
The problem with a naive implementation of that algorithm is that the amount of duplicated work grows exponentially. For example,
fib(5) = fib(4) + fib(3)
= fib(3) + fib(2) + fib(2) + fib(1)
= fib(2) + fib(1) + fib(1) + fib(0)
+ fib(1) + fib(0) + 1
= fib(1) + fib(0) + 1 + 1 + 0 + 1 + 0 + 1
= 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1
= 5
Yikes, and that’s just for the fifth Fibonacci number. The problem is that intermediate results aren’t being saved, so each number is recalculated over and over again, and the higher you go, the more duplicated work there is.
Tail Call Optimization
In Kotlin, there are several ways to fix this. One is to use tail recursion, which involves replacing recursion with iteration. An implementation in Kotlin can take advantage of the tailrec keyword:
@JvmOverloads
tailrec fun fibonacci(n: Int, a: Int = 0, b: Int = 1): Int =
when (n) {
0 -> a
1 -> b
else -> fibonacci(n - 1, b, a + b)
}
There’s a fair amount going on here. First, in order to write a recursive function as a tail call, the recursive call itself has to come last in the implementation. In this example, the last evaluated expression is the else clause in the when loop, which calls the function again.
Also, when you write your function to be called recursively, you need to use an additional parameter to act as the accumulator. Here, n is the nth desired Fibonacci number, the value of b is the previous value, and the value of a is the one before that. In the recursive call, the new value of b is the current value of b plus the value of a, so that is effectively the accumulator.
The next interesting part is that the return type is specified explicitly. Normally in Kotlin when you implement a function as a single expression (using an = sign at the end of the signature) you can leave out the return type. If you do that in this case, however, IntelliJ IDEA complains with “Type checking has run into a recursive problem. Easiest workaround: specify types of your declarations explicitly.” Yeah, okay, I can do that, thus the a : Int at the end of the signature.
The next good part is using default values for the second and third arguments in the function. By initializing a to 0 and b to 1, the function can be invoked as fibonacci(10) without giving values for the other two parameters. That’s the way you want to call the function anyway, so that’s helpful. Unfortunately, Java doesn’t support default parameters, so to make sure the compiler generates overloads that Java can see, the JmvOverloads annotation is added. Now the fibonacci function can be called from Java with only a single argument.
That leads to the best part, which is the tailrec modifier. You could write this tail call algorithm directly in Java, but it wouldn’t save any memory. In Kotlin, however, this page in the reference guide says that compiler will automatically “optimize out the recursion, leaving behind and fast and efficient loop version instead.”
If you play the game in IntelliJ where you “Show Kotlin Bytecodes” and the hit the Decompile button, the resulting Java code looks like:
@JvmOverloads
public static final int fibonacci(int n, int a, int b) {
while(true) {
int var10000;
switch(n) {
case 0:
var10000 = a;
break;
case 1:
var10000 = b;
break;
default:
var10000 = n - 1;
int var10001 = b;
b += a;
a = var10001;
n = var10000;
continue;
}
return var10000;
}
}
The recursive call has been implemented as a while(true) loop with the accumulator in the default section.
Kotlin fold and reduce
That’s all well and good, and normally I’d go on to discuss ways to test this function, but there are a couple of alternative ways to implement the algorithm. One is this particularly interesting version:
fun fibonacciFold(n: Int) =
(2 until n).fold(1 to 1) { (prev, curr), _ ->
curr to (prev + curr)
}.second
Now that’s poetry, in that it’s simple, elegant, and really needs to be explained before it makes any sense. First of all, credit where credit is due. This is from Marcin Moskala (@marcinmoskala on Twitter). He included it in a blog post at Kotlin Academy, based on one of his tweets.
His first example, fib1, is the inefficient recursive algorithm. His second, fib2, is an iterative version of the same. The third one, fib3, is like the tail-call version described above. Finally, the last one, fib4, is the one I want to talk about, repeated in the syntax block prior to the tweet.
First, the expression (2 until n) is a range that runs from 2 to n - 1. An inclusive range would be 2..n.
Next comes the fold function. Kotlin has both fold and reduce functions. The fold function takes two parameters, while reduce only takes one:
inline fun <T, R> Iterable<T>.fold(
initial: R,
operation: (acc: R, T) -> R
): R
inline fun <S, T : S> Iterable<T>.reduce(
operation: (acc: S, T) -> S
): S
Each of them applies the provided operation to each element of the Iterable, and the last evaluated expression from the operation becomes the new value of the acc (accumulator) argument on the next iteration. The difference is that fold takes an initial value for the accumulator, while reduce uses the first element from the sequence to initialize the accumulator.
For those more familiar with Java, the reduce function on Java streams behaves the same way, except that it is overloaded to take either a single BinaryOperator (like Kotlin’s reduce) or two values, where the first is an initial value called identityand the second is a BinaryOperator (like Kotlin’s fold). Note that in Java they refer to the first argument as identity rather than initial, which is more in keeping with the theory of functional programming. In either case the first argument is used as the initial value of the provided operation accumulator, but it’s supposed to be the identity value for the binary operator. The Kotlin implementation works the same way, but doesn’t stress that distinction.
Returning to the Fibonacci calculation, the fold function uses the Pair of 1 to 1 as its initial value, so the operation needs to return a new instance of Pair each time. There are two arguments to the lambda provided as the operation. The first argument is also a Pair, which acts as the accumulator, and the second argument would be each value in the range from 2 to n - 1. The algorithm doesn’t actually need those values, so the implementation just uses an underscore to indicate they’re ignored.
The implementation of the operation creates a new Pair whose first element is the current value and whose second element is the sum of the previous value and the current value. Finally, when the limit of the range is reached, the function returns the second element from the Pair as the desired value.
As usual with a fold function, it’s easiest to understand if you see it in action. Here is a version of it with the previous and current values written out each time:
fun fibonacciFoldDebug(n: Int) =
(2 until n).fold(1 to 1) { (prev, curr), _ ->
println("prev=$prev, curr=$curr")
curr to (prev + curr)
}.second
Here is the output of F(10):
prev=1, curr=1 prev=1, curr=2 prev=2, curr=3 prev=3, curr=5 prev=5, curr=8 prev=8, curr=13 prev=13, curr=21 prev=21, curr=34 Fib(10) == 55
The initial Pair of 1 to 1 initialized the prev and curr variables, which take new values as described in the fold operation. Once again, a recursive problem has been transformed into an iterative one, but this time in a really beautiful way. You can comfortably compute Fibonacci numbers as far as Int values work, and if you need something higher just reimplement this with BigInteger (and replace + with add) and keep going.
Sequences
There’s one more fundamentally different approach to the same problem, this time using sequences. A sequence in Kotlin is just like a stream in Java, in that values go through a series of intermediate operations followed by a terminal operation, and no data is pulled through the sequence until there is a terminal operation.
There are several ways to create a sequence in Kotlin, from the asSequence function on collections to the generateSequence function that takes a lambda to evaluate for each element. There is also, however, the basic function called sequence:
fun <T> sequence(
block: suspend SequenceScope<T>.() -> Unit
): Sequence<T>
The sequence function is a suspend function (so it can be used with coroutines) that takes a lambda with a receiver. The lambda takes no arguments and returns nothing (i.e., Unit), and the receiver is an instance of SequenceScope. The documentation says the function returns a sequence by lazily yielding values one by one.
In fact, that documentation page actually contains a Fibonacci example, repeated here:
fun fibonacci() = sequence {
var terms = Pair(0, 1)
// this sequence is infinite
while (true) {
yield(terms.first)
terms = Pair(terms.second, terms.first + terms.second)
}
}
Look familiar? The iteration occurs over Pair instances, as before, in an infinite loop. The yield function “yields a value to the Iterator being built and suspends until the next value is requested.” Note that this returns a sequence, so to invoke it you need to add a terminal operation. The way the code in the documentation example calls this function is:
println(fibonacci().take(10).toList())
The take function is another intermediate operation that requests ten elements, and toList is, at long last, a terminal operation which converts the sequence into a List. The code prints the first 10 Fibonacci numbers in a list, [0, 1, 1, 2, 3, 5, 8, 13, 21, 34].
Wow, right? Lots of ways to solve the same problem. Of course, any functions like this need to be tested. That, too, can be an interesting story, which I’ll leave for the next blog post in this series.
As always, all the code (including extensive JUnit 5 tests) from this post can be found in this GitHub repository for my new book, the Kotlin Cookbook.
Leave a Reply