Ricordiamo brevemente la definizione di un algoritmo ricorsivo: è un algoritmo che è definito in termini di se stesso; è composto da un passo induttivo e da una condizione di chiusura.
Il passo induttivo definisce una funzione per un generico valore di una variabile n in termini della funzione di n-1. La condizione di chiusura definisce la funzione in n=0. E allora chiamando la funzione per un valore si possono calcolare in cascata tutti i risultati intermedi fino a n=0.
Un tipico algoritmo che è facilmente espresso in forma ricorsiva è la definizione di fattoriale:
integer f=fatt(n)
{
if n==0
f=1; /* condizione di chiusura */
else
f=n*fatt(n-1); /* passo induttivo */
end
return(f);
}
Sviluppando passo per passo ad esempio il fattoriale di 5 si ha:
fatt(5) =5*fatt(4)
=5*4*fatt(3)
=5*4*3*fatt(2)
=5*4*3*2*fatt(1)
=5*4*3*2*1*fatt(0)
=5*4*3*2*1*1=5!
La ricorsione pur permettendo codici molto compatti ed eleganti è di solito poco efficiente perché ogni funzione chiamata alloca memoria nello stack. Quindi è possibile, se non consigliabile, trasformare l’algoritmo in forma iterativa. Nel caso del fattoriale si ha
integer f=fattoriale(n)
{
f=1;
for i=1:n
f=f*i;
end
return(f)
}
Vale anche il viceversa. Prendiamo un qualunque algoritmo iterativo:
for i=1:N
{
blocco istruzioni;
}
end
posso definire una funzione ricorsiva
void ciclo(integer i)
{
if i>N
/* condizione di uscita */
return;
else
blocco istruzioni;
ciclo(i+1);
end
}
Naturalmente a seconda del ciclo dovrò scegliere opportunamente la condizione di chiusura.