Informatica I - la ricorsione

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 combinando 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!:

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
    if (n > 0) return n * factorial(n - 1); conoscere il fattoriale di n-1, cioè per
} risolvere un problema più semplice

• 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