On calculating the Fibonacci sequence

Revisiting a popular first experience with programming

Recursion 101

The Fibonacci sequence is defined by a recurrence relation which maps directly to the concept of recursion in programming. Here is a Python function that calculates the sequence recursively.

def fib(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib(n-1) + fib(n-2)

This is a great example of recursion. Very readable (thank you Python!)

Recursion depth

When evaluating fib(n), the program first recursively evaluates fib(n-1) and fib(n-2), before adding their results. Each recursive level occupies space in the call stack in memory. Going too deep exhausts the call stack.

For Python, exhausting the call stack crashes the Python interpreter itself (not just your function!). Therefore, Python limits recursive depth to 1000 by default.

On my laptop, (MacOS CPython 3.11), fib(1_000) hits Python this default limit:

RecursionError: maximum recursion depth exceeded

Also kind of slow…

fib(38) takes 4.5 seconds on my fancy pants 2023 MacBook Pro.

Why might that be? Probably something to do with exponential number of recalculations during recursion!

Starting from evaluation of fib(38), consider how fib(0) ultimately gets invoked through recursion

fib(38)

fib(37) + fib(36)

[fib(36) + fib(35)] + [fib(35) + fib(34)]

[{fib(35) + fib(34)} + {fib(34) + fib(33)}] + [{fib(34) + fib(33)} + {fib(33) + fib(32)}]

...

You get the picture! No proofs here but probably fib(0) gets called O(2^n) times.

Let’s avoid recalculating then!

Remember all calculated results in the dictionary named cache.

cache = {}

def fib(n):
    if n in cache:
        return cache[n]
    if n == 0:
        result = 0 
    elif n == 1:
        result = 1
    else:
        result = fib(n-1) + fib(n-2)
    cache[n] = result
    return result

Now fib(38) computes in only 0.075 seconds. Is this the best we can do?

Do it iteratively?

Any recursive algorithm may be rewritten as an iterative algorithm. So let’s try it.

def fib(n):
    if n == 0:
        return 0
    f_prev, f_curr = 0, 1
    for _ in range(n-1):
        f_prev, f_curr = f_curr, f_prev + f_curr
    return f_curr

No recursive calls means we only use exactly one level in the call stack. There are no recalculations of any intermediate values by design - no need for any additional caching logic. Some results:

fib(1_000) takes 0.075 seconds.
fib(100_000) takes 0.193 seconds.
fib(1_000_000) takes 11.044* seconds (208988 digits).

* Costs go super-linear, because working with huge numbers requires more CPU and memory!

Let’s go even faster!

This is a highly numerical problem, where the main effort is just calculating sums. Everyone says C++ is faster than Python, so let’s try it.

Python int supports arbitrary size by default, and working with big numbers was a breeze. For C++ we use the GMP library.

#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <gmp.h>


void fib(long n, mpz_t* answer)
{
    if (n == 0) {
        mpz_set_ui(*answer, 0);
        return;
    }

    // Set fib(0) to 0
    mpz_t f_prev;
    mpz_init (f_prev);
    mpz_set_ui(f_prev, 0);

    // Set fib(1) to 1
    mpz_t f;
    mpz_init(f);
    mpz_set_ui(f, 1);

    // Prepare a temporary variable for storing sums
    mpz_t f_sum;
    mpz_init(f_sum);
    for (long i = 0; i < n - 1; ++i) {
        mpz_add(f_sum, f_prev, f);
        mpz_set(f_prev, f);
        mpz_set(f, f_sum);
    }
    mpz_set(*answer, f);
}

int main(int argc, char *argv[])
{
    if (argc < 2) {
        std::cerr << "Usage: " << argv[0] << " <arg1>\n";
        return EXIT_FAILURE;
    }

    // parse arg as an int
    long n = std::atol(argv[1]);
    mpz_t answer;
    mpz_init(answer);
    fib(n, &answer);

    // print result in base 10
    std::cout << mpz_get_str(NULL, 10, answer) << std::endl;
}

That was a mouthful! Quite a bit less readable than Python. However this C++ implementation takes 3 seconds to calculate fib(1_000_000).

Personal takeaways

• You can’t really go wrong with leaning toward iterative implementations.

• Programming language choice matters, sometimes.

• Python is really easy on the eyes (and brain)!