Sequenza di Fibonacci in Python: impara ed esplora le tecniche di programmazione

La sequenza di Fibonacci è un modo divertente per continuare a esercitarti con Python. In questo articolo imparerai a implementare la sequenza di Fibonacci in Python usando diverse tecniche, dalla scrittura di funzioni efficienti e la gestione della ricorsione all’uso di principi orientati agli oggetti per soluzioni più ottimizzate. 

Quando hai finito, prova il nostro corso Writing Functions in Python per rafforzare concetti come lo scope e la gestione degli errori, oppure il corso Intermediate Object-Oriented Programming in Python per imparare ereditarietà e classi base. Ora mettiamoci alla prova con la sequenza di Fibonacci.

Risposta rapida

La sequenza di Fibonacci inizia con 0 e 1, e ogni numero è la somma dei due precedenti. Il modo più semplice per generarla in Python è con un ciclo:

n = 10
a, b = 0, 1

fibonacci_numbers = []

for _ in range(n):  
    fibonacci_numbers.append(str(a)) 
    a, b = b, a + b

print(' '.join(fibonacci_numbers))

# Questo stampa i primi 10 numeri di Fibonacci
# 0 1 1 2 3 5 8 13 21 34Offerto da

Che cos’è la sequenza di Fibonacci?

La sequenza di Fibonacci è un concetto matematico che appare in molte aree della scienza e della natura. È una serie di numeri in cui ciascun numero è la somma dei due precedenti, a partire da 0 e 1. Questo schema è alla base di applicazioni in campi come l’informatica e la finanza. 

Due aspetti principali definiscono la sequenza di Fibonacci: la struttura ricorsiva della sequenza e la sua relazione con la sezione aurea.

Natura ricorsiva della sequenza di Fibonacci

La sequenza di Fibonacci inizia con 0 e 1. Ogni nuovo numero è la somma dei due numeri che lo precedono. Per esempio:

0 + 1 = 1

1 + 1 = 2

1 + 2 = 3

2 + 3 = 5

3 + 5 = 8

5 + 8 = 13

E così via. 

Matematicamente si scrive come F(n) = F(n-1) + F(n-2). La sequenza si costruisce aggiungendo ripetutamente gli ultimi due numeri. I primi due numeri, 0 e 1, sono il punto di partenza o casi base. Senza di essi, la sequenza non funzionerebbe.

Questo schema ricorsivo è alla base di alcuni algoritmi in informatica. Per esempio, la ricorsione in programmazione lavora su questa sequenza per risolvere problemi come generare numeri di Fibonacci o suddividere attività in parti più piccole e gestibili.

Connessione con la sezione aurea 

La sequenza di Fibonacci è strettamente legata alla sezione aurea, un numero irrazionale rappresentato da φ (il cui valore è circa 1,618). Se dividi un numero di Fibonacci per quello precedente, il rapporto si avvicina sempre di più a φ. Per esempio:

5 ÷ 3 ≈ 1,666

8 ÷ 5 ≈ 1,6

13 ÷ 8 ≈ 1,625

Più vai avanti, più ti avvicini a 1,618. Non è un caso — questo rapporto emerge naturalmente nella sequenza di Fibonacci per via di come crescono i numeri.

Euclide lo descrisse per primo nell’antica Grecia come rapporto estremo e medio. Da allora è stato collegato a pattern in natura, come le spirali nelle conchiglie e nei fiori, così come nell’arte e nell’architettura.

Sezione aurea nell’arte. Fonte

Applicazioni pratiche della sequenza di Fibonacci

La sequenza di Fibonacci compare in modi sorprendenti in molti campi. Concentratiamo l’attenzione su due delle sue applicazioni più note: i suoi pattern in natura e il suo uso in informatica.

Fibonacci in natura

Puoi vedere la sequenza di Fibonacci ovunque in natura. Guarda i fiori — il numero di petali spesso corrisponde a numeri di Fibonacci. Per esempio, le margherite possono avere 34, 55 o 89 petali, e i gigli spesso ne hanno 3, 5 o 8. Questi pattern aiutano le piante a crescere in modo da massimizzare luce solare e pioggia.

