Una funzione ricorsiva è una funzione che chiama se stessa per risolvere un problema. Questo concetto, molto potente, è alla base di molte soluzioni eleganti in Python, soprattutto quando si ha a che fare con strutture dati complesse o problemi che possono essere suddivisi in sottoproblemi simili.
Come si costruisce una funzione ricorsiva
Una funzione ricorsiva deve sempre avere una condizione di terminazione, detta anche caso base, per evitare chiamate infinite. La struttura tipica è:
def funzione(parametro):
{
if condizione_di_stop:
{
return risultato
}
else:
{
return funzione(nuovo_parametro)
}
}
Output:
Il risultato finale dipenderà dalla logica implementata nella funzione. Vediamolo con alcuni esempi concreti.
Esempi semplici ma efficaci di funzioni ricorsive
1. Calcolo del fattoriale di un numero
Il fattoriale di un numero (n!) è il prodotto di tutti i numeri interi positivi minori o uguali a n. Ecco una funzione ricorsiva per calcolarlo:
def fattoriale(n):
{
if n == 0:
{
return 1
}
else:
{
return n * fattoriale(n - 1)
}
}
Output:
print(fattoriale(5)) # Output: 120
2. Generazione della sequenza di Fibonacci
La sequenza di Fibonacci è una serie di numeri in cui ciascun numero è la somma dei due precedenti. Ecco un esempio ricorsivo:
def fibonacci(n):
{
if n <= 1:
{
return n
}
else:
{
return fibonacci(n - 1) + fibonacci(n - 2)
}
}
Output:
for i in range(10):
{
print(fibonacci(i), end=" ")
}
# Output: 0 1 1 2 3 5 8 13 21 34
Pro e contro dell’uso della ricorsione
Vantaggi
- Il codice è spesso più leggibile e conciso.
- Perfetta per problemi con strutture dati nidificate, come gli alberi.
- Segue un approccio più matematico e naturale in molti contesti.
Svantaggi
- Può portare a errori di stack overflow se non gestita correttamente.
- Spesso è meno efficiente in termini di memoria rispetto all’iterazione.
- Potrebbe essere più difficile da debuggare per chi è alle prime armi.
Esempio di ricorsione infinita
Una funzione senza caso base può causare una chiamata infinita:
def loop_infinito():
{
return loop_infinito()
}
Questo produrrà un errore RecursionError: maximum recursion depth exceeded.
Ricorsione più efficiente: introduzione alla memoization
Per migliorare le performance, possiamo utilizzare la memoization, ovvero memorizzare i risultati già calcolati:
memo = {}
def fibonacci_mem(n):
{
if n in memo:
{
return memo[n]
}
if n <= 1:
{
memo[n] = n
}
else:
{
memo[n] = fibonacci_mem(n - 1) + fibonacci_mem(n - 2)
}
return memo[n]
}
Questa tecnica riduce drasticamente i tempi di esecuzione nei casi con molte chiamate ripetute.
Confronto diretto tra ricorsione e iterazione
Utilizzare la ricorsione:
La ricorsione è ideale quando il problema può essere suddiviso in sottoproblemi simili, come nel caso di strutture gerarchiche (es. alberi, grafi). Offre un approccio più elegante e spesso più naturale.
Optare per l’iterazione:
L’iterazione è più efficiente in termini di memoria e viene preferita quando si lavora con loop semplici, dove il numero di iterazioni è chiaro e definito.
