Una breve introduzione
Nel numero 113 della rivista Hacker Journal è stata presentata la tecnica della ricorsione:
nell'articolo in questione si utilizzava tale tecnica per risolvere il problema di programmazione detto “le torri di Hanoi”.
Con questa breve introduzione vorrei spiegare la ricorsione in una maniera più semplice, in modo da poter introdurre il maggior numero di persone.
Innanzitutto vorrei fare un esempio più semplice di ricorsione: un approccio accademico all'argomento è quello del calcolo del fattoriale di un numero.
Per calcolare il fattoriale si può scrivere una funzione del tipo:
int Fact( int val )
{
int i;
int res = 1;
for( i = 1; i <= val; i ++ )
res = res * i;
return res;
}
Il
funzionamento è estremamente semplice: il fattoriale di n è dato dal
risultato della moltiplicazione di tutti i valori interi da 1 a n.
Fact( n ) = 1 * 2 * 3 * ... * n
Lo stesso calcolo può essere fatto con una funzione ricorsiva, ovvero una funzione che al suo interno richiama se stessa.
Prima di vedere il codice riconsideriamo il calcolo del fattoriale come:
Fact(n) = n * (n–1) * (n-2) * ... * 1
A questo punto si può anche arrivare a dire:
Fact(n) = n * Fact(n–1)
Quindi alla seguente funzione:
int FactRic( int val )
{
if( val == 1 )
return 1;
else
return val * FactRic( val - 1 );
}
Il
codice risulta molto più 'elegante'. Per capirne il meccanismo possiamo
modificare la funzione per stampare a video qualche messaggio (il debug
'tradizionale', ovvero con il settaggio di breakpoint all'interno del
codice, nel caso di funzioni ricorsive non è sempre così semplice,
spesso è conveniente 'tracciare' le chiamate per capirne il
funzionamento).
int FactRic( int val )
{
int res;
printf( "FactRic(%d)n", val );
if( val == 1 )
{
printf( "return res=1n" );
return 1;
}
else
{
res = val * FactRic( val - 1 );
printf( "return res=%dn", res );
return res;
}
}
Richiamando ad esempio FactRic(4) otterremo il seguente risultato:
FactRic(4)
FactRic(3)
FactRic(2)
FactRic(1)
return res=1
return res=2
return res=6
return res=24
L'algoritmo
non calcolerà niente finchè non si entra in FactRic(n) con n=1; a
questo punto si uscirà dalla sequenza di chiamate moltiplicando di
volta in volta per un valore progressivo.
Se ci fossero ancora dubbi sul funzionamento consiglio comunque di provare ad eseguire passo a passo il codice con un debugger.
Tuttavia
questo è solo un esempio di ricorsione. Di certo nel dover calcolare il
fattoriale di un valore sarà preferibile utilizzare la routine non
ricorsiva, questo perchè i punti a sfavore della ricorsione sono
diversi: un pesante utilizzo dello stack (ogni chiamata a funzione usa
lo stack e tante chiamate possono portare ad esaurirne lo spazio) e
generalmente una minore velocità di esecuzione.
La ricorsione
può risultare utile per particolari tipi di algoritmi, la cui
traduzione in maniera iterativa potrebbe risultare complicata.
Un
buon esempio può essere la soluzione di schemi di Sudoku... e questo sarà sicuramente argomento di un prossimo articolo!!!
Copyright © by Sebastien Costa All Right Reserved.