Anche le spirali nelle pigne e nei girasoli seguono i numeri di Fibonacci. La disposizione dei semi in un girasole, ad esempio, rispetta la sequenza. È affascinante come qualcosa di semplice come sommare due numeri possa descrivere così tanto del mondo naturale.

Fibonacci in informatica

La sequenza di Fibonacci gioca anche un ruolo chiave negli algoritmi e nelle strutture dati. Ad esempio, i numeri di Fibonacci sono usati negli algoritmi di ricerca per suddividere i problemi in parti più piccole in modo efficiente. La sequenza è alla base persino degli heap di Fibonacci, un tipo di struttura dati usata per velocizzare operazioni come trovare il percorso più breve in una rete.

Ecco un semplice esempio di come puoi generare una sequenza di Fibonacci in Python:

def fibonacci(n):
	if n <= 1:
		return n
	return fibonacci(n - 1) + fibonacci(n - 2)

# Example usage
fibonacci_numbers = []

for i in range(10):
	fibonacci_numbers.append(str(fibonacci(i)))

print(' '.join(fibonacci_numbers))

# 0 1 1 2 3 5 8 13 21 34Offerto da

Questa funzione ricorsiva mostra come si costruisce la sequenza di Fibonacci. Anche se la ricorsione è facile da capire, esistono versioni ottimizzate, come la programmazione dinamica, per calcolare i numeri di Fibonacci molto più velocemente.

In crittografia, i numeri di Fibonacci possono aiutare a generare chiavi sicure. E nell’intelligenza artificiale, ottimizzano le reti neurali per migliorare come gli algoritmi apprendono e si adattano. 

Altri esempi comuni

Ecco altri esempi di come questa sequenza appare nella vita di tutti i giorni e in ambiti specialistici:

• Nell’arte: la sequenza di Fibonacci è stata usata da artisti e architetti per secoli. Strutture famose come il Partenone presentano queste proporzioni perché risultano naturalmente gradevoli alla vista.
• Nella musica: i compositori usano i numeri di Fibonacci per creare ritmi e melodie. Ad esempio, possono associare alle semibrevi il valore 1, alle minimhe il 2 e alle semiminime il 3 per creare pattern armoniosi.
• Nel trading: i trader applicano i numeri di Fibonacci per analizzare le tendenze di mercato. Li usano per prevedere potenziali livelli di prezzo in cui i titoli potrebbero invertire, aiutandoli a decidere quando comprare o vendere.
• In fisica: nella fisica quantistica sono stati osservati pattern di Fibonacci nelle interazioni e nel comportamento delle particelle, rivelando come queste sequenze compaiano anche alle scale più piccole della natura.

Implementare la sequenza di Fibonacci in Python

Poiché Python offre diversi modi per generare la sequenza di Fibonacci, ho trattato passo dopo passo quelli più usati con esempi.

Uso di un metodo iterativo

Il metodo iterativo è uno dei modi più semplici per generare la sequenza di Fibonacci. Usa un ciclo per calcolare ogni termine della sequenza, il che lo rende più efficiente in memoria rispetto ai metodi ricorsivi. Ecco come funziona:

Imposto due variabili, a e b, a 0 e 1. Rappresentano i primi due numeri della sequenza. Poi uso un ciclo for per calcolare i numeri successivi. Aggiorno a assegnandogli il valore di b, e b diventa la somma dei precedenti a e b.

Ecco un codice Python per questo:

n = 10
a, b = 0, 1

fibonacci_numbers = []

for _ in range(n):
    fibonacci_numbers.append(str(a))
    a, b = b, a + b

print(' '.join(fibonacci_numbers))

# 0 1 1 2 3 5 8 13 21 34Offerto da

Se vuoi usare un ciclo while invece di un for, ecco come puoi scrivere il codice:

# Number of terms to print in the Fibonacci series
n = 10

# Initialize the first two terms
a, b = 0, 1
i = 0

fibonacci_numbers = []

while i < n:
	fibonacci_numbers.append(str(a))
	# Update the terms
	a, b = b, a + b
	i += 1

