Metodi e Ricorsione in Java

Concetti Chiave

In Java, i metodi possono essere definiti per eseguire operazioni specifiche e possono accettare parametri per personalizzare il loro comportamento.
I metodi possono restituire valori, che possono essere di qualsiasi tipo, inclusi oggetti.
La ricorsione è una tecnica in cui un metodo chiama se stesso per risolvere un problema, spesso utilizzata per semplificare algoritmi complessi.
I metodi ricorsivi devono includere una condizione di terminazione per evitare loop infiniti e potenziali errori di overflow dello stack.

Ricorsione

Java supporta la ricorsione. La ricorsione è il processo di definizione di qualcosa in termini di se stesso. Per quanto riguarda la programmazione in Java, la ricorsione è la funzionalità che permette a un metodo di chiamare se stesso. Un metodo che si chiama da solo si dice che sia ricorsivo.

L'esempio classico di ricorsione è il calcolo del fattoriale di un numero. Il fattoriale di un numero $N$ è il prodotto di tutti i numeri interi compresi tra 1 e $N$ . Per esempio, 3 fattoriale è $1 \cdot 2 \cdot 3$ , ovvero 6.

Ecco come si può calcolare un fattoriale usando un metodo ricorsivo:

// Un semplice esempio di ricorsione.
class Fattoriale {
    // questo è un metodo ricorsivo
    int fatt(int n) {
        int risultato;

        if(n==1) return 1;
        risultato = fatt(n-1) * n;
        return risultato;
    }
}

class Ricorsione {
    public static void main(String[] args) {
        Fattoriale f = new Fattoriale();

        System.out.println("Fattoriale di 3 è " + f.fatt(3));
        System.out.println("Fattoriale di 4 è " + f.fatt(4));
        System.out.println("Fattoriale di 5 è " + f.fatt(5));
    }
}

L'output di questo programma è il seguente:

Fattoriale di 3 è 6
Fattoriale di 4 è 24
Fattoriale di 5 è 120

Se non si ha familiarità con i metodi ricorsivi, allora il funzionamento di fatt() può sembrare un po' confuso. Ecco come funziona. Quando fatt() viene chiamato con un argomento di 1, la funzione restituisce 1; altrimenti, restituisce il prodotto di fatt(n-1)*n. Per valutare questa espressione, fatt() viene chiamato con n-1. Questo processo si ripete finché $n$ è uguale a 1 e le chiamate al metodo iniziano a restituire valori.

Per comprendere meglio come funziona il metodo fatt(), si può esaminare un breve esempio. Quando si calcola il fattoriale di 3, la prima chiamata a fatt() causerà una seconda chiamata con un argomento di 2. Questa invocazione causerà che fatt() venga chiamato una terza volta con un argomento di 1. Questa chiamata restituirà 1, che sarà poi moltiplicato per 2 (il valore di $n$ nella seconda invocazione). Questo risultato (che è 2) viene poi restituito all'invocazione originale di fatt() e moltiplicato per 3 (il valore originale di $n$ ). Questo produce il risultato 6. Può essere interessante inserire istruzioni println() all'interno di fatt(), per vedere a quale livello ogni chiamata si trova e quali sono i risultati intermedi.

Quando un metodo chiama se stesso, vengono allocate nuove variabili locali e parametri nello stack, e il codice del metodo viene eseguito con queste nuove variabili sin dall'inizio. Quando la chiamata ricorsiva termina, le vecchie variabili locali e i parametri vengono rimossi dallo stack, e l'esecuzione riprende dal punto della chiamata all'interno del metodo. I metodi ricorsivi possono essere detti “a telescopio” in entrata e in uscita.

Le versioni ricorsive di molte routine possono risultare un po' più lente rispetto all'equivalente iterativo a causa del sovraccarico aggiuntivo delle chiamate ai metodi. Un gran numero di chiamate ricorsive a un metodo può causare un overflow dello stack. Poiché la memoria per i parametri e le variabili locali si trova nello stack e ogni nuova chiamata crea una nuova copia di queste variabili, è possibile che lo stack venga esaurito. In tal caso, il sistema di esecuzione Java genererà un'eccezione. Tuttavia, questo in genere non è un problema a meno che una routine ricorsiva non vada fuori controllo.

Il principale vantaggio dei metodi ricorsivi è che possono essere usati per creare versioni più chiare e semplici di diversi algoritmi rispetto ai loro equivalenti iterativi. Per esempio, l'algoritmo di ordinamento QuickSort è abbastanza difficile da implementare in modo iterativo. Inoltre, alcuni tipi di algoritmi legati all'intelligenza artificiale sono più facilmente implementabili usando soluzioni ricorsive.

Nota

Errore comune nella ricorsione

Quando si scrivono metodi ricorsivi, è necessario includere un'istruzione if per forzare il metodo a restituire senza eseguire ulteriori chiamate ricorsive. Se non si fa ciò, una volta che il metodo è chiamato, non terminerà mai. Questo è un errore molto comune nella ricorsione. Usare istruzioni println() durante lo sviluppo aiuta a vedere cosa sta accadendo ed interrompere l'esecuzione nel caso si identifichi un errore.

Ecco un altro esempio di ricorsione. Il metodo ricorsivo stampaArray() stampa i primi $i$ elementi dell'array valori.

// Un altro esempio che usa la ricorsione.
class TestRic {
    int[] valori;

    TestRic(int i) {
        valori = new int[i];
    }

    // mostra l'array -- ricorsivamente
    void stampaArray(int i) {
        if(i==0) return;
        else stampaArray(i-1);
        System.out.println("[" + (i-1) + "] " + valori[i-1]);
    }
}

class Ricorsione2 {
    public static void main(String[] args) {
        TestRic ob = new TestRic(10);
        int i;

        for(i=0; i<10; i++) ob.valori[i] = i;

        ob.stampaArray(10);
    }
}

Questo programma genera il seguente output:

[0] 0
[1] 1
[2] 2
[3] 3
[4] 4
[5] 5
[6] 6
[7] 7
[8] 8
[9] 9