Ricorsione
Quando si impara a programmare, spesso si affrontano i compiti in modo lineare e diretto. Ma cosa succede se incontriamo un problema che richiede di essere scomposto in problemi più piccoli e simili? È qui che entra in gioco la ricorsione.
In parole semplici, la ricorsione avviene quando una funzione chiama se stessa durante la sua esecuzione. Questo potrebbe sembrare che crei un ciclo infinito, ma se progettiamo correttamente la nostra funzione, alla fine raggiungerà un punto in cui non chiamerà più se stessa.
Immagina una matrioska. Ogni volta che apri una bambola, ce n'è una più piccola all'interno, e continui finché non raggiungi la bambola più piccola che non può essere aperta. Questo processo di apertura delle bambole è un po' come la ricorsione. Per raggiungere la bambola più piccola, che è come risolvere il problema più difficile, lo risolvi ripetutamente affrontando versioni più semplici dello stesso problema (aprendo le bambole più grandi) finché non raggiungi un punto in cui il problema non può essere ulteriormente ridotto (l'ultima bambola).
Il processo di risolvere un grande problema suddividendolo ricorsivamente in problemi più piccoli fino a raggiungere il più piccolo/semplice possibile è meglio compreso con il concetto di "salto di fede ricorsivo".
Salto di Fede Ricorsivo
Quando si implementa una soluzione ricorsiva a un problema, di solito si crea una funzione che funziona chiamando se stessa a un certo punto. La parte in cui chiama se stessa è solitamente chiamata chiamata ricorsiva.
La grande forza delle soluzioni ricorsive è che si può assumere che la funzione funzioni correttamente quando viene chiamata con alcuni argomenti semplici, e poi implementare il comportamento corretto per quelli più complessi. Simile a chiamare altre funzioni come
sqrt, max, abs e altre che abbiamo usato prima, puoi assumere che la funzione funzioni per alcuni argomenti più piccoli/più semplici e chiamarli per costruire il risultato corrente sopra di essi.💡
L'unico requisito è assicurarsi che la funzione arrivi al caso base (il caso più semplice). Altrimenti, avremmo una funzione ricorsiva che gira all'infinito e potremmo ottenere un StackOverflow!
Come dimostrazione di come si possa avere un calcolo all'interno di una funzione ricorsiva, possiamo provare a calcolare la somma di tutti i numeri da
0, 1, 2, ..., n dato un numero n.Implementiamo la funzione
sum passo dopo passo. Il primo passo è assicurarsi che la funzione funzioni correttamente per il caso più semplice (contare correttamente la somma per n pari a 0 o 1):def sum(n):
print(f'sum({n})', end=' -> ')
if n == 0: # Nel caso in cui n sia 0 => la somma è 0
return 0 # Ferma l'esecuzione della funzione qui
if n == 1: # Nel caso in cui n sia 1 => la somma è 1
return 1 # Ferma l'esecuzione della funzione qui
print(sum(1)) # sum(1) -> 1
print(sum(0)) # sum(0) -> 0
print(sum(2)) # sum(2) -> None (poiché non abbiamo implementato questa parte)Avendo questa parte della funzione, possiamo già usare il fatto che
sum(0) restituirà sempre correttamente 0, mentre sum(1) restituirà sempre 1. La funzione funzionerà correttamente anche se chiamiamo la funzione sum con argomenti 0 o 1 dalla funzione stessa.Quindi, possiamo fare un passo avanti e implementare la funzione
sum per n = 2 e n = 3 utilizzando i risultati di sum(1) e sum(0):def sum(n):
print(f'sum({n})', end=' -> ')
if n == 0:
return 0
if n == 1:
return 1
if n == 2: # Se n è 2, possiamo aggiungere 2 al risultato di sum(1) implementato sopra
return n + sum(1) # oppure n + sum(n - 1)
if n == 3: # Se n è 3, possiamo aggiungere 3 al risultato di sum(2) implementato sopra
return n + sum(2) # oppure n + sum(n - 1)
print(sum(1)) # sum(1) -> 1
print(sum(0)) # sum(0) -> 0
print(sum(2)) # sum(2) -> sum(1) -> 3
print(sum(3)) # sum(3) -> sum(2) -> sum(1) -> 6
print(sum(4)) # sum(4) -> None (poiché non abbiamo implementato questa parte)In questo modo, è ovvio che la funzione
sum funziona correttamente per casi semplici come n pari a 0, 1, 2 o 3.Avendo questo, possiamo implementare la funzione per altri valori di
n maggiori di 3. L'unico requisito è arrivare a quei valori più piccoli di n (0, 1, 2 o 3) quando chiamiamo la funzione sum da se stessa. Quindi, per valori più grandi di n, come 4, 5 o 6, ecc., possiamo implementare la funzione sum utilizzando il fatto che per calcolare sum(4), possiamo aggiungere 4 al risultato di sum(3), mentre per calcolare sum(5) possiamo aggiungere 5 al risultato di sum(4):def sum(n):
print(f'sum({n})', end=' -> ')
if n == 0:
return 0
if n == 1:
return 1
if n == 2:
return n + sum(1)
if n == 3:
return n + sum(2)
# Per tutti gli altri casi (4, 5, 6, ...)
return n + sum(n - 1)
print(sum(2)) # sum(2) -> sum(1) -> 3
print(sum(3)) # sum(3) -> sum(2) -> sum(1) -> 6
print(sum(4)) # sum(4) -> sum(3) -> sum(2) -> sum(1) -> 10
# ...Le parti chiave di una funzione ricorsiva sono:
- Caso base: Una condizione che ferma la ricorsione. Senza questa, la funzione chiamerebbe se stessa indefinitamente, causando un ciclo infinito.
Qui, è
n == 0en == 1.
- Passo ricorsivo: Dove la funzione chiama se stessa, di solito con un argomento diverso.
Qui, è
sum(n - 1).
Dato che le chiamate per
n == 1, n == 2 e n == 3 sono esattamente le stesse per n == 4, n == 5, ecc., possiamo persino semplificare la funzione sum avendo solo 1 caso base (per n == 0):def sum(n):
print(f'sum({n})', end=' -> ')
if n == 0:
return 0
return n + sum(n - 1)
print(sum(2)) # sum(2) -> sum(1) -> sum(0) -> 3
print(sum(3)) # sum(3) -> sum(2) -> sum(1) -> sum(0) -> 6
print(sum(4)) # sum(4) -> sum(3) -> sum(2) -> sum(1) -> sum(0) -> 10
# ...In questo modo, con il salto di fede ricorsivo, assumiamo/sappiamo che la funzione funziona correttamente per casi più piccoli/più semplici, e costruiamo il resto della funzione basandoci su quei casi. Questo aiuta a comprendere come funzionano le funzioni ricorsive e come possono essere implementate.
💡
Chiamare la funzione ricorsivamente è come chiamare una funzione completamente diversa che sai per certo funzionerà con gli argomenti passati.