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:
Read the full article at https://realpython.com/fibonacci-sequence-python/ »
[ Improve Your Python With 🐍 Python Tricks 💌 – Get a short & sweet Python Trick delivered to your inbox every couple of days. >> Click here to learn more and see examples ]
from Planet Python
via read more
No comments:
Post a Comment