Oct 12, 2018 · 8 min read

It’s hard to take an algorithms 101 class without encountering the Fibonacci sequence. The sequence is deeply connected to the golden ratio, which appears over and over again in nature, architecture, art, and the occasional Dan Brown novel. From conch shells to sacred geometry, the Golden Ratio appears to be encoded into many aspects of our universe.

Enumerating everywhere the golden ratio appears would be quite an undertaking, but one of my favorite places where it appears is inside of itself. A recursion inside a recursion; a mathematical inception; what Hofstadter might call a “strange loop.”

In computer science the sequence — and the different strategies for computing it — are also good teaching tools. The Fibonacci sequence can be computed with a clean and simple example of recursion:

As a computer science instructor, I have watched numerous faces scrunch up in confusion when seeing this function for the first time. “You can call a function from inside itself?” they might ask, “How the heck does that work?!” Admittedly, I take a small amount of pleasure in my students’ confusion. Confusion is an integral part of learning, and if a student is never confused I tend to feel that they aren’t being challenged enough.

One of the most wonderful things about this implementation of the Fibonacci sequence is that the code very closely matches the very definition of the sequence.

The sequence was first described in 1202 by Leonardo Fibonacci. The sequence starts with two 1’s, and subsequent digits are computed by adding the previous two digits together. So for the 3rd digit, 1 + 1 = 2, and the 4th digit 1 + 2 = 3, then 2 + 3 = 5… Here are the first few digits:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 …

The Python code above reads just like that definition — if n is 0 or 1, return 1, otherwise, return the result of adding fib(n-1) to fib(n-2), AKA return the sum the previous two digits of the sequence. In addition to the sequence itself, Fibonacci discovered the sequence’s relationship to the golden ratio.

The golden ratio is an irrational number. Like 𝞹 (Pi), it has an infinite number of digits past the decimal and never falls into a repeating pattern. Just like most people remember 𝞹 as 3.14, it’s good enough to remember the golden ratio as 1.618. Also like Pi, the golden ratio has a Greek letter representation, namely 𝝓 (Phi). Dividing the nth digit by the (n-1)th digit in the sequence approximates the golden ratio, and the further into the sequence you go, the better the approximation:

5/3 = 1.666
8/5 = 1.6
13/8 = 1.625
21/13 = 1.61538461538

In algorithms 101 you’ll also learn that the code above is slow — but you might not learn that it is slow in a way that is closely related to 𝝓.

The code above can be modeled with a tree (in fact all recursive functions can be). Every recursive call represents an internal node in the tree, and every base-case represents a leaf node. The tree for fib(5) looks like this:

In a lot of algorithms classes you’ll quickly classify this function as O(2^n). Each function call essentially results in two more functions being called — a near perfect example of exponential doubling. Said another way, the tree representing our code has a branching factor of 2; each node has 2 children, so at each new depth of the tree the number of nodes doubles. 1 node becomes 2 becomes 4 becomes 8…

Perhaps you move on to optimizing this function with Dynamic Programming, which will yield a linear time solution. Perhaps you move on to discussing recursion more generally and how to think about this function’s execution. Both are worthy causes, but the chance to explore a curious and beautiful mathematical oddity is often passed over.

Big O notation is a fuzzy lens, where estimation is both encouraged and required. But is this function’s growth pattern really exponential doubling? Consider this code which times the execution of the fib function defined above:

Even a clumsy empirical analysis reveals a hint of our strange loop. After 32 digits, the time elapsed begins to take a familiar shape…

n  fib(b)    time_elapsed
32 3524578 1
33 5702887 1
34 9227465 2
35 14930352 3
36 24157817 5
37 39088169 8
38 63245986 13

Computers and clocks and interpreters are messy, and the time_elapsed value slowly becomes a worse approximation of the Fibonacci series:

n  fib(b)     time_elapsed
39 102334155 24
40 165580141 37
41 267914296 59
42 433494437 95
43 701408733 155
44 1134903170 253

Nevertheless, the messy business of implementation has (in this case) revealed a theoretical truth. The recursive method for computing the nth digit of the Fibonacci sequence has an algorithmic complexity that mirrors the Fibonacci sequence itself. If this algorithm were truly an O(2^n) algorithm, we would see the amount of time roughly double, but that’s not what we see.

We can model the complexity of our function using a recurrence relation — a formal mathematical language for describing recursive functions. Don’t be intimidated by the “formal mathematical language,” this should look familiar:

f(n) = f(n-1) + f(n-2)

The amount of work it takes to compute the nth digit is the amount of work it took to compute the previous two digits combined, which of course looks a lot like the function itself. Said another way, the number of leaf nodes in our “recursive tree” for computing the nth digit of the sequence mirrors the value of that nth digit.

Let’s take a concrete example:

f(5) = f(4) + f(3)
f(4) = f(3) + f(2)
f(3) = f(2) + f(1)
f(2) = f(1) + f(0)

