Python è il mio primo linguaggio di programmazione, e sto imparando da "Come pensare come uno scienziato informatico". Nel Capitolo 5 l'autore fornisce il seguente esempio sulla ricorsione:
def factorial(n):
if n == 0:
return 1
else:
recurse = factorial(n-1)
result = n * recurse
return result
Capisco che se n = 3, la funzione eseguirà il secondo ramo. Ma quello che non capisco è cosa succede quando la funzione entra nel secondo ramo. Qualcuno può spiegarmelo?
Quello che succede è che la funzione viene chiamata di nuovo, sotto il controllo della prima chiamata, e dopo che ci sono due invocazioni di factorial attive contemporaneamente (ma il primo è in attesa del il secondo da restituire). Ognuno di essi ha una propria copia di n : l'invocazione subordinata ha n == 2 mentre l'invocazione originale ha ancora n == 3 . L'invocazione subordinata si chiama quindi un'altra volta, e così via, fino a quando non ci sono quattro versioni della funzione in memoria (ma i primi tre sono inattivi, in attesa che l'ultimo ritorni).
I valori delle variabili e gli indirizzi di ritorno di tutte quelle invocazioni vengono mantenuti nello stack delle chiamate e scompaiono automaticamente quando viene restituita una chiamata. (Questo è il motivo per cui una ricorsione troppo nidificata può causare il fenomeno di questo sito: l'overflow dello stack.)
Un buon modo per capire cosa succede realmente quando viene chiamata una funzione ricorsiva è simulare lo stack di chiamate con carta e penna, scrivendo quali versioni di n ci sono a in qualsiasi momento e quali sono i loro valori. Una chiamata a factorial 3 è la giusta dimensione per quell'esercizio.
Ho rifratto il codice, nella speranza che sia più chiaro.
def factorial(n):
if n < 0:
raise ValueError
if n == 0:
return 1
else:
return factorial(n-1) * n
Dice:
Questa è la definizione: scriviamo semplicemente la definizione matematica di factorial in python.
Guarda anche la risposta di Kilian Foth che considera i problemi di overflow dello stack.
Leggi altre domande sui tag python