A Python Guide to the Fibonacci Sequence

Memoizing the Recursive Algorithm

As you saw in the code above, the Fibonacci function calls itself several times with the same input. Instead of a new call every time, you can store the results of previous calls in something like a memory cache. You can use a Python list to store the results of previous computations. This technique is called memoization.

Memoization speeds up the execution of expensive recursive functions by storing previously calculated results in a cache. This way, when the same input occurs again, the function just has to look up the corresponding result and return it without having to run the computation again. You can refer to these results as cached or memoized:

With memoization, you just have to traverse up the call tree of depth n once after returning from the base case, as you retrieve all the previously calculated values highlighted in yellow, F(2) and F(3), from the cache earlier.

The orange path shows that no input to the Fibonacci function is called more than once. This significantly reduces the time complexity of the algorithm from exponential O(2ⁿ) to linear O(n).

Even for the base cases, you can replace calling F(0) and F(1) with just retrieving the values directly from the cache at indices 0 and 1, so you end up calling the function just six times instead of fifteen!

Here’s a possible translation of this optimization into Python code:

>>> cache = {0: 0, 1: 1}

>>> def fibonacci_of(n):
...     if n in cache:  # Base case
...         return cache[n]
...     # Compute and cache the Fibonacci number
...     cache[n] = fibonacci_of(n - 1) + fibonacci_of(n - 2)  # Recursive case
...     return cache[n]