print(' '.join(fibonacci_numbers))

# 0 1 1 2 3 5 8 13 21 34Offerto da

Entrambi i metodi sono facilissimi da capire, il che li rende perfetti per chi inizia. 

Uso di un metodo ricorsivo

Il metodo ricorsivo è un’altra via per generare i numeri di Fibonacci. Non è veloce come il metodo iterativo per sequenze lunghe, ma è un ottimo modo per capire la logica con cui la sequenza si costruisce.

Per esempio, creo una funzione chiamata fibonacci_recursive. Questa funzione prende in input un numero n. Se n è 0 o 1, la funzione restituisce n. Questi sono i casi base che indicano alla ricorsione quando fermarsi. Per qualsiasi altro numero, la funzione si richiama per calcolare i due numeri precedenti e li somma.

Ecco il codice:

def fibonacci_recursive(n):
	if n <= 1:
		return n
	else:
		return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

num_terms = 10
fibonacci_numbers = []
for i in range(num_terms):
	fibonacci_numbers.append(str(fibonacci_recursive(i)))

print(' '.join(fibonacci_numbers))

# 0 1 1 2 3 5 8 13 21 34Offerto da

Questo metodo funziona bene per sequenze piccole ma può diventare lento man mano che la sequenza cresce, perché ricalcola più volte gli stessi valori.

Uso di un metodo ricorsivo ottimizzato con caching

Per risolvere l’inefficienza della ricorsione semplice, uso spesso la cache. L’lru_cache di Python memorizza i valori già calcolati così la funzione non deve rifare il lavoro.

Ecco come lo faccio:

from functools import lru_cache

@lru_cache(maxsize = None)
def fib_cache(n):
    if n == 0:
        return 0  
    elif n == 1:
        return 1
    else:
        return fib_cache(n-1) + fib_cache(n-2)

print(f"The Fibonacci Number is {fib_cache(10)}")

# The Fibonacci Number is 55Offerto da

Questo approccio combina la chiarezza della ricorsione con l’efficienza del caching.

Modi più avanzati per fare la sequenza di Fibonacci in Python

Se cerchi altri modi per calcolare i numeri di Fibonacci, ecco alcune tecniche più avanzate:

Esponenziazione di matrici

L’esponenziazione di matrici è uno dei modi più efficienti per calcolare i numeri di Fibonacci per valori grandi di n. Invece di ricalcolare i termini ripetutamente, questo metodo usa la moltiplicazione di matrici per ottenere risultati in tempo logaritmico.

Ecco come l’ho implementata in Python:

import numpy as np

def fibonacci_matrix(n):
	def matrix_power(matrix, power):
		return np.linalg.matrix_power(matrix, power)
	if n == 0:
		return 0
	matrix = np.array([[1, 1], [1, 0]])
	result = matrix_power(matrix, n-1)
	return result[0][0]

fibonacci_numbers = []

for i in range(10):
	fibonacci_numbers.append(str(fibonacci_matrix(i)))

print(' '.join(fibonacci_numbers))

# 0 1 1 2 3 5 8 13 21 34Offerto da

In questo codice, se n è 0 restituisce 0 come caso base. Per gli altri valori, la matrice viene elevata alla potenza (n-1) usando la funzione matrix_power di numpy. Il numero di Fibonacci in posizione n si trova nell’elemento in alto a sinistra della matrice risultante.

Formula di Binet

La formula di Binet calcola direttamente l’n-esimo numero di Fibonacci senza iterazione o ricorsione. Si basa sulla sezione aurea, φ, e usa un’espressione matematica per ottenere il risultato istantaneamente.

La formula è:

Dove:

• φ = (1 + √5) / 2​​, la sezione aurea.
• 1 - φ è il coniugato di φ.

Ecco il codice Python per la formula di Binet:

import math

def fibonacci_binet(n):
    phi = (1 + math.sqrt(5)) / 2
    return round((phi ** n - (1 - phi) ** n) / math.sqrt(5))

# Find the 10th Fibonacci number
n = 10
result = fibonacci_binet(n)
print(f"The Fibonacci Number of {n}th term is {result}" )

