The Fibonacci numbers are an infamous sequence that can be easily explained and shown to anyone. You start with $1$ and $1$ and for subsequent terms in the sequence, take the last two terms and add them. Simple enough right?

\[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \dots\]

Despite their seemingly innocent nature, they’ve been an object of high interest for many mathematicians, and even computer scientists, alike. This post is intended as a look into the cool and interesting ways that the Fibonacci numbers have helped me learn new things.

(If you want to see some other funky things about Fibonacci, you can look here and here.)

This is going to be a 3 part series about Fibonacci, so be sure to stay tuned.

Introduction

I first encountered the Fibonacci numbers in middle school. My teacher showed me the Vi Hart series of videos (first link above), and they seemed very mystical. There were a lot of interesting things I was shown, such as:

If you take the Fibonacci numbers and get some grid paper, you can construct the spiral by drawing the square of $n$ lengths in a spiral-like fashion and then you can draw a curve like so: Drawing of the Golden Spiral. Fun fact, this spiral’s “growth rate” is what is known as the golden ratio, $\varphi = \frac{1 + \sqrt{5}}{2}$. This number comes up a lot when you talk about the Fibonacci numbers.

I’m not going to explain the golden rectangle, but it has this really cool property of self-similarity that you can take a square with the sidelength of the longer side of the rectangle and appended it on to the rectangle, it would still be a golden rectangle! Isn’t that really cool? Oh, and the ratio between the long and the short side of these rectangles is $\varphi$. Who coulda guessed.

Image of the golden rectangle

In the above image, the red rectangle and the red+blue rectangle are both golden rectangles. How cool!

Recursion

Flash-forward to grade 11. I was taking AP CS A (Computer Science course), and we were talking about recursion. For those unfamiliar with recursion, it’s a tool in programming that allows you to break down a big problem into smaller instances of the same problem. This is useful in computer science for analyzing algorithms, because (for reasons that go outside the scope of this post), the runtime (how long the program takes to execute) of recursive programs can be easily analysed, for the most part.

Turns out, solving for the $n$th Fibonacci number is a problem that can be broken into smaller instances of the same problem. For those who don’t get it, you can define the Fibonacci numbers like this:

$$\text{Fib}_{n} = \text{Fib}_{n-1} + \text{Fib}_{n-2}, n \geq 2$$ and also:
$$\text{Fib}_0 = 1, \text{Fib}_{1} = 1$$

This is known as a recurrence relation (by mathematicians), but it allows us to make some recursive code using our good old friend, the Fibonacci numbers.

For any programmer who’s seen recursion, they probably know exactly where this is going. AP CS A is taught in Java, so this is what we were first shown:

public int fib(int n){
    if (n == 0 || n == 1){
        return 1;
    } 
    return fib(n - 1) + fib(n - 2);
}

Yay! Recursion!

Fun fact for the programmers reading this, PHP (yeah, that ugly thing), has a recursive name!

Why is this relevant at all? Well, recursion is a really important and fundamental concept in computer science. It’s used in (the most efficient) sorting algorithms, super useful data structures, searching algorithms, (and as you’ll find), one of the most important algorithms to date (I will talk about this in a later post)! In hindsight, I find it really interesting that the Fibonacci numbers are were used as my introduction to this topic!

Dynamic Programming

Dynamic Programming is a pretty cool concept. In grade 11 (still), I learnt from my friend that you can “optimize” the above code.

What? The code was not optimal?

Yes. While it was correct (it would give the correct answer), it would run very slowly on larger inputs of $n$. Here’s an example, for fib(7): fib(7) call tree

These are all the times that fib(n) is “called”. Notice how there are duplicate calls. This can be fixed!

In dynamic programming, we can fix this, by storing out previous results. Here’s the solution, in Java.

public int fib(int n){
    ArrayList<Integer> result = new ArrayList<Integer>();
    result.add(1);
    result.add(1);
    for (int i = 0; i <= n; i++){
        int fib_n1 = result.get(i-1);
        int fib_n2 = result.get(i-2);
        result.add(fib_n1 + fib_n2);
    }
    return result.get(n);
}

For non-programmers these symbols might look a little scary, but the basic idea is we’re generating all the Fibonacci numbers up to $n$ instead of working backwards. Intuitively, it should make sense why the idea behind this solution is “better” than the recursive solution.

(Note: You can memoize the recursive solution, and it’d become as efficient as the dynamic solution.)

We’ll talk about an even better solution to this problem in the next post, and also get into more of the math behind solving Fibonacci numbers.

Footnote: Memoized Recursive Fibonacci

Turns out you don’t have to do dynamic programming to solve this problem, you can do something similar.

All you have to do is have an array (a list of elements that are indexed by counting numbers), such that A[i], the array at the $i$th element, is equal to the $i$th Fibonacci number if it has already been calculated.

Now, instead of computing the Fibonacci numbers by recursive call, first check if A[i] is not zero, and if it’s not zero you can just return it! Otherwise, use the recursive calls to calculate it.

It should be convincing why this solution will compute each Fibonacci number once and only once, and hence will be similar in efficiency to the Dynamic Programming solution.