Il fattoriale con la ricorsione in Python
In questa lezione scriverai una funzione ricorsiva per calcolare il fattoriale e capirai il ruolo del caso base.
Introduzione
Il problema
Alcuni problemi si descrivono in modo naturale tramite una versione più piccola di sé stessi: una cartella contiene cartelle, un albero genealogico contiene alberi più piccoli, n! è n per (n - 1)!. La ricorsione ti permette di scrivere codice che segue direttamente definizioni del genere.
Immaginalo così
La ricorsione è come una fila di persone che si passano una domanda. Per sapere quanto fa 6!, il primo della fila chiede al vicino quanto fa 5! e aspetta. Quello a sua volta chiede 4!, e così via, finché a qualcuno viene chiesto 1! e risponde subito. Poi le risposte tornano indietro lungo la fila, e ognuno ci moltiplica il proprio numero.
factorial(6)🙋 Il primo della fila: 6 × la risposta che sta aspettandonumber * factorial(number - 1)➡️ Fai la stessa domanda al vicino, con un numero più piccoloif number <= 1: return 1🛑 L'ultimo della fila risponde subito: 1720⬅️ Le risposte tornano indietro lungo la fila: 720Una funzione ricorsiva chiama sé stessa con un input più piccolo finché arriva a un caso base a cui può rispondere direttamente; qui factorial(n) = n × factorial(n - 1) e factorial(1) = 1.
Punti chiave
if number <= 1: return 1è il caso base; senza, le chiamate non si fermerebbero mai.return number * factorial(number - 1)chiama la stessa funzione con un numero più piccolo.factorial(6)aspettafactorial(5), che aspettafactorial(4), giù fino afactorial(1).raise ValueError(...)rifiuta i numeri negativi, che altrimenti non arriverebbero mai al caso base.
Quando si usa?
- Problemi definiti tramite versioni più piccole: alberi, cartelle, dati annidati.
- Algoritmi divide et impera come il merge sort.
- Imparare come funziona lo stack delle chiamate.
Quando non serve
- Semplici ripetizioni come il fattoriale nel codice vero: un ciclo o
math.factorialè più veloce e non ha limiti di profondità. - Input molto profondi: Python si ferma a circa 1.000 chiamate annidate con RecursionError.
Guarda come funziona
Premi Passo per seguire ogni chiamata. Le nuove chiamate finiscono sullo stack delle chiamate e ognuna restituisce il suo valore a chi l'ha fatta.
Codice di esempio
def factorial(number):
if number < 0:
raise ValueError("Factorial is undefined for negative numbers")
if number <= 1:
return 1
return number * factorial(number - 1)
print(factorial(6))
Risultato dell'esecuzione
720
Spiegazione del codice
Quando number vale 0 o 1, la funzione restituisce subito 1. È il caso base che impedisce alla ricorsione di andare avanti all'infinito. Per gli altri valori, la funzione restituisce number moltiplicato per factorial(number - 1). Ogni chiamata ricorsiva viene salvata nello stack delle chiamate (call stack), quindi la profondità della ricorsione è O(n).
Modifica i valori ed esegui il programma nel compilatore Python online CodeUtility senza installare Python.
Esercizi di approfondimento
Prova a modificare il codice seguendo i suggerimenti qui sotto. Cambiare il codice e osservare il risultato ti aiuta a capire molto più che leggerlo soltanto.
- Prova con una lista vuota, una lista di un solo elemento e una lista con valori ripetuti.
- Stampa lo stato dopo ogni passo per vedere l'algoritmo al lavoro.
- Misura il tempo con 100, 1.000 e 10.000 elementi e confrontalo con un'altra soluzione.
Errori comuni
Dimenticare il caso base
La funzione chiama sé stessa all'infinito finché Python solleva RecursionError.
def factorial(number):
return number * factorial(number - 1)
def factorial(number):
if number <= 1:
return 1
return number * factorial(number - 1)
Hai finito questa lezione?
Segnala come imparata per tenere traccia dei tuoi progressi.
Esercitati con una sfida
Usa ciò che questa lezione spiega per risolvere un problema reale. Ogni sfida gira nel browser, con test immediati e una revisione dell'IA.
- Fattoriale Moltiplica tutti i numeri interi positivi fino a n. Facile
- Recursive Power Compute a power recursively by halving the exponent. Media