Tale tecnica risulta particolarmente utile per eseguire dei compiti ripetitivi su di un set di variabili in input. L'algoritmo richiama se stesso generando una sequenza di chiamate che ha termine al verificarsi di una condizione particolare che viene chiamata condizione di terminazione, che in genere si ha con particolari valori di input.
La tecnica ricorsiva permette di scrivere algoritmi eleganti e sintetici per molti tipi di problemi comuni, anche se non sempre le soluzioni ricorsive sono le più efficienti. Questo è dovuto al fatto che comunemente la ricorsione viene implementata utilizzando le funzioni, e che l'invocazione di una funzione ha un costo rilevante, e questo rende più efficienti gli algoritmi iterativi.
In alcuni casi la ricorsione è altrettanto efficiente di un ciclo iterativo: linguaggi dei paradigmi funzionali o logici tipicamente non hanno il concetto di ciclo ed usano la ricorsione ottimizzando automaticamente.
0! = 1;
n! = 1 * 2 * 3 * ...... * n-1 * n; per n > 0.
Rielaborando:
n! = (1 * 2 * 3 * ...... * n-1) * n;
n! = (n-1)! * n;
ESEMPIO DI CODICE:
int FATTiterativo (int n)
{
int fatt = 1;
while (1 <= n)
{
fatt = fatt * n;
n --;
}
return fatt;
}
ECCO LE VARIE TIPOLOGIE DI RICORSIONE:
Esistono vari tipi di ricorsione. Si parla di mutua ricorsione quando nell'algoritmo una funzione ne richiama un'altra che a sua volta richiama la prima, altrimenti si parla di ricorsione diretta.
Altra distinzione è quella fra ricorsione lineare, che si ha quando vi è solo una chiamata ricorsiva all'interno della funzione, e non lineare nel caso in cui le chiamate ricorsive siano più di una.
La distinzione più importante ai fini pratici si ha fra ricorsione di coda (tail recursion) e ricorsione non di coda. Si parla di ricorsione di coda quando la chiamata ricorsiva è l'ultima istruzione eseguita nella funzione. Questo tipo di algoritmo ricorsivo è possibile trasformarlo semplicemente in una versione iterativa, che di solito è più efficiente, in quanto non occorre mantenere lo stato della funzione una volta calcolata come è stato fatto nell'esempio precedente. Se l'algoritmo non è ricorsivo di coda, per trasformarlo in una versione iterativa occorre utilizzare un meccanismo di mantenimento dello stato analogo a quello che è utilizzato implicitamente nelle chiamate di funzione.
Ecco qui un video che ci aiuterà a capire: link
Qui si può trovare un PDF sulla ricorsione: link
