Grandi poteri… grandi effetti collaterali

Posted by Santarelli Luca | Filed under Senza categoria

Tanto per fare quattro chiacchiere tra ricorsione e iterazione.Tecnicamente sono di parte. Amo la ricorsione e la uso dove serve. Programmare ricorsivamente da un grande potere allo sviluppatore. La possibilità di creare costrutti perfettamente logici con pochissimo codice.

Non oserei neanche immaginare ad una visita in profondità di un albero n-ario senza adottare la ricorsione.
Purtroppo anche questo sistema di sviluppo ha i suoi difetti. Come tutti immaginate programmare ricorsivamente implica un abbassamento delle prestazioni del programma (non sempre vero) e generalmente un maggiore impiego della memoria principale.

Basti pensare al codice assembly per una ricorsione
e vi accorgereste che è necessario ad ogni chiamata di funzione memorizzare parametri ed altri registri nello stack per poi ripristinarli quando il tutto verrà “svolto” a ritroso.

Chiamare una funzione, di per se implica memorizzazione di dati aggiuntivi.

ricorsione

ricorsione

Come tutte le cose comunque esistono casi in cui lo stesso codice in versione ricorsiva implichi un numero di operazioni e di parametri superiori a tal punto da perdere totalmente il vantaggio della linearità di esecuzione e credo che un esempio possa essere proprio attraversare in profondità un albero creato con liste concatenate.

Tanto perchè fuori piove… ho scritto un paio di funzioni nei due diversi stili e le ho comparate.

Le funzioni si occupano di calcolare la somma degli elementi di una matrice e restituirla. Purtroppo il benchmark è effettuato su tutto il programma e non solo sulla funzione ma dato che il programma differisce solo per quest’ultima vedrete le differenze.

Ricorsivo:

#include <stdio.h>

int matrix[500][500];

int somma(int i, int j)
{
if(i==499 && j==499) return matrix[i][j];

if(j==500) {++i; j=0;}

return matrix[i][j]+somma(i,j+1);
}

int main()
{
int i=0;
int j=0;

for(;i<500;i++)
for(j=0;j<500;j++)
matrix[i][j]=j;

printf(”somma=%dn”, somma(0,0));
return 0;
}

Iterativo:

#include <stdio.h>

int matrix[500][500];

int somma()
{
int sum=0;
int i=0;
int j=0;

for(;i<500;i++)
for(j=0;j<500;j++)
sum+=matrix[i][j];

return sum;
}

int main()
{
int i=0;
int j=0;

for(;i<500;i++)
for(j=0;j<500;j++)
matrix[i][j]=j;

printf(”somma=%dn”, somma());
return 0;
}

La cosa interessante della ricorsione è che in media la lunghezza della funzione è molto simile a quella che ho scritto per moltissimi algoritmi.

C’è una condizione di termine ricorsione all’inizio, eventuale codice intermedio e la chiamata ricorsiva che effettua al suo interno l’operazione da restituire.

Dal lato iterativo il programma invece può crescere moltissimo a seconda dell’algoritmo da implementare.

Una volta compilati i seguenti codici sorgente li ho eseguiti ed ecco i risultati

bash-3.1$ time ./ricorsivo
somma=62375000

real    0m0.027s
user    0m0.012s
sys     0m0.012s

bash-3.1$ time ./iterativo
somma=62375000

real    0m0.006s
user    0m0.004s
sys     0m0.000s

I test sono stati ripetuti diverse volte e parlano chiaro di quanto le chiamate ricorsive su un esempio semplice come questo pesino parecchio.

Lato memoria occupata invece la situazione è simile.

bash-3.1$ du -b ricorsivo
6641    ricorsivo
bash-3.1$ du -b iterativo
6577    iterativo

Grandi poteri… grandi effetti collaterali dunque (per storpiare una famosa frase).

Perchè dunque utilizzare la ricorsione?

Piccolo esempio… prendo in prestito un codice della Melideo a titolo di esempio

La professoressa Melideo definiva in questo modo una visita in-order di un albero binario

Metodo iterativo:

void inorder(ptree t, void *res, void visita(ptree,void *)){
stkElemType p;
stack stk=initStack( );

if (isEmptyBtree(t)) return;
/* inserisce radice nello stack */
push(stk, ptrStkElem(t));
while (!isEmptyStack(stk)) {
ptree t2;
p=pop(stk);
t2=p->ptrNodo;
if (p->flag==’1′) visita(t2, res);
else if (isEmptyBtree(left(t2))) {
visita(t2, res);
if (!isEmptyBtree(right(t2))) push(stk, ptrStkElem(right(t2)));
} else {
p->flag=’1′;
if (!isEmptyBtree(right(t2))) push(stk, ptrStkElem(right(t2)));
push(stk, p);
push(stk, ptrStkElem(left(t2)));
}
}
freeStack(stk);
}

Metodo ricorsivo:

void Rinorder(ptree t, void *res, void visita(ptree,void *)){
     if (isEmptyBtree(t)) return;
     Rinorder(left(t), res, visita);
     visita(t, res);
     Rinorder(right(t), res, visita);
}

Come avrete notato, non solo il codice iterativo è ben poco leggibile, lungo  e tedioso dal punto di vista della possibilità di commettere errori ma richiede anche la struttura dati stack aggiuntiva per mantenere traccia dell’esecuzione.

Il codice completo lo potete trovare sulla sua pagina web

http://www.di.univaq.it/melideo/lezioni.html

Viva la ricorsione dunque… ma usata quando serve!

pdf

No related posts.

Articoli correlati elaborati dal plugin Yet Another Related Posts.

Scritto da Santarelli Luca lunedì, 15th dicembre , 2008 23:26 Letture:

    « Collegarsi ad internet tramite gateway su Windows XP  |  Personalizzare il TAG Blockquote Con i CSS »

    One Response to “Grandi poteri… grandi effetti collaterali”

    1. Nicola Says:
      gennaio 22nd, 2010 at 16:53

      Bell’articolo, non c’è che dire…
      Sui grandi effetti collaterali putroppo me ne sto accorgendo a mie spese: sto facendo implementazione e testing di algoritmi di ordinamento e quando questi sono ricorsivi (Randomized-Select ad es) posso testare solo vettori fino a 60′000 elementi circa, al di sopra l’eseguibile derivato dalla compilazione del cpp crasha.
      Credi sia questo il motivo (stack overflow dovuto all’impossibilità di salvare ulteriori dati di ritorno)? Se si, come posso calcolare il massimo livello di ricorsione?
      CIAO!

    Leave a Reply