The Fibonacci sequence is a series of numbers where each number is the sum of the two previous numbers. The first two numbers in the sequence are 0 and 1, and then each subsequent number is the sum of the two numbers before it. So, the first few numbers in the Fibonacci sequence are:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

If we notice, to get the Fibonacci number of n it’s the sum of Fibonacci number of n-1 and n-2

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

We will look at 3 different methods to implement.

Method 1: python while loop

def fibonacci_loop(n: int) -> int:
    # initialize 2 variables as 0, 1. 
    # which are intial values of a fibonacci series
    n1, n2 = 0, 1
    # now lets' loop through n-1 times
    while n > 1:
        # decrement the counter to stop the loop
        n -= 1
        # swap the value of n1 and n2 with n2 and n1+n2
        n1, n2 = n2, n1 + n2  
    # variable n2 has the final result
    return n2

Here we are using the while loop to iterate n-1 times. Also, we have 2 variables n1 and n2 to keep the values for each iteration. Now, let’s understand n1, n2 = n2, n1 + n2

As we discussed, Fibonacci series f(n) is f(n-1)+f(n-2) . Here n2 is our f(n). So for each iteration n2 keeps the sum of the previous iter. I am using multi-assignment to avoid creating temporary variables to keep the intermediate sum.

Following is a more generic algorithm using a temp variable to keep the temporary sum.

def fibonacci_loop(n: int) -> int:
    n1 = 0
    n2 = 1
    count = 1
    while count < n:
        tmp = n1 + n2
        n1 = n2
        n2 = tmp
        count += 1
    return n2

Now let’s look at how to implement it using recursion.

Method 2: recursion

Let’s try to implement the formula f(n) = f(n-1) + f(n-2) using recursion.

def fibonacci_recur(n: int) -> int:
    if n == 0:
        return 0
    if n <= 2:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

The results are the same by using either of the methods. Now the question is which method is better?

What’s better

Now that we implemented the program in 2 ways, let’s try to understand what’s better. To measure the performance of the code, I created the following function: (a very scientific way to test😉).

I am running the Fibonacci code starting from 1 to 39 to see how much time each function takes to evaluate. Following is the test code.

import time

def time_func():
    max_n = 40

    def run_func(func, n):
        start = time.perf_counter()
        result = func(i)
        print(f"{func.__name__.ljust(15)}-> n={str(n).ljust(2)} {result=}, "
              f"total time={time.perf_counter() - start:.8f} secs")
    for i in range(1, max_n):
        run_func(fibonacci_loop, i)
    for i in range(1, max_n):
        run_func(fibonacci_recur, i)

Let’s look at the results. First the loop method. The results are returned at a reasonable speed.

# using loop
fibonacci_loop -> n=1  result=1         total time=0.00000430 secs
fibonacci_loop -> n=2  result=1         total time=0.00000210 secs
fibonacci_loop -> n=3  result=2         total time=0.00000090 secs
fibonacci_loop -> n=4  result=3         total time=0.00000080 secs
fibonacci_loop -> n=5  result=5         total time=0.00000090 secs
fibonacci_loop -> n=6  result=8         total time=0.00000090 secs
fibonacci_loop -> n=7  result=13        total time=0.00000100 secs
fibonacci_loop -> n=8  result=21        total time=0.00000280 secs
fibonacci_loop -> n=9  result=34        total time=0.00000120 secs
fibonacci_loop -> n=10 result=55        total time=0.00000090 secs
fibonacci_loop -> n=11 result=89        total time=0.00000070 secs
fibonacci_loop -> n=12 result=144       total time=0.00000100 secs
fibonacci_loop -> n=13 result=233       total time=0.00000080 secs
fibonacci_loop -> n=14 result=377       total time=0.00000090 secs
fibonacci_loop -> n=15 result=610       total time=0.00000100 secs
fibonacci_loop -> n=16 result=987       total time=0.00000100 secs
fibonacci_loop -> n=17 result=1597      total time=0.00000100 secs
fibonacci_loop -> n=18 result=2584      total time=0.00000090 secs
fibonacci_loop -> n=19 result=4181      total time=0.00000110 secs
fibonacci_loop -> n=20 result=6765      total time=0.00000110 secs
fibonacci_loop -> n=21 result=10946     total time=0.00000110 secs
fibonacci_loop -> n=22 result=17711     total time=0.00000110 secs
fibonacci_loop -> n=23 result=28657     total time=0.00000110 secs
fibonacci_loop -> n=24 result=46368     total time=0.00000110 secs
fibonacci_loop -> n=25 result=75025     total time=0.00000110 secs
fibonacci_loop -> n=26 result=121393    total time=0.00000130 secs
fibonacci_loop -> n=27 result=196418    total time=0.00000120 secs
fibonacci_loop -> n=28 result=317811    total time=0.00000120 secs
fibonacci_loop -> n=29 result=514229    total time=0.00000120 secs
fibonacci_loop -> n=30 result=832040    total time=0.00000130 secs
fibonacci_loop -> n=31 result=1346269   total time=0.00000130 secs
fibonacci_loop -> n=32 result=2178309   total time=0.00000130 secs
fibonacci_loop -> n=33 result=3524578   total time=0.00000130 secs
fibonacci_loop -> n=34 result=5702887   total time=0.00000140 secs
fibonacci_loop -> n=35 result=9227465   total time=0.00000140 secs
fibonacci_loop -> n=36 result=14930352  total time=0.00000140 secs
fibonacci_loop -> n=37 result=24157817  total time=0.00000140 secs
fibonacci_loop -> n=38 result=39088169  total time=0.00000140 secs
fibonacci_loop -> n=39 result=63245986  total time=0.00000150 secs

