Le funzioni ricorsive
Una delle prime applicazioni del concetto di ricorsione risale al matematico Giuseppe Peano, quando definì l'insieme dei numeri naturali come:
- 0 è un numero Naturale
- se n è un nunero naturale allora anche successivo(n) = n + 1 è un numero naturale
Una funzione si definisce ricorsiva quando fa riferimento a (o utilizza) sé stessa per assolvere al compito per cui è stata realizzata.
Utilizzando altre parole, una funzione è ricorsiva se nella sua implementazione compare una chiamata/invocazione a sé stessa.
Da tale definizione deriva che il rischio principale di una funzione ricorsiva scritta male è la non terminazione del programma (loop infinito).
La ricorsione può essere di due tipi:
- diretta, quando una funzione è richiamata all'interno della sua stessa implementazione
- indiretta, quando una funzione è richiamata nell'implementazione di una seconda funzione richiamata dalla prima
public static <tipo> funzioneRicorsiva(<tipo1> parametro1, ... <tipoN> parametroN) {
// sequenza di istruzioni
funzioneRicorsiva(...); // chiamata ricorsiva diretta
}Nel frammento di codice che segue, troviamo invece un esempio di ricorsione indiretta:
public static <tipo> funzioneA(<tipo1> parametro1, ... <tipoN> parametroN) {
// sequenza di istruzioni
funzioneB(...);
}
public static <tipo> funzioneB(<tipo1> parametro1, ... <tipoN> parametroN) {
// sequenza di istruzioni
funzioneA(...); // chiamata ricorsiva indiretta
}L'implementazione di una funzione ricorsiva deve contenere i seguenti elementi fondamentali:
- la condizione di terminazione con il caso base (o semplice o noto)
- il passo di avvicinamento (alla terminazione)
- la chiamata ricorsiva
Il prodotto dei primi n numeri interi p(n) può essere schematizzato come segue:
$$ \underbrace{1 * 2 * 3 * \cdots * (n-2) * (n-1)}_{\text p(n-1)} * n $$
ossia il prodotto dei primi n-1 numeri interi moltiplicato per n, cioé p(n-1) * nA sua volta, anche il prodotto dei primi n-1 numeri interi, utilizzando la stessa tecnica, si può schematizzare come segue:
$$ \underbrace{1 * 2 * 3 * ... * (n-2)}_{\text p(n-2)} * (n-1)$$
ossia il prodotto dei primi n-2 numeri interi moltiplicato per n-1, cioé p(n-2) * (n-1)Procedendo nello stesso modo possiamo arrivare a definire la funzione p(n) come segue:
$$ p(n) =
\begin{cases} 1 & \text{se n = 1 (caso base)}
\\
\\ p(n-1) * n & \text{altrimenti (passo di avvicinamento}
\\ & \text{e chiamata ricorsiva)}
\end{cases} $$
Possiamo notare come nella definizione della funzione p(n) si faccia uso della stessa
funzione per calcolare p(n-1).Questa costituisce la chiamata ricorsiva, mentre il valore n-1 a cui è applicata costituisce il passo di avvicinamento.
Sottraendo uno ad ogni chiamata ricorsiva, prima o poi si arriverà al caso base, di cui conosciamo già il risultato, che pone fine alla ricorsione.
Ogni volta che ci troviamo di fronte ad una definizione di funzione come la p(n) vista sopra, possiamo realizzare una implementazione ricorsiva in Java, come mostrato nel codice seguente:
public static int prodottoPrimiN(int n) {
if (n == 1) {
return 1; // caso base
} else {
return prodottoPrimiN(n-1) * n; // passo di avvicinamento
// e chiamata ricorsiva
}
}Confrontando l'implementazione in Java con la definizione della funzione ricorsiva a cui si è giunti sopra, si può vedere come, data la definizione della funzione, l'implementazione in un linguaggio di programmazione consiste in una semplice operazione di traduzione della definizione nelle corrispondenti istruzioni del linguaggio di programmazione.
Nota:
Ogni chiamata ricorsiva alloca spazio in un'area della memoria principale chiamata stack.
Essendo quest'area di dimensioni limitate, una conseguenza di una funzione ricorsiva ben scritta e terminante per determinati valori di input, ma con un numero di chiamate ricorsive eccessivo per valori di input di dimensioni maggiori, potrebbe essere l'esaurimento dello spazio necessario nello stack.
Questa situazione genererebbe un errore di esecuzione che solitamente è indicato con il termine stack overflow.
Ogni chiamata ricorsiva alloca spazio in un'area della memoria principale chiamata stack.
Essendo quest'area di dimensioni limitate, una conseguenza di una funzione ricorsiva ben scritta e terminante per determinati valori di input, ma con un numero di chiamate ricorsive eccessivo per valori di input di dimensioni maggiori, potrebbe essere l'esaurimento dello spazio necessario nello stack.
Questa situazione genererebbe un errore di esecuzione che solitamente è indicato con il termine stack overflow.