[C] Problema funzione ricorsiva

[paulinho]

Non riesco a capire dove sta l'errore.
questa è la funzione :
Ricerca il parlamentare di un dato partito che ha ricevuto il maggior numero di voti.
E’ RICHIESTA UNA IMPLEMENTAZIONE RICORSIVA SULLA BASE DEL DIVIDE ET IMPERA.

TNode* parlamentare_votato(TTree tree, char partito[]){
   TTree sx, dx,curr;
   
   if(tree == NULL)
      return NULL;
   
   if((tree != NULL) && (strcmp(tree->info.satellite.partito, partito)==0) )
      curr = tree;
   else{
     
      sx = parlamentare_votato(tree->left, partito);
      dx = parlamentare_votato(tree->right, partito);
      if((curr->info.satellite.voti >= sx->info.satellite.voti) &&  (sx->info.satellite.voti >= dx->info.satellite.voti))
      return curr;
   else if((sx->info.satellite.voti >= curr->info.satellite.voti) && (curr->info.satellite.voti >= dx->info.satellite.voti))
         return sx;
   else if((dx->info.satellite.voti >= curr->info.satellite.voti) && (curr->info.satellite.voti >= sx->info.satellite.voti))
      return dx;
      else
         return NULL;
   }
}

[MegaAlchimista]

Com'è fatto l'albero?

Edit:
Ma scusa

      
if((tree != NULL) && (strcmp(tree->info.satellite.partito, partito)==0) )
       curr = tree;    
else{  
...
}
//qui non dovrebbe esserci un return *qualcosa* ?

Se entri in quell'if la funzione non torna niente

[paulinho]

Originariamente inviato da MegaAlchimista
Com'è fatto l'albero?

Edit:
Ma scusa

      
if((tree != NULL) && (strcmp(tree->info.satellite.partito, partito)==0) )
       curr = tree;    
else{  
...
}
//qui non dovrebbe esserci un return *qualcosa* ?

Se entri in quell'if la funzione non torna niente

anche mettendo un return non va... quello è un progetto e non so come farvelo vede ..

[paulinho]

l'albero è un bst, ossia un albero binario di ricerca.

[MegaAlchimista]

Premetto che non so molto di alberi, comunque vediamo un attimo, ci sono delle cose che non mi sono chiare

TNode* parlamentare_votato(TTree tree, char partito[]){
   TTree sx, dx,curr;
   
   if(tree == NULL)
      return NULL;
   
   if((tree != NULL) && (strcmp(tree->info.satellite.partito, partito)==0) )
      curr = tree;
   else{
      sx = parlamentare_votato(tree->left, partito);    //<-qui esci!!!
      dx = parlamentare_votato(tree->right, partito);
      if((curr->info.satellite.voti >= sx->info.satellite.voti) &&  (sx->info.satellite.voti >= dx->info.satellite.voti))
      return curr;
   else if((sx->info.satellite.voti >= curr->info.satellite.voti) && (curr->info.satellite.voti >= dx->info.satellite.voti))
         return sx;
   else if((dx->info.satellite.voti >= curr->info.satellite.voti) && (curr->info.satellite.voti >= sx->info.satellite.voti))
      return dx;
      else
         return NULL;
   }
return curr;   //credo che qui ci debba stare questo, oppure potevi direttamente metterlo sotto l'if (meglio, non copi dati inutilmente)
}

se tu percaso entri nell'else vai subito nella parte che ho messo in grassetto, già alla prima riga richiami questa funzione in modo ricorsivo, quindi l'esecuzione si ferma qui. Tutto quello che c'è dopo

sx = parlamentare_votato(tree->left, partito);

non verrà mai eseguito.
Cosa volevi fare con queste istruzioni?

Ah inoltre curr non è inizializzato: quindi quando tu scrivi

 if((curr->info.satellite.voti >= sx->info.satellite.voti) &&  (sx->info.satellite.voti >= dx->info.satellite.voti))
      return curr;

stai comparando un albero costruito con il costruttore di default... ne sei consapevole e lo fai apposta?

E che cos'è quell' "info.satellite"?

Poi c'è anche un'altra cosa che non mi è chiara, ma probabilmente dipende dalla mia ignoranza in fatto di alberi : tu hai una funzione che deve tornare un puntatore a nodo, invece ovunque in questo codice fai tornare un albero. Inoltre a quanto pare questo albero ha due metodi (left() e right() ) che tornano a loro volta un albero... che sarebbero? alberi che hanno come root un nodo in particolare?
A questo punto mi viene da pensare invece che TTree abbia un costruttore che prende un nodo e costruisce un albero che ha come root questo nodo, e che TTree::left() e TTree::right() invece restituiscano nodi, e che vengano costruiti gli alberi in modo implicito

[paulinho]

stai comparando un albero costruito con il costruttore di default... ne sei consapevole e lo fai apposta?

E che cos'è quell' "info.satellite"?

Poi c'è anche un'altra cosa che non mi è chiara, ma probabilmente dipende dalla mia ignoranza in fatto di alberi : tu hai una funzione che deve tornare un puntatore a nodo, invece ovunque in questo codice fai tornare un albero. Inoltre a quanto pare questo albero ha due metodi (left() e right() ) che tornano a loro volta un albero... che sarebbero? alberi che hanno come root un nodo in particolare?
A questo punto mi viene da pensare invece che TTree abbia un costruttore che prende un nodo e costruisce un albero che ha come root questo nodo, e che TTree::left() e TTree::right() invece restituiscano nodi, e che vengano costruiti gli alberi in modo implicito [/QUOTE]

