Si dice ricorsione una tecnica di programmazione nella quale una funzione chiama se stessa. Per capire meglio di cosa si tratta, partiamo da un problema già risolto in passato: il calcolo dell'elevamento a potenza con esponente intero.
Non è difficile vedere che in generale:
Tradotto in termini di funzioni, se eleva è la nostra funzione per il calcolo dell'elevamento a potenza abbiamo:
y = eleva(x,n) = x * eleva(x, n-1);
L'istruzione precedente ci dice che per calcolare l'elevamento a potenza di x alla n, basta saper calcolare l'elevamento a potenza di x elevato a n-1. Naturalmente il ragionamento può essere esteso: per calcolare x alla n-1 basta poter calcolare x alla n-2 eccetera eccetera. Questa sorprendente osservazione ci consente di scrivere una funzione eleva un po' strana, come nell'esempio seguente:
ris = base * eleva(base, esp-1);
return ris;
}
La funzione è abbastanza sorprendente perché, se la osserviamo attentamente, sembra in effetti non svolgere nessun calcolo.
In effetti la versione precedente di eleva non funziona, in quanto genera una sequenza infinita di chiamate che non termina mai (in realtà viene terminata da un errore di esecuzione del programma). Per rendere utilizzabile la nostra funzione ricorsiva, dobbiamo prevedere un caso in cui la funzione termina restituendo un risultato. Questo caso è il primo della serie: nel nostro esempio corrisponde alla situazione in cui l'esponente esp è diventato zero. In questo caso la funzione può tornare il valore 1 e questo pone termine alla ricorsione.
La versione funzionante (solo con esponenti positivi!) è dunque la seguente:
if (esp==0)
return 1;
ris = base * eleva(base, esp-1);
return ris;
}
Ci sono parecchi problemi che possono essere elegantemente risolti usando le funzioni ricorsive. Vediamo ora rapidamente una serie di esempi.
Funzione per il calcolo del fattoriale:
return n*fatt(n-1);
}
Funzione per la ricerca della massima cifra in un numero intero
if (num<10)
return num;
cifra = num%10;
num = num/10;
max = trovamax(num);
if (cifra>max)
return cifra;
return max;
}
Funzione per il calcolo del massimo comune divisore
return mcd(y,x%y);
}
Funzione per invertire le cifre di un numero intero:
if (num==0)
return 0;
reverse(num/10);
rev_num += (num%10)*base_pos;
base_pos *= 10;
return rev_num;
}
Sito realizzato in base al template offerto da
http://www.graphixmania.it