The Fibonacci sequence is a prime example of recursion, and learning it is an essential step in the pragmatic programmer’s journey toward mastering recursion. Even though you’ll focus on learning it using Python in this tutorial, you can apply these concepts universally to any programming language.
As you perform an in-depth analysis on this famous recursive sequence, it will help you to better grasp and internalize the main concepts of recursion. You’ll even go a step further by learning how to optimize the Fibonacci sequence in Python, and recursive algorithms in general, by making them more time efficient.
In this tutorial, you’ll learn:
- What the Fibonacci sequence is
- What recursion is
- How to optimize the Fibonacci sequence using a callable class
- How to optimize the Fibonacci sequence iteratively
- How to visualize recursion using a call stack
To get the most out of this tutorial, you should know the basics of Big O notation, object-oriented programming, Python’s built-in methods, control flow statements, function calls, and basic data structures like lists, queues, and stacks. Having even some familiarity with these concepts will greatly help you understand the new ones you’ll be exploring in this tutorial.
Let’s dive right in!
Free Download: Get a sample chapter from Python Basics: A Practical Introduction to Python 3 to see how you can go from beginner to intermediate in Python with a complete curriculum, up-to-date for Python 3.8.
What Is the Fibonacci Sequence?
Leonardo Fibonacci was an Italian mathematician who was able to quickly produce an answer to this question asked by Emperor Frederick II of Swabia: “How many pairs of rabbits are obtained in a year, excluding cases of death, supposing that each couple gives birth to another couple every month and that the youngest couples are able to reproduce already at the second month of life?”
The answer was the following sequence:
The pattern begins after the first two numbers, 0 and 1, where each number in the sequence is always the sum of the two numbers before it. Indian mathematicians had known about this sequence since the sixth century, and Fibonacci leveraged it to calculate the growth of rabbit populations.
F(n) is used to indicate the number of pairs of rabbits present in month n, so the sequence can be expressed like this:
In mathematical terminology, you’d call this a recurrence relation.
There is also a version of the sequence where the first two numbers are both 1, like so:
In this case, F(0) is still implicitly 0, but you start from F(1) and F(2) instead. The algorithm remains the same because you are always summing the previous two numbers to get the next number in the sequence.
For the purposes of this tutorial, you’ll use the sequence that starts with 0.
Exploring Recursion
The Fibonacci sequence is a quintessential recursive problem. Recursion is when a function calls itself in order to break down the problem it’s trying to solve. In every function call, the problem becomes smaller until it reaches a base case, after which it will then return the result to each caller until it returns the final result back to the original caller.
If you wanted to calculate the fifth Fibonacci number, F(5), you would have to calculate its predecessors, F(4) and F(3), first. And in order to calculate F(4) and F(3), you would need to calculate their predecessors. The breakdown of F(5) into smaller subproblems would look like this:
Each time the Fibonacci function is called, it gets broken down into two smaller subproblems because that is how you defined the recurrence relation. When it reaches the base case of either F(0) or F(1), it can finally return a result back to its caller.
In order to calculate the fifth number in the Fibonacci sequence, you solve smaller but identical problems until you reach the base cases, where you can start returning a result:
Note above where you see some identical subproblems highlighted by the same colors. You have to calculate many numbers in the Fibonacci sequence repeatedly in the recursion.
Examining the Recursive Fibonacci Sequence
The most common and basic implementation of the Fibonacci sequence is shown below, where you invoke fibonacci_sequence() as many times as it is needed until the nth number is calculated:
def fibonacci_sequence(n):
if n == 0 or n == 1:
return n
else:
return fibonacci_sequence(n-1) + fibonacci_sequence(n-2)
As a result, the computation is extremely expensive, being exponential time, because you are calculating many identical subproblems over and over again.
When calculating F(5), you have to make fifteen calls to the Fibonacci function in total. In order to calculate F(n), the maximum depth of the call tree is n, and since each function call produces two additional function calls, the time complexity of this recursive function is O(2n).
Most of those calls are redundant because you’ve already calculated their results. F(3) appears twice, and F(2) appears three times. F(1) and F(0) are base cases, so it’s fine to call them multiple times, but if you want to avoid calling them with the recursive function, then that is possible too. You’ll learn how to eliminate these replicated calls in the subsequent sections.
Two Ways to Optimize the Fibonacci Sequence
There are two techniques you can use to make the Fibonacci sequence more efficient, or, in other words, take less time to compute. These techniques ensure that you do not keep computing the same values over and over again, which is what made the original algorithm so inefficient. They are called memoization and iteration.
Using Memoization
As you saw in the code above, you call the Fibonacci function on itself several times with the same input. Instead of a new call with the Fibonacci function every time, you can store the result of a previous call in something like a memory cache. You can use the list data structure in Python to store the results of previous calculations. This technique is called memoization.
Memoization speeds up the calculation of expensive recursive function calls by storing previously calculated results in a cache, so when the same inputs occur again, the function can look up the result of that input and return it. You can refer to these results as cached or memoized:
With memoization, you just have to traverse up the call tree of depth n just once after returning the from base case, as you retrieve all the previously calculated values highlighted in yellow, F(2) and F(3), from the cache already.
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(2n) 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!
This is possible because you use the indices of 0 and 1 as keys to access the elements at cache[0] and cache[1]. Those cache elements will have the starting values of the Fibonacci sequence, 0 and 1, stored in them respectively.
Using Iteration
What if you didn’t even have to call the recursive Fibonacci function at all? You can actually use an iterative algorithm to compute the nth number in the Fibonacci sequence.
You know that the first two numbers in the sequence are 0 and 1, and each subsequent number in the sequence is the sum of its previous two predecessors. So, you can actually just iteratively add the previous two numbers, n - 1 and n - 2, together to find the nth number in the sequence.
The bolded purple numbers represent the new number that was calculated and added to the cache in each iterative step:
You store the first two numbers of the sequence, 0 and 1, in a cache, then append the calculated results to this ever-growing cache, and call cache[n] when you want to calculate the Fibonacci number at position n.
The Fibonacci Sequence in Python: Using a Callable Class
It’s time to see how both of these optimized versions of the Fibonacci sequence are represented in Python. This code demonstrates the Fibonacci sequence as a callable class:
1class FibonacciSequence():
2 def __init__(self):
3 self.cache = []
4 self.cache.append(0)
5 self.cache.append(1)
6
7 def __call__(self, i):
8 newfibnum = 0
9
10 # Check input is valid
11 if isinstance(i, int) and i >= 0:
12 # If i is base case of 0 or 1
13 if i == 0 or i == 1:
14 return self.cache[i]
15
16 # If i is NOT stored in the cache already
17 elif i >= len(self.cache):
18 newfibnum = self.__call__(i-1) + self.__call__(i-2)
19 self.cache.append(newfibnum)
20
21 # Previous two values in cache calculates i
22 else:
23 newfibnum = self.cache[i-1]+self.cache[i-2]
24
25 # Return the result of the fib sequence entered by the user
26 return self.cache[i]
27
28 # If input is not valid give error message
29 else:
30 raise ValueError("Invalid input, please enter a positive integer for i")
31
32# Instantiate the FibonacciSequence class
33new_seq = FibonacciSequence()
Here’s a breakdown of what’s happening with the code:
-
Line 2 initiates the
FibonacciSequenceobject using.__init__(). The cache is part of the.__init__()constructor, which means whenever you create aFibonacciSequenceobject, there will be a cache. The.__init__()constructor is a built-in function that you can use to enrich your classes. It is sometimes referred to as a dunder method, which is short for double underscore method. -
Line 3 contains the next built-in function,
.__self__(). It refers to the current instance of theFibonacciSequenceclass. This enables you to access the cache to store and retrieve values. -
Line 7 has another built-in function,
.__call__(), to make yourFibonacciSequenceclass callable. What does it mean for a class to be callable? It simply allows a class to be called like a method:>>>>>> new_seq(5) 5You create and then invoke an instance of the
FibonacciSequenceclass namednew_seq, passing it the parameter5. Thennew_seqwill return a value, in this case the fifth number of the Fibonacci sequence.
The Fibonacci Sequence in Python: Using a Non-Recursive Function
This code implements the iterative version of the Fibonacci sequence described above:
1def FibonacciSequence(i):
2 # Check whether input is valid
3 if isinstance(i, int) and i >=0:
4 # Initialize the cache with 0, 1
5 cache = []
6 fib_number = 0
7 cache.append(0)
8 cache.append(1)
9 cache_size = len(cache)
10
11 for _ in range(cache_size, i+1):
12 # You're always summing the previous two numbers
13 fib_number = sum(cache[-2:])
14 cache.append(fib_number)
15
16 # Return ith number in fibonacci sequence
17 return cache[i]
18
19 # If input is not valid raise exception
20 else:
21 raise ValueError("Invalid input, please enter a positive integer")
You are not using any type of recursion with FibonacciSequence, and it runs in O(n) linear time. Here’s a breakdown:
-
Line 11 iterates through a
forloop that sums up all the previous two numbers until you have reached the end of the cache, after which you can return the number in the Fibonacci sequence at the indexi. You use an underscore (_) for the loop variable because you won’t be using this value later on in the code, so it’s a throwaway variable. -
Line 13 uses the list notation
[-2:]to denote that you are summing the last two numbers in the cache. You then always append this new number you’ve calculated to the end of the cache in line 14. -
Line 21 raises a
ValueErrorif the input to the function is not valid.
Visualization of a Memoized Fibonacci Sequence
With stacks, you’ll effectively see how each call in a recursive function is handled. The way each call is pushed onto the stack and popped off is exactly how the program is run, and it’ll clearly demonstrate how calculating large numbers will take a long time, if not optimized.
Illustrating Visualization Using a Call Stack
In a call stack, whenever a function call 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.
Walking Through the Call Stack
The steps are outlined by the blue labels below each call stack. You will see what is happening step by step, helping you understand the underlying principles of recursion.
You want to compute F(5). To do this, you allocate a block of memory on the stack frame to store all the calculations of the call stack at a single time:
Note that this is referred to as space complexity, and it is O(n) because there are no more than n stack elements on the frame at a single time.
In order to compute F(5), you must compute F(4) as outlined by the Fibonacci algorithm, so you add that to the stack:
In order to compute F(4), you must compute F(3), so you add that to the stack:
In order to compute F(3), you must compute F(2), so you add that to the stack:
In order to compute F(2), you must compute F(1), which is F(n - 1), so you add that to the stack. As F(1) is a base case, it can return a result immediately, giving you 1, and you remove it from the stack:
Now you start to unwind the results recursively. F(1) returns the result back to its calling function, F(2). In order to compute F(2) you also need to compute F(0), which is F(n - 2):
You add F(0) to the stack. As F(0) is a base case, it can return a result immediately, giving you 0, and you remove it from the stack:
This result is returned to F(2), and now you have both F(n - 1) and F(n - 2) to compute F(2). You compute F(2) as 1 and remove it from the stack:
The result of F(2) is returned to its caller F(3). F(3) also needs the result of F(n - 2), F(1), to complete its calculation:
After adding the call of F(1) onto the stack, as it is a base case and also in the cache, 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(n - 2), F(2), to complete its calculation:
You add the call of F(2) to 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 by calling cache[2], avoiding having to recursively compute the result for F(2) again. It returns 1, and you remove F(2) from the stack:
F(2) is returned to its caller, and now F(4) has all the results it needs to complete its calculation, which is 3:
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 from F(4) and also needs the result from F(n - 2), which is equivalent to F(3).
You add the function call of F(3) to 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 by calling cache[3], and you get the result. There is no recursive process to compute F(3). It returns 2, and you remove F(3) from the stack:
Now F(5) has all the prerequisites it needs to calculate the result. Adding 3 and 2, you get 5, and that is the final step before you pop F(5) off the stack, ending your function call:
The stack is empty now that it has completed calculating F(5):
Representing recursive function calls as stacks enables you to have a more concrete understanding of all the work that takes place behind the scenes. It also allows you to see how many resources a recursive function call takes up when they are displayed as individual blocks.
Putting all these images together, this is what the recursive Fibonacci sequence in a stack looks like as a complete visualization:
You can click the image above to zoom in on individual stacks. From the image, you can see how much computational time the cache saves. If you did not store previously calculated results, some of the stacks would need to be taller, and it would take longer to return the results to their respective callers.
Conclusion
You have now methodically analyzed the Fibonacci sequence in Python and gained a deeper understanding of how this recursive sequence works. You also learned that there are ways to optimize it with clean, Pythonic code, which will be handy when you study more complicated recursive algorithms. The Fibonacci sequence provides you an excellent springboard and entry point into the world of recursion.
In this tutorial, you learned:
- What the Fibonacci sequence is
- What recursion is
- How to optimize the Fibonacci sequence using a callable class
- How to optimize the Fibonacci sequence iteratively
- How to visualize recursion using a call stack
Once you master the concepts covered in this tutorial, your Python programming skills will improve along with your recursive algorithmic thinking.
