Fibonacci Series in Python
The Fibonacci sequence is a well-known integer number series. The sequence appears in many problems naturally and has a great recursive definition. Learning how to produce it is an important step toward grasping recursion for the pragmatic programmer.
Examining the Recursion Behind the Fibonacci Sequence
The Fibonacci sequence generation is a classic recursive problem. Recursion occurs when a function refers to itself in order to deconstruct the problem it is attempting to solve. Each function call reduces the problem until it reaches a base case, at which point it returns the result to each intermediate caller until it provides the result to the original caller.
Generating the Fibonacci Sequence Recursively in Python
To generate the Fibonacci sequence, the most common and simplest algorithm requires you to write a recursive function that calls itself as many times as necessary until it computes the desired Fibonacci number.
The base case is checked first within Fibonacci of(). Then you return the sum of the values obtained by executing the function with the two preceding n values. At the end of the example, the list comprehension generates a Fibonacci sequence using the first fifteen numbers.
Optimizing the Recursive Algorithm for the Fibonacci Sequence
There are at least two ways you may employ to improve the efficiency of the algorithm used to construct the Fibonacci sequence—that is, to make it take less time to compute. These strategies ensure that you do not repeatedly compute the same numbers, which is what made the previous algorithm wasteful. They are known as memoization and iteration.
By storing previously calculated results in a cache, memoization speeds up the execution of expensive recursive procedures. When the same input is given again, the function only needs to seek up the appropriate result and return it, rather than running the computation twice. These outcomes can be referred to as cached or memoized:
This optimization could be translated into Python code as follows:
Exploring an Iterative Algorithm
An iterative algorithm can be used to compute the number at position n in the Fibonacci sequence.
In the diagram below, the bolded purple numbers represent the new numbers that must be calculated and added to cache in each iterative step:
To find the Fibonacci number at location n, save the first two integers in the series, 0 and 1, in cache. Then, calculate the following integers sequentially until you can return cache[n].
Generating the Fibonacci Sequence in Python
Using Recursion and a Python Class
Your first method for producing the Fibonacci sequence will involve the usage of a Python class and recursion. The class has an advantage over the previously seen memoized recursive function in that it retains state and behavior (encapsulation) together within the same object.
Using Iteration and a Python Function
The previous sections' examples implement a recursive solution that employs memoization as an optimization strategy. In this section, you will write an iterative function. The following code runs an iterative version of your Fibonacci sequence algorithm:
The Fibonacci sequence can help you better comprehend recursion. You have learned about the Fibonacci sequence in this course. You have also learned about some standard sequence generation techniques and how to transfer them into Python code.
The Fibonacci sequence can be a good springboard and entry point into the domain of recursion, which is a fundamental programming ability.
Subscribe to our Newsletter
Receive latest industry news and updates, exclusive offers directly in your inbox.