Now let’s look at the recursion method performance.

fibonacci_recur-> n=1  result=1         total time=0.00000090 secs
fibonacci_recur-> n=2  result=1         total time=0.00000050 secs
fibonacci_recur-> n=3  result=2         total time=0.00000090 secs
fibonacci_recur-> n=4  result=3         total time=0.00000150 secs
fibonacci_recur-> n=5  result=5         total time=0.00000120 secs
fibonacci_recur-> n=6  result=8         total time=0.00000130 secs
fibonacci_recur-> n=7  result=13        total time=0.00000180 secs
fibonacci_recur-> n=8  result=21        total time=0.00000250 secs
fibonacci_recur-> n=9  result=34        total time=0.00000350 secs
fibonacci_recur-> n=10 result=55        total time=0.00000540 secs
fibonacci_recur-> n=11 result=89        total time=0.00000940 secs
fibonacci_recur-> n=12 result=144       total time=0.00001320 secs
fibonacci_recur-> n=13 result=233       total time=0.00002060 secs
fibonacci_recur-> n=14 result=377       total time=0.00003330 secs
fibonacci_recur-> n=15 result=610       total time=0.00005180 secs
fibonacci_recur-> n=16 result=987       total time=0.00008660 secs
fibonacci_recur-> n=17 result=1597      total time=0.00014050 secs
fibonacci_recur-> n=18 result=2584      total time=0.00022950 secs
fibonacci_recur-> n=19 result=4181      total time=0.00037390 secs
fibonacci_recur-> n=20 result=6765      total time=0.00063830 secs
fibonacci_recur-> n=21 result=10946     total time=0.00101400 secs
fibonacci_recur-> n=22 result=17711     total time=0.00141120 secs
fibonacci_recur-> n=23 result=28657     total time=0.00212920 secs
fibonacci_recur-> n=24 result=46368     total time=0.00352270 secs
fibonacci_recur-> n=25 result=75025     total time=0.00618250 secs
fibonacci_recur-> n=26 result=121393    total time=0.01017430 secs
fibonacci_recur-> n=27 result=196418    total time=0.01584420 secs
fibonacci_recur-> n=28 result=317811    total time=0.02798530 secs
fibonacci_recur-> n=29 result=514229    total time=0.04655380 secs
fibonacci_recur-> n=30 result=832040    total time=0.07358940 secs
fibonacci_recur-> n=31 result=1346269   total time=0.11667970 secs
fibonacci_recur-> n=32 result=2178309   total time=0.19072480 secs
fibonacci_recur-> n=33 result=3524578   total time=0.31605260 secs
fibonacci_recur-> n=34 result=5702887   total time=0.47243740 secs
fibonacci_recur-> n=35 result=9227465   total time=0.78889710 secs
fibonacci_recur-> n=36 result=14930352  total time=1.32147390 secs
fibonacci_recur-> n=37 result=24157817  total time=2.09678590 secs
fibonacci_recur-> n=38 result=39088169  total time=3.37948670 secs
fibonacci_recur-> n=39 result=63245986  total time=5.53867920 secs

The performance degraded exponentially with each iteration.

Why is the recursion slow?

Let’s look at the following image on how the Fibonacci number is calculated for n=5

First, the program tries to get the Fibonacci numbers of 4 and 3. But since f(4) and f(3) are not available f(4) will request for f(3) and f(2) and f(3) will request for f(2) and f(1). Our program returns a value only when it’s less than 2. Until 2 or 1 is part of the request, the recursion will go on. Hence if you take a larger number, there is a significant spike in total evaluation time.

So is recursion “bad”? Should we not write recursive functions?

Recursion can be considered bad in Python when there is a more optimal way to implement the same algorithm using iteration or the recursive use case has the potential to generate more than 1000 function calls on the call stack.

But I still want to use recursion for the Fibonacci series. Is there a way I can make this faster? What if F(n) value can be reused instead of evaluated for each f(n-1) and f(n-2) iteration.

That’s where a cache is going to help!

Let’s implement a program that will remember the last value and return it instead of creating another recursive call (in short a cache). We will take the help of a Python dictionary and create a decorator.

from functools import wraps

def dict_cache(func):
    a_dict = {}

    @wraps(func)
    def wrapper(n):
        if n in a_dict:
            return a_dict[n]
        r = func(n)
        a_dict[n] = r
        return r
    return wrapper

Here I have imported from functools import wraps to get the functions name while logging. The function has a dictionary where I store the values for n for the first time and from the next call onwards the code checks if n exists and returns it instead of making the function call.

