C/C++ - Ricorsione - Piero Tofy.it

Forum - C/C++ - Ricorsione

MagoAntò (Normal User)
Rookie

Messaggi: 42
Iscritto: 07/02/2009

Postato alle 16:00
Martedì, 01/05/2012

Ciao a tutti!

Mentre rileggevo il codice di un programma che ho completato, mi è venuto un dubbio: senza voler scendere troppo in particolari, ho bisogno di confrontare una stringa digitata dall'utente con le chiavi di ciascun nodo di un albero binario e di salvare il risultato di questo confronto in una matrice.

La funzione che ho scritto è di questo tipo:

Codice sorgente - presumibilmente C/C++

void inorder (node n, string stringa)
{
 if (node!=NULL)
 {
  funzione_ricorsiva (n->figlio_sx());
 int** matrice = NULL;
 // chiamata alla funzione per il confronto
 funzione_ricorsiva(n->figlio_dx());
 }
}

E' sbagliato dichiarare delle variabili nel corpo di una funzione ricorsiva? Ad ogni chiamata, in pratica, viene istanziata una nuova variabile puntatore a intero? Sarebbe meglio convertire la funzione da ricorsiva ad iterativa?

Grazie in anticipo per le risposte.

Poggi Marco (Member)
Guru

Messaggi: 969
Iscritto: 05/01/2010

Postato alle 17:44
Martedì, 01/05/2012

Ciao!

Certamente le funzioni ricorsive richiedono molte risorse, sia per la memoria sullo stack, che per le variabili interne.
Ma non sempre si implementare un meccanismo iterativo, sia semplice.

MagoAntò (Normal User)
Rookie

Messaggi: 42
Iscritto: 07/02/2009

Postato alle 19:01
Martedì, 01/05/2012

Innanzitutto, grazie per la risposta.

In realtà, il codice per una visita inorder di un albero binario ce l'avrei anche nei miei appunti. La mia perplessità nasce dall'uso della ricorsione stessa: ad ogni chiamata ricorsiva, vengono create "nuove copie" delle variabili dichiarate nel corpo della funzione (dopo la sfilza di chiamate ricorsive per la discesa a sinistra, vengono inizializzate con i valori del nodo corrente e passate ad un'altra funzione)? E' corretto dichiarare delle variabili nel corpo di una funzione ricorsiva? Riscrivendola con un approccio iterativo, queste copie "extra" non verrebbero create, giusto?

Poggi Marco (Member)
Guru

Messaggi: 969
Iscritto: 05/01/2010

Postato alle 20:35
Martedì, 01/05/2012

Se in una funzione, servono delle variabili è giusto dichiararle, indipendentemente se quest' ultima sia ricorsiva o meno.
Per quanto riguarda il processo iterativo, non si creano copie "extra", ma a volte, bisogna creare una " struttura " che simuli il meccanismo di ricorsione.

MagoAntò (Normal User)
Rookie

Messaggi: 42
Iscritto: 07/02/2009

Postato alle 21:54
Martedì, 01/05/2012

Ok, ho capito. Grazie ancora!