Algoritmi ricorsivi

Molti algoritmi presentano una struttura ricorsiva: per risolvere un determinato problema, tali algoritmi richiamano se stessi per gestire sottoproblemi analoghi a quello di partenza.

Gli algoritmi ricorsivi generalmente sono organizzati nel seguente modo:

Il problema da risolvere è suddiviso in sottoproblemi simili a quello originale, ma di dimensione inferiore.

I sottoproblemi sono risolti ricorsivamente. Se la dimensione dei sottoproblemi è sufficientemente piccola, essi sono invece risolti direttamente.

Le soluzioni dei sottoproblemi sono combinate per ottenere la soluzione del problema di partenza.

Un esempio: la funzione fattoriale

Immaginiamo di dover calcolare il fattoriale di un numero n:

n! = 1 * 2 * 3 * ... * n

Per convenzione 0! = 1. Inoltre, il fattoriale non è definito per i numeri negativi.

Come possiamo scrivere un metodo che calcoli la funzione fattoriale? Osserviamo che

n! = 1*2*...*(n-1)*n = (n-1)! * n

Quindi, un algoritmo per calcolare il fattoriale di n si può descrivere nel seguente modo:

per calcolare il fattoriale di n, si calcola il fattoriale di n-1 e lo si moltiplica per n.

Possiamo allora implementare il seguente metodo:

public static int factorial(int n)
{
    if (n == 0)
        return 1; // calcolo diretto di 0!
    else
    { int result = n * factorial(n - 1);
        return result;
    }
}

Un programma completo per il calcolo del fattoriale: Fac.java

Chiamate ricorsive di un metodo

In Java, un metodo può chiamare se stesso, purché la chiamata utilizzi un valore più semplice. Il meccanismo per cui un metodo chiama se stesso per un numero ripetuto di volte si chiama ricorsione.

Esaminiamo il calcolo di 4! con il metodo factorial.

Per calcolare il fattoriale di 4, il metodo factorial(4) chiede di calcolare 4 * factorial(3). Non sapendo il risultato, si sospende temporaneamente questo calcolo e si intraprende il calcolo di factorial(3).
Per calcolare factorial(3) dobbiamo calcolare 3 * factorial(2). Non sapendo nemmeno questo risultato, si tralascia temporaneamente anche questo problema e si risolve factorial(2).
Per calcolare factorial(2) dobbiamo prima calcolare factorial(1).
Per calcolare factorial(1) dobbiamo prima calcolare factorial(0).
Il metodo factorial(0) restituisce 1, e a questo punto possiamo completare i calcoli lasciati in sospeso.

Ecco la successione delle chiamate e dei valori restituiti:

factorial(4) chiama factorial(3)

factorial(3) chiama factorial(2)

factorial(2) chiama factorial(1)

factorial(1) chiama factorial(0)

factorial(0) restituisce 1

factorial(1) restituisce 1 (1*1)

factorial(2) restituisce 2 (2*1)

factorial(3) restituisce 6 (3*2)

factorial(4) restituisce 24 (4*6)

Chiusura della ricorsione

Esistono due requisiti chiave per assicurarsi che la ricorsione riesca:

Ciascuna chiamata ricorsiva deve semplificare in qualche modo l'elaborazione.
(Nel metodo factorial le chiamate ricorsive si fanno su parametri più piccoli.)
Il metodo deve prevedere una clausola di chiusura per assicurarsi che le chiamate successive del metodo abbiano termine, ovvero devono esistere casi speciali per risolvere le elaborazioni più semplici.
(Nel metodo factorial, il valore del parametro giunge inevitabilmente a zero, ed esiste un caso speciale per risolvere 0!).

Un errore comune di programmazione è una ricorsione infinita: un metodo che chiama se stesso infinite volte. Ciò si verifica perché i valori del parametro non si semplificano, o perché manca la clausola di chiusura per terminare.

Il calcolatore ha bisogno di una certa quantità di memoria per gestire ciascuna chiamata ricorsiva. Dopo un certo numero di chiamate la memoria disponibile per questo scopo si esaurisce e il programma termina automaticamente segnalando un errore di stack.

Un altro esempio

Un metodo ricorsivo per determinare l'elemento minimo in un array di numeri interi:

public static int minRic(int a [ ], int from, int to)
{
if (from == to)
return a[from]; int mid = (from + to)/2; // cerchiamo ricorsivamente il minimo // nella prima e nella seconda metà dell'array: int min1 = minRic(a, from, mid); int min2 = minRic(a, mid+1, to); if (min1 <= min2) return min1; else return min2; }

Un programma completo che usa il metodo minRic: ArrayMinRic.java