Informatica I - la ricorsione

Ricorsione

Tecnica di programmazione che sfrutta l'idea di suddividere un problema da risolvere in sottoproblemi simili a quello originale, ma più semplici.

COME FUNZIONA UNA INVOCAZIONE RICORSIVA DI UN METODO

In una invocazione ricorsiva, la JVM:

• sospende l'esecuzione del metodo invocante
• esegue il metodo invocato fino alla sua terminazione
• riprende l'esecuzione del metodo invocante dal punto in cui era stata sospesa

STRUTTURA DI UN METODO RICORSIVO

CASO BASE: Si definisce come risolvere direttamente dei problemi analoghi a quello di partenza, ma di dimensione "sufficientemente piccola".

PASSO RICORSIVO: Si definisce come ottenere la soluzione del problema di partenza combinandola con la soluzione di uno o più sottoproblemi di "dimensione inferiore".

ESEMPIO: La funzione fattoriale

La funzione fattoriale, molto usata nel calcolo combinatorio, è così definita:

Per ogni n intero positivo, il fattoriale di n è il...

prodotto dei primi n numeri interi positivi.

Invochiamo factorial(3) per calcolare 3!:

ESEMPIO:

public static int factorial(int n){
    if (n < 0) throw new IllegalArgumentException(); // CASO BASE
    if (n == 0) return 1; // si invoca la funzione ricorsivamente per conoscere il fattoriale di n-1, cioè per risolvere un problema più semplice
    if (n > 0) return n * factorial(n - 1);
}

factorial(3) invoca factorial(2)
factorial(2) invoca factorial(1)
factorial(1) invoca factorial(0)
factorial(0) restituisce 1
factorial(1) restituisce 1
factorial(2) restituisce 2
factorial(3) restituisce 6

Si crea quindi una pila di metodi "in attesa", che si allunga e che poi si accorcia fino ad estinguersi.

RICORSIONE INFINITA

Quanto detto ci suggerisce che non tutti i metodi ricorsivi realizzano algoritmi:
- se manca il caso base, il metodo ricorsivo continua ad invocare se stesso all'infinito
- se il problema non viene semplificato ad ogni invocazione ricorsiva, il metodo ricorsivo

continua ad invocare se stesso all'infinito