[C] Chiamata ricorsiva alberi binari

[m45511]

salve, ho un dubbio riguardo la ricorsione.
Devo semplicemente verificare se è l'elemento inserito da tastiera è resente nell'albero binario di interi.
La mia soluzione è questa:

int verifica (tipoalbero a, int ele)
{
   if(a==NULL)
   return 0;

   if(a->radice==ele)
   return 1;
   else{
           verifica (a->s, ele) ;
           verifica(a->d, ele);
           }
}

Questa soluzione non funziona. La soluzione funzionante è:

int verifica (tipoalbero a, int ele)
{
   if(a==NULL)
   return 0;

   if(a->radice==ele)
   return 1;
   else{
           return ( verifica (a->s, ele)  || verifica(a->d, ele) );
           }
}

Ho capito il meccanismo ma ho una domanda:
Qualcuno mi può spiegare perchè la chiamata ricorsiva è sul return?
Grazie per l'aiuto

[apatriarca]

Nel primo codice non restituisci alcun valore. Non è necessario che le chiamate ricorsive siano inserite direttamente nel return, ma qualche cosa devi restituire comunque. Avresti anche potuto scriverlo nel seguente modo (o altre varianti simili):

int verifica (tipoalbero a, int ele)
{
   if(a==NULL)
   return 0;

   if(a->radice==ele)
   return 1;
   else{
           int ret = verifica (a->s, ele) ;
           ret ||= verifica(a->d, ele);
           return ret;
           }
}

[m45511]

Ti ringrazio per l'aiuto, ho capito!
Non ho mai visto l'espressione
ret ||=
Ti sei costruito l'or sulla variabile ret se non ho capito male.
Grazie ancora!

[m45511]

Quindi se ho capito bene, dopo una chiamata ricorsiva devo SEMPRE restituire un valore (inerente a quella chiamata).
Mettendo la chiamata ricorsiva direttamente sul return, "sfrutto" il ritorno dei valori precedenti, in questo caso:

 if(a==NULL)
   return 0;

   if(a->radice==ele)
   return 1;

E' giusto questo ragionamento?

[apatriarca]

No, tu devi restituire un valore di ritorno per come hai dichiarato la funzione: la funzione restituisce int e quindi deve sempre restituire un intero. Puoi avere una funzione ricorsiva che non restituisce valori.

||= funzione in modo simile a +=, -=.. ma con l'operazione di or logico ||.

[m45511]

"apatriarca":No, tu devi restituire un valore di ritorno per come hai dichiarato la funzione: la funzione restituisce int e quindi deve sempre restituire un intero. Puoi avere una funzione ricorsiva che non restituisce valori.

||= funzione in modo simile a +=, -=.. ma con l'operazione di or logico ||.

Scusa la mia ottusità ma non riesco a capire.
Ipotizziamo un semplice esempio di ricorsione:

void Esempio(int x) {
  int y;

  if(x==0)
    return;

  Esempio(x-1);
}

int main() {
  float f=-12.3;

  Esempio(90);

  return 0;
}

In questo esempio la ricorsione finisce quando x==0 (controllo sull'if).




Adesso analizzando questa funzione che calcola la profondità dell'albero:

int profondita (tipoalbero a)
{
    int s=0;
    int d=0;
    
    if(a==NULL)
    return -1; // profondità di un albero vuoto
    
           s=profondita(a->s);
           d=profondita(a->d);
             
              if(s>d)
                 return(1+s);
              else
                 return(1+d);
}      

La funzione finisce la ricorsione quando a==NULL e restituisce -1.
Quindi nel misurare la profondità farà una cosa simile:

x=profondità(a)

x sarà la somma dei return (1+s) oppure (1+d).
Quando l'albero finisce (a==null) a questa somma (x) viene sottratto -1 (return di uscita dalla funzione).
Mi pare abbastanza coerente con il ragionamento dei record di attivazione.

Qualcosa non mi è chiaro, quel -1 mi blocca il ragionamento.
Sto sbagliando in qualcosa

[apatriarca]

Non ho capito la domanda. Nel primo esempio non hai bisogno di un secondo return perché si tratta di una funzione che non restituisce valore. La seconda funzione restituisce invece un valore e quindi devono esserci i return per ogni possibile esecuzione della funzione.

[m45511]

"apatriarca":Non ho capito la domanda. Nel primo esempio non hai bisogno di un secondo return perché si tratta di una funzione che non restituisce valore. La seconda funzione restituisce invece un valore e quindi devono esserci i return per ogni possibile esecuzione della funzione.

La mia domanda è questa:

Nel secondo esempio, quando c'è l'uscita dalla ricorsione?
Quando a==NULL?

Se si, quel -1 dove va a finire?
In altre parole non riesco a capire come finisce la ricorsione. Nel primo esempio c'è un punto di uscita, nel secondo manca e mi blocca il ragionamento

[apatriarca]

Il punto di uscita dalla ricorsione, se ho capito bene cosa intendi, è qualsiasi return a cui si arrivi senza chiamare in modo ricorsivo la funzione. Nel secondo caso, se a == NULL, la funzione restituisce -1 senza dover richiamare se stessa e quindi la ricorsione ha termine.

[m45511]

"apatriarca":Il punto di uscita dalla ricorsione, se ho capito bene cosa intendi, è qualsiasi return a cui si arrivi senza chiamare in modo ricorsivo la funzione. Nel secondo caso, se a == NULL, la funzione restituisce -1 senza dover richiamare se stessa e quindi la ricorsione ha termine.

Scusami ma sono un idiota, ancora non ci arrivo:


Se a==NULL:
return -1; (solo se a ERA == null all'inizio)

1)applico la chiamata ricorsiva al sottoalbero sinistro, s=profondita(a->s);

2) se s>d
return(1+s);
altrimenti
return(1+d);

