Fibonacci sequence in Python can have different implementation algorithms.
Recall that the Fibonacci sequence is a sequence of positive integers in which each number starting from the third is the sum of the previous two except the first two which are 1, 1.
For example, if N = 9, the terms of the sequence are: 1, 1, 2, 3, 5, 8, 13, 21, 34.
Fibonacci sequence in Python algorithm
So let’s create an algorithm that represents the Fibonacci sequence.
Take a number N as input and display the N terms of the Fibonacci sequence.
To implement this algorithm, first of all we take two variables a and b and assign the value 1 to both. We thus create the first two terms of the Fibonacci sequence that we will immediately print.
Then, we make a for loop to display the N terms with an index i ranging from 0 to N-1. After, within the cycle we calculate the third term c and then exchange a with b and b with c. Finally we print c.
Here is a possible solution:
n = int(input('How many numbers?: ' )) a,b = 1,1 print(a) print(b) for i in range(n): c = a+b a = b b = c print(c, end=' ')
Once we understand the procedure, we rewrite the algorithm in a more elegant way, avoiding some instructions, such as the initial prints, and we carry out the exchange in a single line.
Here is the solution:
n = int(input('How many numbers?: ' )) a,b = 1,1 for i in range(n): print(a, end=' ') a,b = b,a+b print()
Fibonacci sequence in Python algorithm – with a function
We can also use a function to solve the algorithm.
def print_fibonacci(length): a = 1 b = 1 for i in range (length): print(a, end=" ") a,b=b,a+b n = int(input('How many numbers?: ' )) print_fibonacci(n)
We can also add a control input. If a user insert a negative number the program can be request a new number.
def print_fibonacci(length): a = 1 b = 1 for i in range (length): print(a, end=" ") a,b=b,a+b n = int(input('How many numbers?: ' )) while(n < 0): n = int(input('How many numbers? Insert a positive number: ' )) print_fibonacci(n)
Fibonacci sequence in Python algorithm – recursive solution
Here is the recursive solution to the algorithm. Remember that recursion is when you have a call directly to the function itself. In our case, in fact, we call the function rec_fib within the same function rec_fib.
def rec_fib(n): if n > 1: return rec_fib(n-1) + rec_fib(n-2) return n n = int(input('How many numbers?: ' )) for i in range(1,n+1): print(rec_fib(i))
In this lesson we studied how to develop a Fibonacci sequence algorithm in Python, in the next lesson we will see how to understand if a number is part of the sequence.