Algoritmi ricorsivi - terza parte

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

Il calcolatore ha bisogno di una certa quantità di memoria di tipo stack per gestire ciascuna chiamata ricorsiva. Dopo un certo numero di chiamate la memoria disponibile per questo scopo puo’ esaurirsi, allora il programma termina automaticamente segnalando un errore di stack.

Algoritmi ricorsivi - seconda parte

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)

==================================================

La fine 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!).

Algoritmi ricorsivi in Java - Prima parte

Molti algoritmi presentano una struttura ricorsiva e, per risolvere un determinato problema, tali algoritmi richiamano se stessi più volte, 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 del numero n:
n! = 1 * 2 * 3 * ... * n
Cioè il fattoriale di 7 che si indica con 7! = 7*6*5*4*3*2*1
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;
}
} // fine metodo factorial