E' il punto 2) che non capisco.
Come fa a portare a termine la somma senza sapere dove fermarsi?

[apatriarca]

Ci sono linguaggi in cui la ricorsione è qualcosa di gestito in modo particolare dal compilatore, ma il C non è tra questi. Una chiamata ricorsiva non ha nulla di particolare. È semplicemente una chiamata a funzione. Il fatto che questa chiamata sia verso la funzione in cui ci si trova non cambia il modo in cui questa chiamata a funzione viene interpretata dal compilatore. Quello che succede in quelle righe è quindi il seguente:
1. Chiami ricorsivamente la funzione sull'albero sinistro. Questa funzione ad un certo punto finirà la sua esecuzione (non ci importa come) e restituirà un valore che memorizzerai nella variabile s.
2. Chiami ricorsivamente la funzione sull'albero destro e scrivi il valore restituito in d.
3. Confronti s e d e restituisci il valore corrispondente in base al confronto.
Se la funzione era stata chiamata dall'interno di se stessa (in uno tra i punti 1 o 2), allora il valore di ritorno in 3 sarà scritto nella corrispondente variabile locale nella funzione da cui è partita la chiamata. Questa a sua volta restituirà il valore alla funzione chiamante fino ad arrivare alla fine della ricorsione.

[m45511]

Ti ringrazio molto per la pazienza e la disponibilità.
A presto e buona serata!
Grazie ancora!

[m45511]

"apatriarca":Ci sono linguaggi in cui la ricorsione è qualcosa di gestito in modo particolare dal compilatore, ma il C non è tra questi. Una chiamata ricorsiva non ha nulla di particolare. È semplicemente una chiamata a funzione. Il fatto che questa chiamata sia verso la funzione in cui ci si trova non cambia il modo in cui questa chiamata a funzione viene interpretata dal compilatore. Quello che succede in quelle righe è quindi il seguente:
1. Chiami ricorsivamente la funzione sull'albero sinistro. Questa funzione ad un certo punto finirà la sua esecuzione (non ci importa come) e restituirà un valore che memorizzerai nella variabile s.
2. Chiami ricorsivamente la funzione sull'albero destro e scrivi il valore restituito in d.
3. Confronti s e d e restituisci il valore corrispondente in base al confronto.
Se la funzione era stata chiamata dall'interno di se stessa (in uno tra i punti 1 o 2), allora il valore di ritorno in 3 sarà scritto nella corrispondente variabile locale nella funzione da cui è partita la chiamata. Questa a sua volta restituirà il valore alla funzione chiamante fino ad arrivare alla fine della ricorsione.

Ti scrivo una funzione fatta da me che sembra funzionare! Con questa scrittura mi è chiaro il funzionamento e la struttura:

int profondita (tipoalbero a)
{
    int s=0;
    int d=0;
    
    if(a==NULL)
    return -1; // profondità di un albero vuoto
           
           s=profondita(a->s);
           d=profondita(a->d);
       
          if(a->s) 
           s++;
           else
           d++;
           
             
              if(s>d)
                 return(s);
              else
                 return(d);
}