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