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 F_{0} = 0, the first F_{1} = 1, the second F_{2} = 1, the third F_{3} = 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 F_{n} = F_{n-1} + F_{n-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 `identity`

and 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