[C] Un aiuto su ricorsione e alberi binari

[Downloader]

Ciao a tutti,
mi dareste una mano a comprendere bene che ragionamento seguire quando devo fare chiamate ricorsive per gestire un albero binario?

Ad esempio stavo provando a studiare questo codice che conta il numero di elementi presenti nell'albero:

int num_elem(tree t)
{
 if (t == NULL)
 return 0;
 else
  return num_elem(t->sx) + num_elem(t->dx) + 1;
}

Uno dei miei dubbi più grandi è:



una volta raggiunto il nodo foglia (d ad esempio) num_elem(t->sx) torna essendo NULL 0, ma dopo che succede??
Si torna alla funzione del nodo chiamante (b) e poi si visita il nodo dx oppure si lancia num_elem(t->dx) relativa alla funzione che ha precedentemente chiamato num_elem(t->sx) (tornando 0)??


Grazie

[KataKlism2002]

Devi cercare di immaginare lo stack delle chiamate.

il primo nodo ad essere chiamato è A, che chiama SX ovvero B... DX lo chiamerà solo dopo che avrà computato tutto il sottoramo SX. quindi B chiamerà SX ovvero D, stesso discorso per DX di B, che verrà chiamato quando tutto SX avrà tornato un valore. D chiamerà SX, che ritornerà 0, e poi DX, che gli ritornerà 0, a questo punto ritornerà 1 al chiamante ovvero B, che ora che ha finito con il ramo di sinistra passa a quello di destra chiamando E, e così via.

[Downloader]

Scusa, ma nel caso base, come fa a tornare sempre 0?
Cioè, come conto gli elementi se mi torna sempre lo 0?
Io mi sarei aspettato che nel caso base tornasse 1.

[KataKlism2002]

ma se la foglia è null perchè deve tornare 1?

gli elementi li conto con il + 1 di
"return num_elem(t->sx) + num_elem(t->dx) + 1;"



prendi il nodo D del tuo esempio

le sue foglie sono null... ovvero non ha foglie, ovvero è egli stesso una foglia, giusto? quindi dovrebbe tornare 1, e infatti torna 1

return num_elem(t->sx) + num_elem(t->dx) + 1;

in italiano: Ritorna il numero di nodi a sinistra (zero) + il numero di nodi a destra (zero) + te stesso (1) = 1

quindi al suo chiamante, cioè B ritornerà 1.

[Downloader]

Ma a parte l'esperienza che si accumula nel tempo, c'è qualche pagina web che parla in maniera dettagliata del funzionamento ricorsivo di un albero??

Io proprio non riesco a immaginarmi cosa avviene, e purtroppo se prima non riesco a farlo non riesco poi a scrivere codice.

Grazie

[mondobimbi]

la ricorsione la hai capita ?, prova questo semplice programma, eventualmente utilizzando il debugger passo passo.

#include <stdio.h>
int sum (int n) 
{
    if (n) return n+sum(n-1);
    else return 0;
}

int main (int argc, char *argv[])
{
    if (argc != 2) {
        printf("Specificare un intero\n");
        return (-1);
    }
    else {
        int n = atoi(argv[1]);
        printf("La somma dei primi %s interi è %d\n", argv[1], sum(n));
        printf("Avrei potuto anche usare la formula n*(n-1)/2=%d\n", n*(n+1) /2);
        return (0);
    }
} 

Comunque non ti preoccupare, la ricorsione è tosta da capire, bisogna concentrarsi molto e provare e provare.
Roma non fu fatta in un giorno
ciao
sergio