[C++] Trasformare una funzione ricorsiva in qualcos'altro?

[DomusP45]

Salve a tutti.

Qualcuno sa dirmi come posso trasformare una funzione ricorsiva in una funzione non ricorsiva?

Chiedo questa cosa perchè vorrei avere una funzione non ricorsiva che si occupi di scansionare un vector di elementi, multilivello.

Il codice attuale è questo:

void addraw(cubo temp)
{
//se non ci sono sottocubi
if (temp.lista_sottocubi.size() == 0)
{
if (temp.livello == LMAXI) {
double centro[3]={(temp.V[6].x)/2, (temp.V[6].y)/2,(temp.V[6].z)/2};
//salvataggio centro e lato
}
}
//se i sottocubi ci sono
else {
for (int i=0;i<(int)temp.lista_sottocubi.size();i++){
addraw(temp.lista_sottocubi[i]);
}
}
}

come si passa da una ricorsiva ad una ad esempio iterativa?

[cdimauro]

Risposta banale: usando uno stack per tenere traccia degli elementi intermedi che ti servono.

Poi magari possono esserci soluzioni migliori (più efficientii) in base all'algoritmo da implementare. Vedi la classica implementazione del fattoriale, ad esempio.

Comunque io preferisco nettamente l'eleganza tipica delle soluzioni ricorsive.

[DomusP45]

Risposta banale: usando uno stack per tenere traccia degli elementi intermedi che ti servono.

Poi magari possono esserci soluzioni migliori (più efficientii) in base all'algoritmo da implementare. Vedi la classica implementazione del fattoriale, ad esempio.

Comunque io preferisco nettamente l'eleganza tipica delle soluzioni ricorsive.

ed io sono daccordo con te...ma a quanto pare sono poco efficaci le funzioni ricorsive.

A me mi crea problemi per disegnare il contenuto di quell'oggetto con OpenGL, e quindi volevo provare usando una funzione non ricorsiva...

[cdimauro]

Prova con uno stack allora, ma guardando il codice mi sorge il dubbio che la funzione che hai scritto sia inefficiente perché non passi un puntatore o reference (meglio!) all'oggetto (o struttura) cubo, ma ogni volta ne fai una copia intera. Per cui non risolveresti molto passando a una funzione non ricorsiva.

[DomusP45]

Prova con uno stack allora, ma guardando il codice mi sorge il dubbio che la funzione che hai scritto sia inefficiente perché non passi un puntatore o reference (meglio!) all'oggetto (o struttura) cubo, ma ogni volta ne fai una copia intera. Per cui non risolveresti molto passando a una funzione non ricorsiva.

Cosa mi consigli di fare allora? Di modificare questa? Come?

Ti ringrazio anticipatamente per la disponibilità

[Daniels118]

Come ti è suggerito dovresti passare alla funzione il puntatore invece dell'intera struttura, la firma della funzione diventerebbe questa:
void addraw(cubo *temp)
Naturalmente per accedere ai campi di temp dovrai usare l'operatore -> invece del punto.

[DomusP45]

Come ti è suggerito dovresti passare alla funzione il puntatore invece dell'intera struttura, la firma della funzione diventerebbe questa:
void addraw(cubo *temp)
Naturalmente per accedere ai campi di temp dovrai usare l'operatore -> invece del punto.

Ok,
la domanda è: questo tipo di riferimento, cambia le performance della funzione? Oppure in pratica, non cambia niente?

Mi rendo conto che non creare una copia, ma passare il puntatore al riferimento, ottimizza l'uso della memoria, ma i tempi di "calcolo" secondo voi sono migliori?

[Daniels118]

Oltre a ridurre la quantità di memoria utilizzata elimini anche il tempo necessario per copiare le strutture; d'altra parte si introduce un leggero ritardo nell'accesso ai campi poiché i puntatori vanno dereferenziati, però i compilatori creano codice ottimizzato per ridurre al minimo queste operazioni, in sostanza dovresti apprezzare un incremento significativo delle prestazioni.

Una soluzione iterativa sarebbe comunque più efficiente, ma richiederebbe un maggiore sforzo nella progettazione.

[DomusP45]

Oltre a ridurre la quantità di memoria utilizzata elimini anche il tempo necessario per copiare le strutture; d'altra parte si introduce un leggero ritardo nell'accesso ai campi poiché i puntatori vanno dereferenziati, però i compilatori creano codice ottimizzato per ridurre al minimo queste operazioni, in sostanza dovresti apprezzare un incremento significativo delle prestazioni.

Una soluzione iterativa sarebbe comunque più efficiente, ma richiederebbe un maggiore sforzo nella progettazione.

grazie davvero

[cdimauro]

Visto che usi il C++, utilizza i reference (& al posto di * nella firma della funzione), che è meglio. In questo modo puoi continuare a usare anche il . anziché -> per accedere ai campi della struttura.

[DomusP45]

Perfetto, grazie a tutti.