Now let’s add the decorator to the recursive function and measure the timing.

@dict_cache
def fibonacci_recur(n: int) -> int:
    if n == 0:
        return 0
    if n <= 2:
        return 1
    return fibonacci_recur(n - 1) + fibonacci_recur(n - 2)

fibonacci_recur-> n=1  result=1         total time=0.00000160 secs
fibonacci_recur-> n=2  result=1         total time=0.00000080 secs
fibonacci_recur-> n=3  result=2         total time=0.00000140 secs
fibonacci_recur-> n=4  result=3         total time=0.00000160 secs
fibonacci_recur-> n=5  result=5         total time=0.00000120 secs
fibonacci_recur-> n=6  result=8         total time=0.00000110 secs
fibonacci_recur-> n=7  result=13        total time=0.00000090 secs
fibonacci_recur-> n=8  result=21        total time=0.00000160 secs
fibonacci_recur-> n=9  result=34        total time=0.00000090 secs
fibonacci_recur-> n=10 result=55        total time=0.00000080 secs
fibonacci_recur-> n=11 result=89        total time=0.00000330 secs
fibonacci_recur-> n=12 result=144       total time=0.00000080 secs
fibonacci_recur-> n=13 result=233       total time=0.00000070 secs
fibonacci_recur-> n=14 result=377       total time=0.00000070 secs
fibonacci_recur-> n=15 result=610       total time=0.00000060 secs
fibonacci_recur-> n=16 result=987       total time=0.00000070 secs
fibonacci_recur-> n=17 result=1597      total time=0.00000080 secs
fibonacci_recur-> n=18 result=2584      total time=0.00000070 secs
fibonacci_recur-> n=19 result=4181      total time=0.00000080 secs
fibonacci_recur-> n=20 result=6765      total time=0.00000070 secs
fibonacci_recur-> n=21 result=10946     total time=0.00000080 secs
fibonacci_recur-> n=22 result=17711     total time=0.00000140 secs
fibonacci_recur-> n=23 result=28657     total time=0.00000430 secs
fibonacci_recur-> n=24 result=46368     total time=0.00000110 secs
fibonacci_recur-> n=25 result=75025     total time=0.00000080 secs
fibonacci_recur-> n=26 result=121393    total time=0.00000120 secs
fibonacci_recur-> n=27 result=196418    total time=0.00000080 secs
fibonacci_recur-> n=28 result=317811    total time=0.00000070 secs
fibonacci_recur-> n=29 result=514229    total time=0.00000080 secs
fibonacci_recur-> n=30 result=832040    total time=0.00000070 secs
fibonacci_recur-> n=31 result=1346269   total time=0.00000070 secs
fibonacci_recur-> n=32 result=2178309   total time=0.00000070 secs
fibonacci_recur-> n=33 result=3524578   total time=0.00000070 secs
fibonacci_recur-> n=34 result=5702887   total time=0.00000070 secs
fibonacci_recur-> n=35 result=9227465   total time=0.00000080 secs
fibonacci_recur-> n=36 result=14930352  total time=0.00000080 secs
fibonacci_recur-> n=37 result=24157817  total time=0.00000080 secs
fibonacci_recur-> n=38 result=39088169  total time=0.00000080 secs
fibonacci_recur-> n=39 result=63245986  total time=0.00000080 secs

Now, that’s a significant improvement.

Is there any other way?

Yes, there is. Python’s functools library provides lru_cacheand cache methods that can be used to cache results.

lru_cache and cache are the same, except lru_cache allows you to define the maximum size for caching. Use them as per your project needs.

Learn about the LRU cache below:

LRU Cache

Let’s use it in our Python code. (I have created a separate function fibonacci_lru so that we can measure the performance later, the algo is the same as fibonacci_recur

from functools import lru_cache

@lru_cache()
def fibonacci_lru(n: int) -> int:
    if n == 0:
        return 0
    if n <= 2:
        return 1
    return fibonacci_lru(n-1)+fibonacci_lru(n-2)

Now let’s measure which one is better. I am using timeit and running the code 100,000 times to get the Fibonacci number for 100 and taking the average time.

import timeit

def time_it():
    num = 100_000
    total = timeit.timeit("fibonacci_lru(100)", globals=globals(), number=num)
    print(f"fibonacci_lru  -> {total=:.8f} average={total/num:.8f} secs")
    total = timeit.timeit("fibonacci_loop(100)", globals=globals(), number=num)
    print(f"fibonacci_loop -> {total=:.8f} average={total/num:.8f} secs")
    total = timeit.timeit("fibonacci_recur(100)", globals=globals(), number=num)
    print(f"fibonacci_recur-> {total=:.8f} average={total/num:.8f} secs")

All 3 methods are faster. Although both the caching methods seem to be faster than the loop. Here are the results:

fibonacci_lru -> total=0.00517680 average=0.00000005 secs
fibonacci_loop -> total=0.39864330 average=0.00000399 secs
fibonacci_recur-> total=0.00676110 average=0.00000007 secs

I would go with the lru_cache method as it's simple and less code.

Thank you for reading through the article. This is the first article that I have written ever and published. Please do share any feedback or improvements needed. 😊