# The Fibonacci Number of 10th term is 55Offerto da

In questo codice, la funzione fibonacci_binet(n) calcola l’n-esimo numero di Fibonacci usando la formula di Binet. All’interno della funzione, calcolo phi (la sezione aurea) come (1 + math.sqrt(5)) / 2, usando math.sqrt() per la radice quadrata di 5. La formula (phi ** n - (1 - phi) ** n) / math.sqrt(5) viene poi applicata per trovare direttamente l’n-esimo numero di Fibonacci. Infine, uso la funzione round() per gestire eventuali piccole imprecisioni dei numeri in virgola mobile.

Array

Puoi anche usare array per generare e memorizzare l’intera sequenza di Fibonacci. Questo è utile quando hai bisogno di più termini contemporaneamente.

Ecco il codice:

def fibonacci(n):
    if n <= 0:
        return "Incorrect Output"
    data = [0, 1]  # Initialize list with first two Fibonacci terms: 0 and 1
    if n > 2:
        for i in range(2, n):  # Start loop from the third term
            data.append(data[i-1] + data[i-2])  # Calculate next term as sum of previous two
    return data[n-1]  # Return the nth term

print(f"Fibonacci Number: {fibonacci(10)}")

# Fibonacci Number: 34Offerto da

Backtracking

Il backtracking è un’altra opzione che posso usare, soprattutto quando voglio combinare ricorsione e memoization per prestazioni migliori.

Ecco il codice:

def fibonacci_backtracking(n, computed ={0: 0, 1: 1}):
    if n in computed:
        return computed[n]
    computed[n] = fibonacci_backtracking(n - 1) + fibonacci_backtracking(n - 2)
    return computed[n]

n = 10
result = fibonacci_backtracking(n)
print(f"The {n}th Fibonacci term is {result}")

# The 10th Fibonacci term is 55Offerto da

Complessità degli algoritmi di Fibonacci in Python

Abbiamo visto parecchi esempi! Guardiamo ora le differenze in termini di complessità temporale e spaziale. Come abbiamo detto, alcuni metodi sono veloci ma usano più memoria, mentre altri sono più lenti ma richiedono meno spazio. Ho preparato questa tabella per confrontare l’efficienza di ciascun approccio.

Nella tabella sopra, ecco cosa significa ogni complessità temporale e spaziale:

Complessità temporale

• O(n): l’algoritmo itera una volta sulla sequenza eseguendo un numero fisso di operazioni per ciascun elemento. Il tempo impiegato cresce linearmente con la dimensione dell’input n.

• O(1): il numero di Fibonacci è calcolato usando un numero fisso di operazioni senza iterazione o ricorsione.

• O(2ⁿ): l’algoritmo effettua due chiamate ricorsive per ogni input, il che porta a una crescita esponenziale del numero di chiamate man mano che n aumenta.

• O(log n): il tempo di esecuzione cresce in proporzione al logaritmo della dimensione dell’input n.

Complessità spaziale

• O(n): l’algoritmo usa memoria che cresce direttamente con il numero di input n. Qui, ogni elemento richiede una quantità fissa di spazio.

• O(1): l’uso di memoria rimane costante indipendentemente dalla dimensione dell’input.

• O(2ⁿ): usa spazio esponenziale a causa della creazione di nuovi stati per ogni diramazione.

• O(log n): le moltiplicazioni di matrici intermedie usano memoria logaritmica.

Considerazioni finali

Come hai visto, in Python puoi calcolare i numeri di Fibonacci con molti metodi diversi, da semplici cicli a tecniche avanzate come l’esponenziazione di matrici e la formula di Binet. Ogni metodo ha punti di forza e compromessi.

Spero che tu abbia imparato qualcosa sia sulla sequenza di Fibonacci sia sulla programmazione in Python. Se vuoi esplorare di più su Python e argomenti correlati, dai un’occhiata al nostro corso Introduction to Python. Puoi anche provare il nostro percorso di carriera completo Python Developer e imparare tecniche di programmazione fino a iniziare a sviluppare i tuoi pacchetti!