PROGRAMMIAMO
C++ - Funzioni ricorsive
Definizione di ricorsione

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:

double eleva(double base, int esp)
{
double ris;

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:

double eleva(double base, int esp)
{
double ris;

if (esp==0)
return 1;

ris = base * eleva(base, esp-1);

return ris;
}

Altre funzioni ricorsive

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:

int fatt (int n)
{
if (n==1)
return 1;

return n*fatt(n-1);
}

Funzione per la ricerca della massima cifra in un numero intero

int trovamax (int num)
{
int cifra, max;

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

int mcd (int x, int y)
{
if (y==0)
return x;

return mcd(y,x%y);
}

Funzione per invertire le cifre di un numero intero:

int reverse (int num)
{
static int rev_num = 0;
static int base_pos = 1;

if (num==0)
return 0;

reverse(num/10);

rev_num += (num%10)*base_pos;
base_pos *= 10;

return rev_num;
}

  

 

link precedente - successiva

Sito realizzato in base al template offerto da

http://www.graphixmania.it