[OT] Programmare ricorsivamente

[padrino01]

grassie a tutti per i vari consigli ne sta venendo fuori una discussione interessante...

[iiba88]

spero pero che tu stia capendo qulcosa pero sulla ricorsione e non solo chicchiere...

[XWolverineX]

Originariamente inviato da iiba88
allora se vuoi tiposso spiegare che cos'è un albero o che cos'è una funzione perche mi sembra che questo concetto non ti è molto chiaro o sbaglio???

Ci stiamo atteggiando un pò troppo ora.
So benissimo cos'è una funzione e cos'è un albero, sto cercando di buttarmi in un discorso che non conosco completamente (non che non conosco proprio) con una certa modestia, per evitare di fare figuracce con frasi che potrebbero essere assurde.

Ma da qui a cominciare anche a sfottere con "Ti posso spiegare cos'è una funzione",non ti pare di esagerare?

Comunque grazie per la definizione di funzione, mi hai davvero cambiato la vita.
:berto:

[iiba88]

Mi sa proprio che ti ci voleva perche dalle frasic he dici se non te la davo i ola definizione di funzione forse rimanevi con idee ben diverse, forse quella di albero non ti è ancora entrata in testa eee bhe pazienza quando la imparerai allora potrai iniziare a postare frasi senzate...

[alka]

Intervengo solamente per dire... caaaalma.

Si possono spiegare le cose senza alzare i toni, e lo stesso vale per la proposta di domande.

Ciao!

[iiba88]

alca non ti preoccupare stai tranquillo non stiamo alzando i toni e solo che noi ragazzi del mondo dell'informatica siamo tutti cosi crediamo di sapere e difendiamo le nostr idee io sono al primo... tutto ok cmq

[daniele_dll]

La discussione è decisamente interessante!

