The famous Fibonacci sequence starts off [1, 1, 2, 3, 5, 8, 13, 21, …] and continues forever. Each number in the series, except the first two, is the sum of the previous two numbers. For example, 3+5=8.

The canonical algorithm to calculate the series uses recursion and is elegant enough to be a common example of a recursive function. But while elegant conceptually, the algorithm is deadly computationally. In this post I’ll look at several ways to dodge the bullet.

The usual recursive algorithm looks something like this:

function fibonacci (n) begin
    if n < 2 begin
        return(1)
    end
    return(fibonacci(n-2) + fibonacci(n-1))
end

Given some number n, the function calculates and returns the nth Fibonacci number. A consequence of this we’ll deal with next is that this can’t generate the sequence, only the requested number.

Note how the function calls itself twice. This means two things: Firstly, as in any recursive function, depth is a concern. Most systems have a physical limit on how big the call stack can be. Secondly, the two calls end up generating the same numbers, but one. (The first one generates one less, but if n is large, this hardly matters.)

A recursive function requires a guarantee that recursion stops, and the fibonacci function stops recursing once n gets below 2, so that isn’t a problem. Besides the usual issues with recursion, the real issue here is repeated calculation of the same numbers. The function is good for illustrating recursion, but straightforward real-world implementations are slow and risk “blowing up the stack”.

To get a sequence of Fibonacci numbers, we need a function that calls fibonacci for each number to generate. Usually, starting with one and following the sequence upwards for as many numbers as desired. A typical function looks something like this:

function fibonacci-sequence (n) begin
    sequence = []

    for x = 1 to n begin
        fibnum = fibonacci(n)
        sequence.add(fibnum)
    end

    return sequence
end

As you might imagine, repeatedly calling fibonacci makes the repeated calculation problem even worse.

To illustrate the problem, here’s a simple implementation of the two functions above in Python:

