Python - Ricorsione: Una Guida per Principianti

Ciao a tutti, futuri maghi Python! Oggi, intraprenderemo un viaggio avventuroso nel mondo della ricorsione. Non preoccupatevi se sembra un po' intimidante – prometto che lo renderemo divertente e facile da capire. Allora, afferra la tua bevanda preferita, metti te stesso a tuo agio, e abbattoni!

Cos'è la Ricorsione?

Immagina di stando tra due specchi che si affacciano l'uno sull'altro. Vedi un numero infinito di riflessioni, giusto? Ecco un po' come la ricorsione nella programmazione! In termini semplici, la ricorsione è quando una funzione si chiama se stessa per risolvere un problema.

Iniziamo con un esempio semplice:

def countdown(n):
if n <= 0:
print("Blastoff!")
else:
print(n)
countdown(n - 1)

countdown(5)

Se esegui questo codice, vedrai:

5
4
3
2
1
Blastoff!

Ora, scomponiamo questo:

1. Definiamo una funzione chiamata countdown che prende un numero n.
2. Se n è 0 o meno, stampiamo "Blastoff!"
3. Altrimenti, stampiamo n e poi chiamiamo countdown di nuovo con n - 1.

Questa è la ricorsione in azione! La funzione continua a chiamarsi se stessa con un numero più piccolo fino a raggiungere lo zero.

Componenti della Ricorsione

Ogni funzione ricorsiva ha due componenti principali:

1. Caso Base: Questo è la condizione che ferma la ricorsione.
2. Caso Ricorsivo: Questo è dove la funzione si chiama se stessa.

Nel nostro esempio di countdown:

• Il caso base è if n <= 0
• Il caso ricorsivo è countdown(n - 1)

Guardiamo un altro esempio classico: il calcolo del fattoreiale.

def factorial(n):
if n == 0 or n == 1:
return 1
else:
return n * factorial(n - 1)

print(factorial(5))  # Output: 120

Ecco cosa succede:

1. Se n è 0 o 1, ritorniamo 1 (questo è il nostro caso base).
2. Altrimenti, moltiplichiamo n per il fattoreiale di n - 1 (questo è il nostro caso ricorsivo).

Quindi, factorial(5) diventa: 5 factorial(4) 5 (4 factorial(3)) 5 (4 (3 factorial(2))) 5 (4 (3 (2 factorial(1)))) 5 (4 (3 (2 1))) 5 4 3 2 1 = 120

Il Potere della Ricorsione

La ricorsione può rendere alcuni problemi complessi molto più semplici da risolvere. Guardiamo un esempio leggermente più avanzato: la sequenza di Fibonacci.

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

for i in range(10):
print(fibonacci(i), end=" ")
# Output: 0 1 1 2 3 5 8 13 21 34

Questa funzione calcola il numero di Fibonacci ennesimo. La sequenza di Fibonacci inizia con 0 e 1, e ogni numero successivo è la somma dei due precedenti.

Ricerca Binaria Utilizzando la Ricorsione

Ora, affrontiamo un esempio più pratico: la ricerca binaria. Questo è un modo efficiente per trovare un elemento in una lista ordinata.

def binary_search(arr, low, high, x):
if high >= low:
mid = (high + low) // 2

if arr[mid] == x:
return mid
elif arr[mid] > x:
return binary_search(arr, low, mid - 1, x)
else:
return binary_search(arr, mid + 1, high, x)
else:
return -1

arr = [2, 3, 4, 10, 40]
x = 10

result = binary_search(arr, 0, len(arr)-1, x)

if result != -1:
print(f"Elemento è presente all'indice {result}")
else:
print("Elemento non è presente nell'array")

Questa funzione funziona ripetendo il dividere l'intervallo di ricerca in due. Se il valore della chiave di ricerca è minore dell'elemento nel mezzo dell'intervallo, restringi l'intervallo alla metà inferiore. Altrimenti, restringi alla metà superiore. Controlla ripetutamente fino a che il valore viene trovato o l'intervallo è vuoto.

Quando Usare la Ricorsione

La ricorsione è particolarmente utile per:

1. Problemi che possono essere scomposti in sottoproblemi simili
2. Strutture dati a forma di albero (ad esempio, sistemi di file, HTML DOM)
3. Algoritmi come QuickSort, MergeSort, ecc.

Tuttavia, la ricorsione non è sempre la migliore soluzione. Può essere memory-intensive per ricorsioni molto profonde e a volte un semplice ciclo può essere più efficiente e più facile da capire.

Tabella dei Metodi di Ricorsione

Metodo	Descrizione	Esempio
Ricorsione Diretta	Una funzione si chiama direttamente se stessa	I nostri esempi countdown e factorial
Ricorsione Indiretta	La funzione A chiama la funzione B, che a sua volta chiama la funzione A	Vedi esempio sotto
Ricorsione a Coda	La chiamata ricorsiva è l'ultima cosa eseguita dalla funzione	Il nostro esempio countdown
Ricorsione Non a Coda	La chiamata ricorsiva non è l'ultima cosa eseguita dalla funzione	Il nostro esempio factorial

Ecco un esempio di ricorsione indiretta:

def is_even(n):
if n == 0:
return True
else:
return is_odd(n - 1)

def is_odd(n):
return not is_even(n)

print(is_even(4))  # Output: True
print(is_odd(4))   # Output: False

In questo esempio, is_even chiama is_odd, che a sua volta chiama is_even.

Conclusione

Congratulazioni! Hai appena fatto i tuoi primi passi nel fascinante mondo della ricorsione. Ricorda, come ogni strumento potente, la ricorsione dovrebbe essere usata saggiamente. Può rendere il tuo codice più elegante e risolvere problemi complessi con facilità, ma può anche rendere problemi semplici inutilmente complicati.

Mentre continui il tuo viaggio con Python, incontrerai molte altre situazioni in cui la ricorsione può essere applicata. Continua a praticare, e presto ricorrerai come un professionista!

Credits: Image by storyset