Personalmente (e sottolineo personalmente) e per esperienza personale, ho sempre preferito scrivere codice iterativo piuttosto che ricorsivo: per lo più per evitare di incorrere in problemi come stack overflow o per aumentare la performance (leggere l'esempio di sotto)

Ovviamente è solo un esempio però è una situazione che deve essere gestita correttamente altrimenti, potenzialmente (ma del resto come la maggioranza dei bug del codice), possono venir fuori exploit di vario genere.

Anche gli alberi mi ritrovo a gestirli tramite iterazione: per esempio attualmente sto costruendo la visualizzazione di una treeview contenente un elenco di categorie di clienti/fornitori. Il codice estrae prima il resultset dal database ordinandolo in base alla profondità, in modo da spostare quelle con minore profondità sopra, e poi cicla il resultset in modo che ciclando una sola volta tutti gli elementi li posso piazzare.
Una struttura del genere è più performante rispetto ad un sistema ricorsivo che non ha congnizione a priori della profondità (cosa che ho implementato a livello di database)

Ovviamente tutto dipende dalle situazioni specifiche, e le ottimizzazioni per la programmazione iterativa varia da situazione a situazione, però personalmente, ripeto, preferisco l'iterazione alla ricorsione.

Riagganciandomi al discorso di wolverine, facendo un esempio banale: se il vostro codice è arrivato ad una "profondità" di 50 chiamate (ovvero la funzione ha richiamato se stessa 50 volte per scendere di livello) il sistema dovrà effettuare 50 spostamenti di puntatori vari per tornare alla normale esecuzione, cosa che ovviamente non si ha con l'iterazione ... questo è, ad esempio, uno dei motivi per il quale la ricorsione è sconsigliata per la performace. O ancora ogni volta che viene richiamata la funzione il sistema deve allocare memoria apposita nello stack e altra memoria per mantenere le informazioni delle variabili presenti nelle varie funzioni ricorsive: a profondità 50 il sistema terrà ancora in memoria le variabili inizializzate ed impostate alla profondità 1 il che comporta, soprattutto se c'è un considerevole controllo sui dati, un consumo di memoria notevole!

Per esempio il codice postato da MItaly

long fattoriale(long numero)
{
    if(numero==1)
        return 1;
    else
        return numero*fattoriale(numero-1);
}

ad ogni chiamata comporterebbe l'allocazione di valore per la variabile numero che è passata come valore e non come puntatore

NOTA: ovviamente se mi ritrovo a dover scrivere 50 volte il codice che dovrei scrivere per la ricorsione giusto per evitare un ipotetico caso remoto estremamente difficile (se non surreale) ... evito e uso la ricorsione però se la complessità della struttura da ripercorrere non è elevata preferisco l'iterazione ... poi, a parte casi particolari, direi che dipende più dalle propie abitudini

[padrino01]

vi ringrazio a tutti perchè ho capito finalmente cos'è la ricorsione...un'ultima cosa: cos'è la ricorsione di coda?

[MItaly]

La mia opinione in merito:
certamente è vero che la versione iterativa di un algoritmo è più veloce ed efficiente (si evita di occupare inutilmente lo stack), d'altra parte quando le performance non sono essenziali o per illustrare il funzionamento concettuale di un algoritmo spesso la ricorsione può essere una soluzione. Infatti la trasformazione di un algoritmo ricorsivo (in molti casi più "naturale") in uno iterativo non è sempre un'operazione banale come nel caso della funzione fattoriale (che, come già detto, ho portato a titolo di esempio classico e semplice della ricorsione, non perché la ricorsione sia il metodo più efficiente per risolvere il problema). Un esempio che mi è capitato di recente è una funzione di floodfill: con la ricorsione la scrittura di una funzione floodfill è estremamente semplice, ma se l'area da riempire supera certe dimensioni è molto facile incorrere in uno stack overflow (senza contare che durante l'operazione di riempimento si spreca molta memoria); d'altra parte se l'algoritmo di floodfill non serve per grandi immagini, ma, ad esempio, per un programma tipo campo minato (dove l'area di lavoro difficilmente supererà le 500 caselle) è inutile perdere tempo ad implementare una incasinata versione non ricorsiva dell'algoritmo di floodfill, quella semplice ricorsiva va più che bene (nota a margine: alla fine comunque io ho usato un algoritmo senza ricorsione e più efficiente del comune floodfill "semplice" - nel mio programma mi posso ritrovare anche immagini molto grandi).
In sostanza, al solito bisogna valutare caso per caso cosa conviene fare, per evitare di perdere tempo con ottimizzazioni inutili: anch'io fino a poco tempo fa ero fissato con l'ottimizzazione ad ogni costo e in ogni posto, ma in effetti spesso è una gran perdita di tempo inutile. In effetti il processore passa in media l'80% del tempo sul 20% del codice: è in questo 20% che ha effettivamente senso cercare i colli di bottiglia ed ottimizzarli, nel resto del codice prima dell'ottimizzazione vengono altre priorità, come la chiarezza del codice e la manutenibilità.

[LeleFT]

La ricorsione di coda è un particolare tipo di ricorsione in cui il risultato dell'elaborazione lo si ha immediatamente all'ultima chiamata ricorsiva. Questo particolare caso di ricorsione viene comunemente trasformato in una iterazione.

Diversamente da quanto accade con la ricorsione pura in cui il risultato dell'elaborazione lo si ha solamente al ritorno dalla prima chiamata ricorsiva.

Esempio:

// PS: Funziona solo con i numeri naturali.
int isPari(int x) {
   if (x <= 1) {
      return (x == 0);
   } else {
      return isPari( x-2 );
   }
}

Il risultato dell'elaborazione della funzione precedente lo si avrebbe già all'ultima chiamata (che sarà isPari( 1 ) oppure isPari( 0 ). Essendo, però, una chiamata ricorsiva (di coda) il risultato dovrà pervenire dopo che tutte le chiamate sono ritornate. Esempio con x = 4:

isPari( 4 ); --> return isPari( 2 );
   isPari( 2 ); --> return isPari( 0 );
      isPari( 0 ); --> return true
   return true;
return true;

PS: Aggiungo una nota alla discussione... esistono linguaggi in cui l'iterazione non esiste e tutto viene fatto attraverso la ricorsione. Scheme (derivato da Lisp) e Prolog sono due esempi.

Ciao.