>>> [fibonacci_of(n) for n in range(15)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

In this example, you use a Python dictionary to cache the computed Fibonacci numbers. Initially, cache contains the starting values of the Fibonacci sequence, 0 and 1. Inside the function, you first check if the Fibonacci number for the current input value of n is already in cache. If so, then you return the number at hand.

If there is no Fibonacci number for the current value of n, then you compute it by calling fibonacci_of() recursively and updating cache. The final step is to return the requested Fibonacci number.

Exploring an Iterative Algorithm

What if you don’t even have to call the recursive Fibonacci function at all? You can actually use an iterative algorithm to compute the number at position n in the Fibonacci sequence.

You know that the first two numbers in the sequence are 0 and 1 and that each subsequent number in the sequence is the sum of its previous two predecessors. So, you can just create a loop that adds the previous two numbers, n - 1 and n - 2, together to find the number at position n in the sequence.

The bolded purple numbers in the diagram below represent the new numbers that need to be calculated and added to cache in each iterative step:

To calculate the Fibonacci number at position n, you store the first two numbers of the sequence, 0 and 1, in cache. Then, calculate the next numbers consecutively until you can return cache[n].

Using Recursion and a Python Class

Your first approach to generating the Fibonacci sequence will use a Python class and recursion. An advantage of using the class over the memoized recursive function you saw before is that a class keeps state and behavior (encapsulation) together within the same object. In the function example, however, cache is a completely separate object, so you don’t have control over it.

Below is the code that implements your class-based solution:

 1# fibonacci_class.py
 2
 3class Fibonacci:
 4    def __init__(self):
 5        self.cache = [0, 1]
 6
 7    def __call__(self, n):
 8        # Validate the value of n
 9        if not (isinstance(n, int) and n >= 0):
10            raise ValueError(f'Positive integer number expected, got "{n}"')
11
12        # Check for computed Fibonacci numbers
13        if n < len(self.cache):
14            return self.cache[n]
15        else:
16            # Compute and cache the requested Fibonacci number
17            fib_number = self(n - 1) + self(n - 2)
18            self.cache.append(fib_number)
19
20        return self.cache[n]

Here’s a breakdown of what’s happening in the code:

• Line 3 defines the Fibonacci class.

• Line 4 defines the class initializer, .__init__(). It’s a special method that you can use to initialize your class instances. Special methods are sometimes referred to as dunder methods, short for double underscore methods.

• Line 5 creates the .cache instance attribute, which means that whenever you create a Fibonacci object, there will be a cache for it. This attribute initially contains the first numbers in the Fibonacci sequence.

• Line 7 defines another special method, .__call__(). This method turns the instances of Fibonacci into callable objects.

• Lines 9 and 10 validate the value of n by using a conditional statement. If n is not a positive integer number, then the method raises a ValueError.

• Line 13 defines a conditional statement to check for those Fibonacci numbers that were already calculated and are available in .cache. If the number at index n is already in .cache, then line 14 returns it. Otherwise, line 17 computes the number, and line 18 appends it to .cache so you don’t have to compute it again.

• Line 20 returns the requested Fibonacci number.

To try this code, go ahead and save it into fibonacci_class.py. Then run this code in your interactive shell:

>>> from fibonacci_class import Fibonacci

>>> fibonacci_of = Fibonacci()

>>> fibonacci_of(5)
5
>>> fibonacci_of(6)
8
>>> fibonacci_of(7)
13

>>> [fibonacci_of(n) for n in range(15)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

Here, you create and then call an instance of the Fibonacci class named fibonacci_of. The first call uses 5 as an argument and returns 5, which is the sixth Fibonacci number because you’re using zero-based indices.

This implementation of the Fibonacci sequence algorithm is quite efficient. Once you have an instance of the class, the .cache attribute holds the already computed numbers from call to call.

Visualizing the Memoized Fibonacci Sequence Algorithm

You can effectively understand how each call to a recursive Fibonacci function is handled using a call stack representation. The way each call is pushed onto the stack and popped off reflects exactly how the program runs. It clearly demonstrates how calculating large numbers will take a long time if you don’t optimize the algorithm.

In a call stack, whenever a function returns a result, a stack frame representing the function call is popped off the stack. Whenever you call a function, you add a new stack frame to the top of the stack. In general, this operation has a space complexity of O(n) because there are no more than n stack frames on the call stack at a single time.

To visualize the memoized recursive Fibonacci algorithm, you’ll use a set of diagrams representing the call stack. The step number is indicated by the blue label below each call stack.

Say you want to compute F(5). To do this, you push the first call to the function onto the call stack:

To compute F(5), you must compute F(4) as outlined by the Fibonacci recurrence relation, so you add that new function call to the stack:

To compute F(4), you must compute F(3), so you add another function call to the stack:

To compute F(3), you must compute F(2), so you add yet another function call to the call stack:

To compute F(2), you must compute F(1), so you add that to the stack. As F(1) is a base case, it returns immediately with 1, and you remove this call from the stack:

Now you start to unwind the results recursively. F(1) returns the result back to its calling function, F(2). To compute F(2), you also need to compute F(0):

You add F(0) to the stack. Since F(0) is a base case, it returns immediately, giving you 0. Now you can remove it from the call stack:

This result of calling F(0) is returned to F(2). Now you have what you need to compute F(2) and remove it from the stack:

The result of F(2) is returned to its caller, F(3). F(3) also needs the results of F(1) to complete its calculation, so you add it back to the stack:

F(1) is a base case and its value is available in the cache, so you can return the result immediately and remove F(1) from the stack:

You can complete the calculation for F(3), which is 2:

You remove F(3) from the stack after completing its calculation and return the result to its caller, F(4). F(4) also needs the result of F(2) to compute its value:

You push the call to F(2) onto the stack. This is where the nifty cache comes in. You have calculated it before, so you can just retrieve the value from the cache, avoiding a recursive call to compute the result of F(2) again. The cache returns 1, and you remove F(2) from the stack:

F(2) is returned to its caller, and now F(4) has all it needs to compute its value, which is 3:

Next, you remove F(4) from the stack and return its result to the final and original caller, F(5):

F(5) now has the result of F(4) and also the result of F(3). You push an F(3) call onto the stack, and the nifty cache comes into play again. You previously calculated F(3), so all you need to do is retrieve it from the cache. There’s no recursive process to compute F(3). It returns 2, and you remove F(3) from the stack:

Now F(5) has all the values it needs to calculate its own value. You get 5 by adding 3 and 2, and that’s the final step before you pop the F(5) call off the stack. This action ends your sequence of recursive function calls:

The call stack is empty now. You’ve completed the final step to compute F(5):

Representing recursive function calls using a call stack diagram helps you understand all the work that takes place behind the scenes. It also allows you to see how many resources a recursive function can take up.

Putting all these diagrams together allows you to visualize how the whole process looks:

You can click the image above to zoom in on individual steps. If you don’t cache previously computed Fibonacci numbers, some of the stack stages in this diagram would be way taller, which means that they would take longer to return a result to their respective callers.

Using Iteration and a Python Function

The example in the previous sections implements a recursive solution that uses memoization as an optimization strategy. In this section, you’ll code a function that uses iteration. The code below implements an iterative version of your Fibonacci sequence algorithm:

 1# fibonacci_func.py
 2
 3def fibonacci_of(n):
 4    # Validate the value of n
 5    if not (isinstance(n, int) and n >= 0):
 6        raise ValueError(f'Positive integer number expected, got "{n}"')
 7
 8    # Handle the base cases
 9    if n in {0, 1}:
10        return n
11
12    previous, fib_number = 0, 1
13    for _ in range(2, n + 1):
14        # Compute the next Fibonacci number, remember the previous one
15        previous, fib_number = fib_number, previous + fib_number
16
17    return fib_number

Now, instead of using recursion in fibonacci_of(), you’re using iteration. This implementation of the Fibonacci sequence algorithm runs in O(n) linear time. Here’s a breakdown of the code:

• Line 3 defines fibonacci_of(), which takes a positive integer, n, as an argument.

• Lines 5 and 6 perform the usual validation of n.

• Lines 9 and 10 handle the base cases where n is either 0 or 1.

• Line 12 defines two local variables, previous and fib_number, and initializes them with the first two numbers in the Fibonacci sequence.

• Line 13 starts a for loop that iterates from 2 to n + 1. The loop uses an underscore (_) for the loop variable because it’s a throwaway variable and you won’t be using this value in the code.

• Line 15 computes the next Fibonacci number in the sequence and remembers the previous one.

• Line 17 returns the requested Fibonacci number.

To give this code a try, get back to your interactive session and run the following code:

>>> from fibonacci_func import fibonacci_of

>>> fibonacci_of(5)
5
>>> fibonacci_of(6)
8
>>> fibonacci_of(7)
13

>>> [fibonacci_of(n) for n in range(15)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

This implementation of fibonacci_of() is quite minimal. It uses iterable unpacking to compute the Fibonacci numbers during the loops, which is quite efficient memory-wise. However, every time you call the function with a different value of n, it has to recompute the sequence over again. To fix this, you can use closures and make your function remember the already computed values between calls. Go ahead and give it a try!