Both f(1) and f(0) are constant work in our case, and we simply return 1 in both of those cases so we can say:

f(1) = 1
f(0) = 1

If we add it all up from the bottom:

f(2) = 1 + 1 = 2
f(3) = 2 + 1 = 3
f(4) = 3 + 2 = 5
f(5) = 5 + 3 = 8

And we know where this is going, but let’s take a look at what happens when we expand the formulas for f(5), instead of solving them by inserting the real values:

f(5) = f(4) + f(3)
f(5) = [f(3) + f(2)] + [f(2) + f(1)]
f(5) = {[f(2) + f(1)] + [f(1) + f(0)]} + {[f(1) + f(0)] + f(1)}
f(5) = {f(1) + f(0) + f(1) + f(1) + f(0)} + {f(1) + f(0) + f(1)}

Each of these f(0) and f(1)s are the leaf nodes in our tree, and they all evaluate to the number 1.

Is there is a better way than this expansion to model this relationship? Can we write a formula that describes how many f(0)’s and f(1)’s there will be in the expansion of any particular f(n)? It turns out there is. Buckle up, we’re entering the realm of calculus.

Many recurrence relations (this one included) are essentially geometric series. Let’s consider a recurrence relationship that (roughly) models the population growth of bacteria.

f(n) = 2*f(n-1)

Because each bacterium becomes two bacteria at each timestep, the population of bacteria is always twice as large as the previous timestep. If we start with 1 bacterium, then in the next timestep there will be 2 bacteria, then 4, then 8, then 16, then 32. This is the exponential function f(n) = 2^n.

Let me call your attention to just how similar this recurrence is to the one for the Fibonacci sequence by reminding you that multiplication is just repeated addition:

f(n) = 2 * f(n-1) = f(n — 1) + f(n — 1)

Side by side then:

f(n) = f(n — 1) + f(n — 1) = 2^n
f(n) = f(n — 1) + f(n — 2) = ???

We have every reason to believe that the second recurrence will also display exponential growth, but it should grow slower than 2^n. Said another way, the recursive tree for our bacterial growth function will have more nodes than our tree for fib — even though in both trees a node has either 2 or 0 children. The two are similar, but not the same.

It turns out that for, “linear homogeneous recurrence relations with constant coefficients,” we can use a neat trick to find a closed form solution to the recurrence relationship. Lucky for us Fibonacci is such a recurrence. Therefore, it’s possible to write a single formula in terms of n that represents the Fibonacci sequence without using recursion (or even iteration!).

A proof of this trick, called the “distinct roots theorem,” can be found here.

We know the relationship is exponential growth, this trick helps us find the “roots” of that exponential function. The trick itself is quite simple: take the subscripts of our function f, and turn them into exponents on a variable r (for root) which we will then solve for.

Here is the trick applied to bacterial growth:

f(n) = 2f(n-1)
r^n = 2r^n-1
r = 2

In the last step, we divided each side by r^n-1. We’ve shown that this trick resulted in the same answer we found above, that bacterial growth is modeled by the exponential 2^n.

Now lets try Fibonacci:

f(n) = f(n-1) + f(n-2)
r^n = r^n-1 + r^n-2
r^2 = r + 1 ; [divide both sides by r^n-2]
r^2 — r — 1 = 0

We can now solve for r by using the quadratic formula.

r = [1 +- sqrt(1 — (4*(-1)))] / 2
r = (1 + sqrt(5)) / 2
r = (1 — sqrt(5)) / 2

Something remarkable has happened, even if you didn’t notice it. Punch 1 + sqrt(5) / 2 into a calculator and you get …. 1.618: 𝝓, the golden ratio. Wow.

Not losing the forest for the trees, what we have shown here is something we’ve already shown experimentally — that the growth of the digits in the Fibonacci sequence is an exponential function, and that specifically the root of that exponent is 1.618. When we showed that the nth digit divided by the (n-1)th digit approximated 𝝓, we also showed that (essentially) multiplying the (n-1)th digit by 𝝓 would result in the nth digit.

(Aside: The second root is another number, sometimes called 𝝍 (Psi), which is similar to the golden ratio, it roughly equals -0.618)

Although it’s technically accurate to say the Big O upper bound of our recursive function above is O(2^n) I hope you agree it is much more satisfying to know that a tighter bound is O(𝝓^n).

The next part of the distinct roots theorem says that if our recursion is a “linear homogeneous recurrence relations with constant coefficients” that we can not only put an upper bound on its growth (as we did just now) we can actually find a closed form solution to the recurrence.

I’ll leave the proof of this remarkable fact as an exercise for the reader. This is Binet’s Formula, and it is a formula (not a process) for determining the nth digit of the Fibonacci sequence:

f(n) = (𝝓^n - 𝝍^n) / sqrt(5)

Incredible.

Written by

## Teb’s Lab

#### Teb’s Lab is a publication dedicated to educational content with a strong bend towards the overlap between programming and the sciences.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just \$5/month. Upgrade