Innanzitutto grazie per l'attenzione datami; Dopodichè premetto il seguente tipo costruito da me :

struct SNode {
   TInfo info;
   struct SNode *left;
   struct SNode *right;
};
typedef struct SNode TNode;
typedef TNode* TTree;


struct SKey{
   char tessera[8];
};   
typedef struct SKey TKey;

struct SSat {
   char cognome[16];
   char nome[16];
   char partito[6];
   int voti;
};
typedef struct SSat TSat;

struct SInfo{
      TKey key;
      TSat satellite;
};

typedef struct SInfo TInfo;

Da questo codice si evince che in realtà TTree è un altro modo per indicare TNode*, le due notazioni sono la stessa cosa.
Poi tu stai parlando di costruttore e metodi, ma questo non riguarda la programmazione orientata agli oggetti, come il linguaggio java?

Comunque mi stai dando comunque degli spunti, ad esempio ora provo a inizializzare curr e a modificare la posizione delle chiamate ricorsive.

[MegaAlchimista]

Ah scusa non sono abituato a pnsare ai container in c, per qualche arcano motivo mi ero dimenticato del titolo di questo topic e pensavo stessi scrivendo in c++.
Detto questo: è ancora peggio , se curr non è inizializzato si becca i dati che trova in Ram quando viene creato, quindi devi inizializzarlo per forza.

E poi semplicemente ripensa a cosa sia una funzione ricorsiva: nel momento in cui tu chiami la funzione ricorsiva, quello è un punto di uscita, quindi il codice successivo non verrá eseguito.
Pensa prima ad una semplice funzione ricorsiva come quella del fattoriale (fattela per esercizio) e poi applica i principi a questa (che sicuramente è più complessa)

[paulinho]

Originariamente inviato da MegaAlchimista
Ah scusa non sono abituato a pnsare ai container in c, per qualche arcano motivo mi ero dimenticato del titolo di questo topic e pensavo stessi scrivendo in c++.
Detto questo: è ancora peggio , se curr non è inizializzato si becca i dati che trova in Ram quando viene creato, quindi devi inizializzarlo per forza.

E poi semplicemente ripensa a cosa sia una funzione ricorsiva: nel momento in cui tu chiami la funzione ricorsiva, quello è un punto di uscita, quindi il codice successivo non verrá eseguito.
Pensa prima ad una semplice funzione ricorsiva come quella del fattoriale (fattela per esercizio) e poi applica i principi a questa (che sicuramente è più complessa)

Grazie mille ancora per l'attenzione, non so chi tu sia, ma ti inizio a volere bene , mi stai incoraggiando con i tuoi consigli.

Quindi una volta che faccio la chiamata ricorsiva tutto quello che segue non viene fatto? Giusto?
Dunque dovrei pensare alla condizione del "parlamentare più votato" facendo in modo che risulti come caso base .. Giusto? e poi applicare le chiamate ricorsive? giusto ? alla fine ?

[MegaAlchimista]

Allora... Prendendone una semplice:

//queata funzione restituisce il fattoriale di n (=1*2*3*...n-1*n)
int fattoriale(int n)
{
If(n<=1)
    return 1;              //il mio vero punto di uscita
n *= fattoriale(n-1);
return n;
}

Allora entri nella funzione, con ingressi 0 o 1 la funzione torna 1 (perchè così è definito il fattoriale), altrimenti copio n (vedi che non gli passo l'indirizzo, ma lo copio: è importante) e lo moltiplico per il fattoriale del numero che lo precede... In questo modo questa stessa funzione viene richiamata n-1 volte.
ESEMPIO
Se la chiamo per n=3, lui entra ed esegue

n= 3* fattoriale(2)

, per calcolare fattoriale di due esegue

n=2*fattoriale(1)

, il fattoriale di 1 torna 1, quindi la prima chiamante in definitiva fa
N=1*2*3.
che è quello che volevamo ottenere.
Allora cosa ha di particolare questa funzione?
In primis ha un punto di uscita (return 1) che dopo un certo numero di chiamate viene SEMPRE raggiunto!
Se così non fosse la funzione continuerebbe a chiamare se stessa in modo infinito!
Dopo questo c'è la vera ricorsione: la runzione richiama se stessa con differenti input.
Infine faccio ritornare il valore calcolato.

Ora pensaci bene ed applica questi concetti alla tua situazione

[paulinho]

Allora entri nella funzione, con ingressi 0 o 1 la funzione torna 1 (perchè così è definito il fattoriale), altrimenti copio n (vedi che non gli passo l'indirizzo, ma lo copio: è importante) e lo moltiplico per il fattoriale del numero che lo precede... In questo modo questa stessa funzione viene richiamata n-1 volte.
ESEMPIO
Se la chiamo per n=3, lui entra ed esegue

n= 3* fattoriale(2)

, per calcolare fattoriale di due esegue

n=2*fattoriale(1)

, il fattoriale di 1 torna 1, quindi la prima chiamante in definitiva fa
N=1*2*3.
che è quello che volevamo ottenere.
Allora cosa ha di particolare questa funzione?
In primis ha un punto di uscita (return 1) che dopo un certo numero di chiamate viene SEMPRE raggiunto!
Se così non fosse la funzione continuerebbe a chiamare se stessa in modo infinito!
Dopo questo c'è la vera ricorsione: la runzione richiama se stessa con differenti input.
Infine faccio ritornare il valore calcolato.

Ora pensaci bene ed applica questi concetti alla tua situazione

ok grazie.Sembra di esserci riuscito.Un ultima domanda.. Quando alloco una struttura dati, che sia un albero o una lista o che si voglia, alla fine devo sempre deallocarla. giusto?