The variable N (line #1) controls the sequence length. The clicks list (line #2) will store a record of each call to the fibonacci function (lines #4 to #8). On line #6, we add the number passed to the function.

The fibonacci_sequence (lines #10 to #14) uses a list comprehension to create and return the sequence (line #14). This function is called by line #16. The remainder of the script analyzes the clicks list to see how often fibonacci is called for each number in the sequence.

When run, this prints:

Fibonacci Sequence: 15

[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]

3177 clicks

0: 610 
1: 986 
2: 609 
3: 376 
4: 232 
5: 143 
6: 88 
7: 54 
8: 33 
9: 20 
10: 12 
11: 7 
12: 4 
13: 2 
14: 1 

The issue is readily apparent. The fibonacci function is called a total of 3,177 times — over 1,000 times to calculate the first two Fibonacci numbers. This function would be severely limited in how long a sequence it could generate.

I have five Fibonacci sequence algorithms to compare here. All five will use these common resouces:

The fib_seq_print function (lines #1 to #6) is a utility for listing a Fibonacci sequence (which is passed to it). The print_timing function is a utility for printing the timing results of the sequence functions. It takes a name, a length, and the number of nanoseconds the function took.

As a reference for the other algorithms today, here’s the naive Fibonacci algorithm again:

This is the same as the above, but I moved the fib function inside sequence-generating function (lines #4 to #7). In all these, I’ll make a habit of using the abbreviations “fib” and “seq”.

Here’s a function that calls the sequence generator and (optionally) prints the returned sequence. It also times the sequence generation:

When run, this prints:

   1 = 1
   2 = 1
   3 = 2
   4 = 3
   5 = 5
   6 = 8
   7 = 13
   8 = 21
   9 = 34
  10 = 55
  11 = 89
  12 = 144

Canonical Fibonacci[12]     :     71.058 ms

Generating just 12 Fibonacci numbers takes 71 milliseconds. From the test above, we know why. We’d like a way to cache a result once we generate it and just give that back if asked so we don’t have to recurse to generate it again.

Python Decorators offer a generic way to do this without changing the fib function itself. [See Python Decorators, part 1, and part 2, for info.] The Python standard library provides a decorator, cache, in functools suited to the purpose.

For illustration, I’ll implement a simple version of it here:

This decorator function adds an attribute, previous, to the decorator function itself. The attribute contains a dictionary that will contain the results of previous calls. The wrapper function (lines #5 to #10) wraps function (in this case, the fib function).

In the wrapper function, we check to see if we’ve seen n before (line #6). If so, we return the entry from previous (line #7). Otherwise, we call function, passing n, and store the result in previous (line #8 and #9). We also return the result (line #10).

We add it in our sequence function like this:

Note the only change is the addition of the @cache decorator.

The sequence generator test rig is essentially identical to the previous example:

One notable difference is that we can set the default sequence length to 100 because, when run, this prints:

   1 = 1
   2 = 1
   3 = 2
   4 = 3
   5 = 5
     :
     :
     :
  96 = 51680708854858323072
  97 = 83621143489848422977
  98 = 135301852344706746049
  99 = 218922995834555169026
 100 = 354224848179261915075

Name-Cache Fibonacci[100]   :    506.890 ms

Obviously, a lot faster than the naive version. And it turns out that most of the time is spent in the printing. Let’s try it without printing the list:

When run, this prints:

Name-Cache Fibonacci[100]   :      0.067 ms
Name-Cache Fibonacci[10000] :      9.398 ms

Only 67 nanoseconds to generate 100 Fibonacci numbers and less than 10 milliseconds to generate 10,000. Printing is slow, but the function is fast.

Wrapping the function in a data cache is a good general technique, but we can often do better if we look closely at the function. In this case, we’re generating an integer (an increasingly large one) for every number from 1 to some sequence length. This suggests a list as a cache, and why not let the list become the sequence?

Here’s an implementation:

While the recursive fib function (lines #9 to #12) is (nearly) the same as before, the sequence generator is different. Line #4 defines a list of zeros whose length is the requested sequence length. There is one slot in the list for each Fibonacci number we’ll generate, and the list will be in sequence order.

To eliminate the need for the recursive function to check for the first Fibonacci numbers, which can’t follow the (n-2)+(n-1) pattern, we initialize the list with the first three Fibonacci numbers (lines #5 to #7).

The sequence generation loop just needs to call fib for each n. It doesn’t need to catch the return value, because we’ll ultimately return the entire list (line #17).

The test rig is similar to previous ones:

When run, this prints:

   1 = 1
   2 = 1
   3 = 2
   4 = 3
   5 = 5
   :
   :
   :
  96 = 51680708854858323072
  97 = 83621143489848422977
  98 = 135301852344706746049
  99 = 218922995834555169026
 100 = 354224848179261915075

Index-Cache Fibonacci[100]  :    466.858 ms

A bit faster than the decorator cache function. We can repeat the no-listing test:

When run, this prints:

Index-Cache Fibonacci[100]  :      0.034 ms
Index-Cache Fibonacci[10000]:      6.176 ms

Using a list is clearly faster. And printing again accounts for most of the time.

Even with caching, functions have overhead that slows things down. If we move from recursion to iteration, we can skip the function call overhead. Here’s an iterative implementation of a Fibonacci sequence generator:

Which is similar to the list example above but uses a loop to generate the sequence. We no longer call a fib function, so there’s no function call overhead during the sequence generation. Note that we still use the (n-2)+(n-1) pattern — not surprising, it’s the mathematical definition of a Fibonacci sequence.

The sequence generator becomes much simpler without recursion. At root, despite its mathematical definition, the Fibonacci sequence is a natural progression, which is why it appears so often in nature (explored in more detail below).

Here’s the usual test rig for the iterative function:

When run, this prints:

   1 = 1
   2 = 1
   3 = 2
   4 = 3
   5 = 5
   :
   :
   :
  96 = 51680708854858323072
  97 = 83621143489848422977
  98 = 135301852344706746049
  99 = 218922995834555169026
 100 = 354224848179261915075

Iterative Fibonacci[100]    : 469.964 ms

The same numbers again, and the time isn’t any better, but remember the printing to the screen takes most of that time. Let’s turn off printing again:

This time we get:

Iterative Fibonacci[100]    :      0.010 ms
Iterative Fibonacci[10000]  :      4.432 ms

A noticeable improvement (as expected).

Recently I was challenged to explain how nature can use the Fibonacci sequence without knowing how to do math. I had some fun coming up with an algorithm that doesn’t use math. Here’s a “mechanical” version of a Fibonacci sequence generator that uses a mechanical process:

It’s vaguely similar to the iterative example but structured differently. It’s meant to imitate a process a person could do by hand. Literally by hand.

In plain English, the process is:

1. Start with an item in both hands (and empty pile).
2. Copy the contents of both hands to pile.
3. Move contents of left hand to end of sequence.
4. Move contents of right hand to left hand.
5. Move pile to right hand.
6. Repeat until sequence is long enough.

You can try it yourself if you have a jar of pennies or large-ish collection of other small items. Popcorn kernels, for instance. Remember to keep the piles you move from your left hand to the end of the sequence so you can see their size (which is their Fibonacci number).

We have the usual test rig to exercise the sequence generator:

Which prints essentially the same thing as the iterative and array-cache examples with the same general print-bound timing.

Now that we have all five sequence generators, let’s see how they compare:

When run, this prints.

Canonical Fibonacci[33]     :   1289.344 ms
Name-Cache Fibonacci[50000] :     78.114 ms
Index-Cache Fibonacci[50000]:     65.593 ms
Iterative Fibonacci[50000]  :     56.264 ms
Mechanical Fibonacci[50000] :     53.038 ms

All blazing fast compared to the naive recursive method, but iterative methods have a clear upper hand on recursive methods.

As for that 50,000th Fibonacci number:

When run, this prints:

Found 50000 Fibonacci numbers.
The last one has 10450 digits.
First 50 digits: 10777734893072974780279038855119480829625106769411
Last 50 digits:  70374907819690111266524020297618305364252373553125

You can print the full number, all 10,000+ digits of it, at your own risk.

But remember two valuable lessons: data caching (check out Python functools) and the difference between recursion and iteration. Recursion can be powerful, but it has its drawbacks, especially in a case like this with so many repeated calls for the same thing.

Link: Zip file containing all code fragments used in this post.

∅