You may have studied the Fibonacci sequence in school, but it’s also useful to know how to work with Fibonacci numbers as a professional software engineer or web developer, because it’s the kind of thing that job interviewers may ask us questions about when they want to test our knowledge or gauge our ability to think through a problem.

Getting to Grips With Some Fibonacci Numbers

The important thing to know is that there’s nothing difficult about the Fibonacci sequence: it’s just a never-ending list of numbers that was named by the medieval Italian mathematician Leonardo Bonacci (more commonly known by his nickname Fibonacci).

The first two numbers in the sequence are defined by default: they are 0 and 1. All of the other numbers in the sequence are defined based on a simple rule, where each number is simply the sum of its previous two numbers.

Below we’re going to look at various ways to code the solution to a specific problem: how to calculate the n-th Fibonacci number from the sequence. Because programming languages like Golang are zero-indexed, the first number in the sequence will really be the 0-th and the second will be the 1-st.

So if we have a function fibonacci(n) that returns the n-th number, fibonacci(0) will return 0 and fibonacci(1) will return 1, as discussed above. Then fibonacci(2) will return 1, which is the sum of the previous two numbers (0 and 1), fibonacci(3) will return 2, which is a similar sum (of 1 and 1), fibonacci(4) will return 3 and fibonacci(5) will return 5. You get the idea.

The Simplest Recursive Solution

Let’s see if we can use the definition above to create a Go function that behaves as we described. We can call the function recursively if n is greater than or equal to two:

package main

import "fmt"

func fibonacci(n uint) uint {
	if n < 2 {
		return n
	}

	return fibonacci(n-1) + fibonacci(n-2)
}

func main() {
	fmt.Println(fibonacci(10))
}

This works well, but it struggles when the parameter n is a large value. This is because of the way the function is defined recursively: the number of times the function has to call itself grows exponentially as n grows.

For example, try running the code with fibonnacci(100), and the program will probably be very slow or even crash, unless you’re running it on an extremely high-performance machine.

A Little Speedy Cache Solves Our Problem

However, we can make the function much faster simply by employing the use of a cache.

If we save the value of fibonnacci(n) for every n when we first encounter it, then we won’t have to keep repeating the same recursive function calls to recalculate it.

Running the code below should, on most computers, now be able to produce a result even for fibonnacci(1000) in a reasonable amount of time, which is especially impressive considering that n is an order of magnitude greater here than it was when our previous code struggled:

package main

import "fmt"

var (
	fibonacciCache = make(map[uint]uint)
)

func fibonacci(n uint) uint {
	if n < 2 {
		return n
	}

	if result, ok := fibonacciCache[n]; ok {
		return result
	}

	result := fibonacci(n-1) + fibonacci(n-2)

	fibonacciCache[n] = result

	return result
}

func main() {
	fmt.Println(fibonacci(1_000))
}

This is a great example of how important the data structures and algorithms that we use in our code are, since they can have a huge impact on the performance of our compiled program.

What would have been very slow or impossible to calculate using the original code, now becomes fast, with the use of nothing more complicated than a map to cache values, so they don’t need to be recalculated multiple times. (This technique is known as memoization.)

Let’s Make It Iterative

But what if we don’t want to use recursion at all?

It seems unnecessary to have to keep calling the same function just to calculate a single number, and indeed it is.

In fact, it’s true that any recursive function — with no exceptions — can be converted into an iterative function: you just need to work out how to do it.

package main

import "fmt"

func fibonacci(n uint) uint {
	if n < 2 {
		return n
	}

	var a, b uint

	b = 1

	for n--; n > 0; n-- {
		a += b
		a, b = b, a
	}

	return b
}

func main() {
	fmt.Println(fibonacci(100))
}

The code above works in exactly the same way as the previous versions. It has the advantage, however, of not needing a cache for performance, since it does not do the same amount of repetitive work that the others did.

That is, of course, a very real advantage, since it simplifies our code, and it also makes it easier to run the function concurrently, without worrying about the problems that can be caused by multiple goroutines writing to the same map at once that we discussed in a previous post on this blog.

The Bigger, the Better

We’ve improved the performance, but there’s still a limit to how high in the Fibonacci sequence we can go.

The problem isn’t caused because we lack processing power or memory. It’s rather because Fibonacci numbers get very big very fast: even if we used a uint64, we would soon overflow the data type.

It seems obvious then that we need to use a different return type in our fibonacci function, one that can hold arbitrarily large integers.

package main

import (
	"fmt"
	"math/big"
)

func fibonacci(n uint) *big.Int {
	if n < 2 {
		return big.NewInt(int64(n))
	}

	a, b := big.NewInt(0), big.NewInt(1)

	for n--; n > 0; n-- {
		a.Add(a, b)
		a, b = b, a
	}

	return b
}

func main() {
	fmt.Println(fibonacci(5_000))
}

Above we use the "math/big" package from the Go standard library, so that we can create extremely large integers.

The a.Add(a, b) function performs an addition using its two arguments and then stores the result in the receiver, which in this case is a.

It is now possible to produce huge results that a primitive data type wouldn’t have been able to hold, such as where n is 5,000.

Generating the Fibonacci Sequence Using Goroutines and Channels

Until now, we’ve only been printing out the n-th number in the Fibonacci sequence, but, in the following example, we’ll print out every number in the sequence up to n.

A natural way to do this in Golang is by spinning up a goroutine that continually sends Fibonacci numbers to a channel, and we’ll just consume as many of them as we need.

package main

import (
	"fmt"
	"math/big"
)

func fibonacciGenerator(c chan<- *big.Int) {
	a, b := big.NewInt(0), big.NewInt(1)

	for {
		c <- a

		a, b = b, a
		a.Add(a, b)
	}
}

func main() {
	const n = 1000

	c := make(chan *big.Int)

	go fibonacciGenerator(c)

	for i := 0; i < n; i++ {
		fmt.Println(<-c)
	}
}

You can see how it would clearly have been possible to keep this code running infinitely (or at least until the computer breaks down), if we had used a for loop with no conditions.

However, this is unlikely to be practical, unless perhaps you wanted to create a web server that would greet each user with a different Fibonacci number.

Final Thoughts on the Fibonacci Sequence

The Fibonacci sequence has an important history in mathematics and computer science. But it actually turns up in all kinds of surprising places: in nature, many plants, for example, have a total of 3, 5, 8, 13, 21, 34 or 55 petals on their flowers.

The sequence is especially important for programmers, because it has also been used as part of more sophisticated algorithms and data structures, such as Fibonacci search, which I plan to write a post about in the future.