La successione di Fibonacci, ricorsiva ed iterativa Python

Sviluppiamo l’algoritmo della successione di Fibonacci in Python. Ricordiamone la definizione.

La successione di Fibonacci è una successione di numeri interi positivi, in cui ciascun numero, a cominciare dal terzo, è la somma dei due precedenti eccetto i primi due che sono 1, 1.

Ad esempio se N=9, i termini della successione sono: 1, 1, 2, 3, 5, 8, 13, 21, 34.

La successione di Fibonacci in Python

Realizziamo dunque un algoritmo dapprima iterativo.

Prendere in input un numero N e visualizzare gli N termini della successione di Fibonacci.

Per realizzare questo algoritmo innanzitutto prendiamo due variabili a e b e ad entrambe assegniamo il valore 1. Creiamo così i primi due termini della successione che andremo subito a stampare.

Quindi, utilizziamo un ciclo for per visualizzare gli N termini con un indice i che varia da 0 ad N-1. Dopo, all’interno del ciclo calcoliamo il terzo termine c e poi scambiamo a con b e b con c. Infine stampiamo c.

Ecco dunque una possibile soluzione:


n = int(input('Quanti numeri?: ' ))
a,b = 1,1
print(a)
print(b)

for i in range(N):
    c=a+b
    a=b
    b=c
    print(c, end=' ')

Una volta capito il procedimento, riscriviamo l’algoritmo sulla successione di Fibonacci in Python in maniera più elegante. Dunque evitiamo un pò di istruzioni, come ad esempio i print iniziali e realizziamo lo scambio delle variabili in un’unica riga.

Ecco dunque la soluzione:


n = int(input('Quanti numeri?: ' ))
    
a,b = 1,1

for i in range(n):
    print(a, end=' ')
    a,b = b,a+b
    print()

Potremmo anche definire una funzione da richiamare all’occorrenza.


def print_fibonacci(length):
    a = 1
    b = 1
    for i in range (length):
        print(a, end=" ")
        a,b=b,a+b
n = int(input('Quanti numeri?: ' ))
while(n < 0):
    n = int(input('Quanti numeri? Inserisci un numero positivo: ' ))
print_fibonacci(n)

Disponibile il libro su Python "50 Algoritmi per imparare Python"

Acquistalo adesso su Amazon

La successione di Fibonacci in Python – soluzione ricorsiva

Implementiamo anche una soluzione ricorsiva dell'algoritmo. Ricordiamo che si ha ricorsione quando all'inerno della propria definizione si richiama la funzione stessa. Nel nostro caso, infatti, chiamiamo la funzione rec_fib all'interno della stessa funzione 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))

Conclusione

In questa lezione abbiamo studiato una soluzione iterativa ed una ricorsiva all'algoritmo per la successione di Fibonacci in Python. Nelle prossime lezioni introdurremo il concetto di lista in Python.

Lezione precedente: come trovare le cifre di un numero in Python

Lezione successiva: controllare se un numero appartiene alla successione di Fibonacci