La ricorsione e' un grosso problema della programmazione!
Non perche' sia difficile, ma perche' sembra una magia.
In analisi un problema si dice ricorsivo quando e' definito
in istanze di se stosso.
Cio' vuol dire, ad esempio, che la funzione fattoriale e'
ricorsiva perche' e' definita:
{ 1 if n = 0;
n! = {
{ n * (n - 1)! else;
Questo pone n! in termini di (n-1)!, cioe' definisce
n! in funzione della sua istanza minore.
E' chiaro che un problema ricorsivo puo' essere
risolto in modo non ricorsivo, ad esempio con una
serie di prodotti:
int Fact(int n)
{
int product = 1, i;
for (i = 1; i <= n; i++) {
product *= i; /* Esegue le moltiplicazioni */
}
return (product);
}
E' una soluzione standard al problema.
Ma non e' la sola. vediamo come risolvere il
problema con la ricorsione:
int Fact(int n) /* La dichiarazione e' la stessa */
{
if (!n) {
return (1);
} else {
return (n * Fact(n - 1));
}
}
Semplicemente la funzione Fact(n)
valuta il caso limite n == 0 (!n) e, se
e' vero, cioe' se n e' zero, restituisce 1.
Se n > 0 restituisce n * il risultato di Fact(n - 1).
Si deve notare ce ora la riga "congela" l'esecuzione del
programma fino a quando n diventa zero, a quel punto
l'ultima funzione chiamata restituisce 1 e via fino al valore di n:
n = 3 -> (n * (n -1) * (n - 2) * (n - 3))
(3 * 2 * 1 * 1) = 6
Per capire meglio si dovrebbe disegnare lo stack frame delle
chiamate di funzioni del programma e vedere in che ordine sono
eseguite. Essendo uno stack, l'ultima funzione entrata sara' la prima a
restituire
un valore, in questo caso 1.
*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/*/**/*/*/*/*/
Proposta: Perche' non iniziamo una serie di
lezioni sulla programmazione in C (o altri linguaggi!) e sui
comandi Linux? Chi conosce qualcosa la dica, e chi ha da aggiungere
lo faccia liberamente! E senza paura di dire cose che altri sanno,
perche' qualcuno sa sempre meno e qualcuno sempre di piu' di altri!
se volete conoscere altri dettagli sulla ricorsione ditelo che mando una
nuova
Mail con altri esempi ( o fatelo voi se sapete di piu' di me che io devo
imparare ;-) )
CIAO!!!
