Ricorsione — come funziona, esempi e casi base

In matematica, la ricorsione significa definire una funzione, una successione o un processo usando casi più piccoli della stessa idea. Una definizione ricorsiva funziona solo se include un caso base e una regola che porta ogni nuovo caso verso quel caso base.

Se ti serve solo l’idea essenziale, è questa: la ricorsione smette di essere utile nel momento in cui la regola dei passi più piccoli non raggiunge più un punto di arresto valido.

Che cosa significa ricorsione in matematica

Una definizione ricorsiva non elenca ogni caso separatamente. Invece, fornisce un punto di partenza e una regola per costruire i casi più grandi a partire da quelli più piccoli.

Questo è diverso da una formula diretta. Una formula diretta dà la risposta a partire dall’input in un’unica espressione. Una definizione ricorsiva riduce il problema passo dopo passo finché non raggiunge un caso già noto.

Perché è necessario un caso base

Il caso base è il punto di arresto. Senza di esso, la definizione continua a rimandare a casi sempre più piccoli senza mai concludersi.

Anche il caso base deve essere coerente con la regola scelta. Se il passo ricorsivo riduce da $n$ a $n-1$, allora il caso base deve essere raggiungibile secondo quel modello per gli input ammessi.

Esempio svolto: ricorsione del fattoriale

Il fattoriale è una definizione ricorsiva standard. Per i numeri interi $n \ge 0$, definiamo il fattoriale con

$$0! = 1$$

e, per $n \ge 1$,

$$n! = n(n-1)!$$

Qui, $0! = 1$ è il caso base, e $n! = n(n-1)!$ è il passo ricorsivo.

Per trovare $4!$, continua a ridurre finché non compare il caso base:

$$4! = 4 \cdot 3! = 4 \cdot 3 \cdot 2! = 4 \cdot 3 \cdot 2 \cdot 1! = 4 \cdot 3 \cdot 2 \cdot 1 \cdot 0!$$

Ora applica il caso base $0! = 1$:

$$4! = 4 \cdot 3 \cdot 2 \cdot 1 \cdot 1 = 24$$

Questo è il modello completo della ricorsione: riduci a un caso più piccolo, raggiungi il caso base, poi risali fino alla domanda iniziale.

Ricorsione vs. relazione di ricorrenza

La ricorsione è l’idea più generale. Una relazione di ricorrenza è una regola ricorsiva per una successione, in cui ogni termine dipende dai termini precedenti.

Per esempio, la successione di Fibonacci è data da una ricorrenza perché ogni termine è definito a partire dai precedenti. Anche il fattoriale è ricorsivo, ma di solito viene presentato come definizione ricorsiva di una funzione piuttosto che come ricorrenza di una successione.

Errori comuni nella ricorsione

Omettere il caso base

Se non c’è un caso base, la definizione non termina.

Usare un passo che non diventa più piccolo

Se il passo ricorsivo non si muove verso il caso base, il processo può continuare all’infinito oppure diventare indefinito per alcuni input.

Dimenticare la condizione della regola

Nell’esempio del fattoriale, la regola $n! = n(n-1)!$ si usa per $n \ge 1$. Questa condizione è importante. Senza di essa, potresti provare ad applicare la regola dove la definizione non era prevista.

Pensare che la ricorsione sia solo un’idea di programmazione

La ricorsione compare in matematica molto prima del codice. È un modo per definire funzioni, successioni e insiemi facendo riferimento a casi più piccoli. L’induzione viene poi spesso usata per dimostrare proprietà di queste definizioni ricorsive.

Quando la ricorsione è utile

La ricorsione è utile quando un problema si scompone naturalmente in versioni più piccole di sé stesso. La trovi nei fattoriali, nelle successioni di tipo Fibonacci, negli insiemi definiti ricorsivamente e in molti algoritmi.

È particolarmente utile quando il caso più piccolo ha la stessa struttura di quello originale. Se il caso più piccolo non è davvero lo stesso tipo di problema, allora la ricorsione di solito non è lo strumento giusto.

Un test rapido per una definizione ricorsiva corretta

Poniti due domande:

1. Ho un caso base?
2. Ogni passo ricorsivo si avvicina a esso?

Se una delle due risposte è no, la definizione va corretta.

Prova un problema simile

Definisci una successione con

$$a_1 = 2, \qquad a_n = a_{n-1} + 3 \quad \text{for } n \ge 2$$

Poi trova $a_2$, $a_3$ e $a_4$. È un modo rapido per esercitarti a riconoscere il caso base e il passo ricorsivo in un contesto nuovo.