Informazioni su Ricorsione
La ricorsione è un modo per eseguire ripetutamente del codice all'interno di una funzione tramite la funzione stessa che si chiama.
Le funzioni che chiamano se stesse sono dette funzioni ricorsive.
La ricorsione può essere vista come un altro modo di eseguire un ciclo o di iterare.
E come per i cicli, si usa un'espressione booleana o un test True/False per determinare quando fermare l'esecuzione ricorsiva.
A differenza dei cicli, la ricorsione senza terminazione in Python non può essere eseguita all'infinito.
I valori usati in ogni chiamata di funzione vengono inseriti nel proprio frame sullo stack dell'interprete Python.
Se il numero totale di chiamate di funzione occupa più spazio di quanto lo stack possa contenerne, si verifica un errore.
Implementazione iterativa e ricorsiva a confronto
I cicli e la ricorsione possono sembrare simili, nel senso che entrambi sono iterativi.
Tuttavia, appaiono diversi, sia a livello di codice sia a livello di implementazione.
Un ciclo può avvenire all'interno dello stesso frame sullo stack delle chiamate.
Di solito questo viene gestito aggiornando il valore di una o più variabili per mantenere progressivamente lo stato a ogni iterazione.
È un'implementazione efficiente, ma può risultare un po' disordinata guardando il codice.
La ricorsione, invece di aggiornare lo stato delle variabili, può passare valori aggiornati direttamente come argomenti alla chiamata successiva (iterazione) della stessa funzione.
Questo rende più ordinato il corpo della funzione e può chiarire come avviene ogni aggiornamento.
Tuttavia, è anche un'implementazione meno efficiente, dato che ogni chiamata alla stessa funzione aggiunge un altro frame allo stack.
Ricorsione: perché sì e perché no?
Se c'è il rischio di causare un errore o un overflow dello stack, perché qualcuno dovrebbe usare una strategia ricorsiva per risolvere un problema?
Leggibilità, tracciabilità e intento.
Ci possono essere situazioni in cui una soluzione è più leggibile e/o più facile da seguire quando è espressa tramite la ricorsione invece che tramite un ciclo.
Possono anche esserci vincoli del programma legati all'uso o alla modifica dei dati, alla gestione della complessità, alla delega delle responsabilità o all'organizzazione del carico di lavoro.
I problemi che si prestano alla ricorsione includono problemi complessi ma ripetitivi che diventano via via più piccoli, in particolare gli algoritmi divide and conquer e gli algoritmi cumulativi.
Tuttavia, a causa del limite di Python sul numero di frame consentiti nello stack, non tutti i problemi traggono beneficio da una strategia completamente ricorsiva.
I problemi meno adatti alla ricorsione includono quelli che hanno uno stato stabile, ma devono ripetersi per un certo numero di cicli, i problemi che devono essere eseguiti in modo asincrono e le situazioni che richiedono un gran numero di iterazioni.
Strategia iterativa e ricorsiva a confronto: l'insicurezza di Indira
Indira riceve automaticamente sul conto bancario il suo assegno mensile di previdenza sociale, il secondo mercoledì di ogni mese.
Indira è preoccupata di riuscire a tenere i conti in ordine.
Teme di emettere assegni prima che il denaro venga depositato.
Chiede a sua nipote Adya di darle un elenco delle date in cui il denaro comparirà sul suo conto.
Adya, che sta appena imparando a programmare in Python, scrive un programma basato sui suoi primi pensieri.
Vuole restituire una list con le date dei depositi, in modo che possano essere stampate.
Vuole scrivere una funzione che funzioni per qualsiasi anno.
Nel caso in cui il calendario cambi (o nel caso in cui altri parenti vogliano che Adya calcoli le loro date di deposito), decide che la funzione ha bisogno di un parametro aggiuntivo per il giorno della settimana.
Infine, Adya decide che la funzione ha bisogno di un parametro per indicare quale giorno della settimana del mese sia: il primo, il secondo e così via.
Per soddisfare tutte queste esigenze, decide di usare la classe date importata da datetime.
Mettendo insieme tutto questo, Adya arriva a:
from datetime import date
def paydates_for_year(year, weekday, ordinal):
"""Returns a list of the matching weekday dates.
Arguments:
year (int): The year (e.g. 2022).
weekday (int): The weekday number (e.g. 3 for Wednesday).
ordinal (int): Which weekday of the month (e.g. 2 for the second day).
Returns:
output (list): Matching weekday dates.
"""
output = []
for month in range(1, 13):
for day_num in range(1, 8):
if date(year, month, day_num).isoweekday() == weekday:
output.append(date(year, month, day_num + (ordinal - 1) * 7))
break
return output
# find the second Wednesday of the month for all the months in 2022
print(paydates_for_year(2022, 3, 2))
Questo primo tentativo funziona, ma Adya si chiede se può riorganizzare il codice per usare meno righe e meno cicli annidati.
Ha anche letto che è bene ridurre al minimo la modifica dello stato, quindi vorrebbe vedere se può evitare di modificare alcune delle sue variabili come output, month e day_num .
Conosce anche la ricorsione e riflette su come potrebbe modificare il suo programma per usare un approccio ricorsivo.
Le variabili che vengono create e modificate nella sua funzione iterativa potrebbero invece essere passate come argomenti.
Invece di modificare le variabili all'interno della sua funzione, potrebbe passare valori aggiornati come argomenti alla chiamata di funzione successiva.
Con queste intenzioni arriva a questo approccio ricorsivo:
from datetime import date
def paydates_for_year_rec(year, weekday, ordinal, month, day_num, output):
"""Returns a list of the matching weekday dates
Arguments:
year (int): The year (e.g. 2022).
weekday (int): The weekday number (e.g. 3 for Wednesday).
ordinal (int): Which weekday of the month (e.g. 2 for the second day).
month (int): The month number currently being processed.
day_num (int): The day number of the month currently being processed.
Returns:
output (list): Matching weekday dates.
"""
if month == 13:
return output
if date(year, month, day_num).isoweekday() == weekday:
return paydates_for_year_rec(
year, weekday, ordinal, month + 1, 1, output
+ [date(year, month, day_num + (ordinal - 1) * 7)]
)
return paydates_for_year_rec(year, weekday, ordinal, month, day_num + 1, output)
# find the second Wednesday of the month for all the months in 2022
print(paydates_for_year_rec(2022, 3, 2, 1, 1, []))
Adya è felice che non ci siano più cicli annidati, né stato modificato, e che ci siano 2 righe di codice in meno!
È un po' preoccupata che l'approccio ricorsivo usi più passaggi di quello iterativo, e quindi sia meno «performante».
Ma riscrivere il problema usando la ricorsione l'ha sicuramente aiutata a gestire gli antiestetici cicli annidati (un rischio per le prestazioni), l'estesa modifica dello stato e la confusione intorno a una logica condizionale complessa.
Inoltre, le sembra più «leggibile»: è sicura che, quando tornerà su questo codice dopo una pausa, riuscirà a rileggerlo e a ricordare più facilmente cosa fa.
In futuro, Adya potrebbe provare ad affrontare i problemi prima in modo ricorsivo.
Potrebbe trovare più facile affrontare inizialmente il problema in passaggi chiari, quando annidamento, modifiche e complessità sono ridotti al minimo.
Dopo aver elaborato la logica di base, può poi concentrarsi sull'ottimizzazione dei suoi passaggi ricorsivi iniziali, trasformandoli in un approccio iterativo più performante.
Ancora più avanti, quando imparerà a conoscere tuples, Adya potrà considerare altri approcci di «ottimizzazione», come usare una list comprehension con Calendar.itermonthdates, o la memoizzazione di determinati valori.
Una variante ricorsiva: la chiamata in coda
Una chiamata in coda si ha quando l'ultima istruzione di una funzione chiama soltanto se stessa e nient'altro.
Questo esempio non è una chiamata in coda, dato che la funzione aggiunge 1 al risultato della chiamata a se stessa:
def print_increment(step, max_value):
if step > max_value:
return 1
print(f'The step is {step}')
return 1 + print_increment(step + 1, max_value)
def main():
retval = print_increment(1, 2)
print(f'retval is {retval} after recursion')
if __name__ == "__main__":
main()
Questo stampa:
The step is 1
The step is 2
retval is 3 after recursion
Per riorganizzarlo in una chiamata in coda, rendi retval un parametro di print_increment.
def print_increment(step, max_value, retval):
if step > max_value:
return retval
print(f'The step is {step}')
return print_increment(step + 1, max_value, retval + 1)
def main():
retval = print_increment(1, 2, 1)
print(f'retval is {retval} after recursion')
if __name__ == "__main__":
main()
Potresti trovare una chiamata in coda ancora più facile da seguire rispetto a una chiamata ricorsiva che non è in coda.
Tuttavia, quando si usa la ricorsione è sempre importante sapere che non ci saranno così tante iterazioni da far traboccare lo stack.
I limiti della ricorsione in Python
Alcuni linguaggi sono in grado di ottimizzare le chiamate in coda, così che ogni chiamata ricorsiva riutilizzi il frame dello stack della prima chiamata alla funzione (in modo simile a come un ciclo riutilizza un frame), invece di aggiungere un altro frame allo stack.
Python non è uno di quei linguaggi.
Per proteggersi dall'overflow dello stack, Python ha un limite di ricorsione che per impostazione predefinita è di mille frame.
Viene sollevata un'eccezione RecursionError quando l'interprete rileva che il limite di ricorsione è stato superato.
È possibile usare il metodo sys.setrecursionlimit per aumentare il limite di ricorsione, ma così facendo si rischia un segmentation fault a runtime che manderà in crash il programma e, potenzialmente, anche il sistema operativo.
Risorse
Per saperne di più sull'uso della ricorsione in Python, puoi iniziare da
{one: "1 esercizio", many: "%{count} esercizi", other: "%{count} esercizi"}
