Select Page I 100 libri da non perdere

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))

``````

## Conclusion

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.

Python lambda function

Use Python dictionaries