Algoritmi Python

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.

  • Intermedio
  • 2 min di lettura
  • 1 esempio eseguibile

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.

Dalla fila di persone al codice
factorial(6)🙋 Il primo della fila: 6 × la risposta che sta aspettando
number * factorial(number - 1)➡️ Fai la stessa domanda al vicino, con un numero più piccolo
if number <= 1: return 1🛑 L'ultimo della fila risponde subito: 1
720⬅️ Le risposte tornano indietro lungo la fila: 720
Ogni chiamata aspetta una chiamata più piccola finché il caso base risponde.
In una frase

Una 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

  1. if number <= 1: return 1 è il caso base; senza, le chiamate non si fermerebbero mai.
  2. return number * factorial(number - 1) chiama la stessa funzione con un numero più piccolo.
  3. factorial(6) aspetta factorial(5), che aspetta factorial(4), giù fino a factorial(1).
  4. 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

Esegui codice →
main.py
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))
Crea un pulsante Run per questo esempio

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.

  1. Prova con una lista vuota, una lista di un solo elemento e una lista con valori ripetuti.
  2. Stampa lo stato dopo ogni passo per vedere l'algoritmo al lavoro.
  3. Misura il tempo con 100, 1.000 e 10.000 elementi e confrontalo con un'altra soluzione.
Esegui nel compilatore Python →

Errori comuni

Dimenticare il caso base

La funzione chiama sé stessa all'infinito finché Python solleva RecursionError.

Problema
def factorial(number):
    return number * factorial(number - 1)
Correzione
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.

Tutte le sfide