The Fibonacci Sequence is one of the most famous sequences in mathematics. It’s quite simple to calculate: each number in the sequence is the sum of the previous two numbers.
This sequence has found its way into programming. Often, it is used to train developers on algorithms and loops.
In this guide, we’re going to talk about how to code the Fibonacci Sequence in Python. We’ll look at two approaches you can use to implement the Fibonacci Sequence: iterative and recursive.
What is the Fibonacci Sequence?
The Fibonacci Sequence is a series of numbers. Each number is the product of the previous two numbers in the sequence. The sequence starts like this:
0, 1, 1, 2, 3, 4, 8, 13, 21, 34
It keeps going forever until you stop calculating new numbers. The rule for calculating the next number in the sequence is:
x(n) = x(n-1) + x(n-2)
x(n) is the next number in the sequence. x(n-1) is the previous term. x(n-2) is the term before the last one.
Python Fibonacci Sequence: Iterative Approach
Let’s start by talking about the iterative approach to implementing the Fibonacci series.
This approach uses a “while” loop which calculates the next number in the list until a particular condition is met. Each time the while loop runs, our code iterates. This is why the approach is called iterative.
Let’s begin by setting a few initial values:
terms_to_calculate = 9 n1, n2 = 0, 1 counted = 0
We have declared four variables.
The first variable tracks how many values we want to calculate. The next two variables, n1 and n2, are the first two items in the list. We need to state these values otherwise our program would not know where to begin. These values will change as we start calculating new numbers.
The last variable tracks the number of terms we have calculated in our Python program.
Let’s write a loop which calculates a Fibonacci number:
while counted < terms_to_calculate: print(n1) new_number = n1 + n2 n1 = n2 n2 = new_number counted += 1
This while loop runs until the number of values we have calculated is equal to the total numbers we want to calculate. The loop prints out the value of n1 to the shell. It then calculates the next number by adding the previous number in the sequence to the number before it.
We swap the value of n1 to be equal to n2. This makes n1 the first number back after the new number. We then set n2 to be equal to the new number. Next, we use the += operator to add 1 to our counted variable.
Our code returns:
Our program has successfully calculated the first nine values in the Fibonacci Sequence!
Python Fibonacci Sequence: Recursive Approach
Calculating the Fibonacci Sequence is a perfect use case for recursion. A recursive function is a function that depends on itself to solve a problem.
Recursive functions break down a problem into smaller problems and use themselves to solve it. Let’s start by initializing a variable that tracks how many numbers we want to calculate:
terms_to_calculate = 9
This program only needs to initialize one variable. Next, we can create a function that calculates the next number in the sequence:
def calculate_number(number): if number <= 1: return number else: return(calculate_number(number-1) + calculate_number(number-2))
This function checks whether the number passed into it is equal to or less than 1. If it is, that number is returned without any calculations. Otherwise, we call the calculate_number() function twice to calculate the sum of the preceding two items in the list.
Finally, we need to write a main program that executes our function:
for number in range(terms_to_calculate): print(calculate_number(number))
This loop will execute a number of times equal to the value of terms_to_calculate. In other words, our loop will execute 9 times. This loop calls the
calculate_number() method to calculate the next number in the sequence. It prints this number to the console.
Our code returns:
The output from this code is the same as our earlier example.
The difference is in the approach we have used. We have defined a recursive function which calls itself to calculate the next number in the sequence. The recursive approach is usually preferred over the iterative approach because it is easier to understand.
This code uses substantially fewer lines than our iterative example. What’s more, we only have to initialize one variable for this program to work; our iterative example required us to initialize four variables.
The Fibonacci Sequence can be generated using either an iterative or recursive approach.
The iterative approach depends on a while loop to calculate the next numbers in the sequence. The recursive approach involves defining a function which calls itself to calculate the next number in the sequence.
Now you’re ready to calculate the Fibonacci Sequence in Python like an expert!