[C] Funzione ricorsiva

[felpone]

Ciao,
ho questa funzione che lavora su stack (e fa una somma sugli elementi),non riesco a capire come faccia a ricreare lo stack la funzione push in quanto è fuori dalla ricorsione.
Grazie

int somma(stack s){
    int x, sum;
    if (isEmptyStack(s)) return 0;
    x=pop(s);
    sum=somma(s)+x;
    push(s,x);
    return sum;
}

[LeleFT]

La push non è fuori dalla ricorsione... è solo richiamata dopo che è stato eseguito l'n-esimo passo ricorsivo... ad ogni passo (quindi, anche nei passi ricorsivi).


Ciao.

[felpone]

Uhmm..non mi è chiara questa cosa...ma la push non viene invocata quando ormai la catena delle chiamate ricorsive si è "riavvolta"ed ha sommato i valori memorizzandoli in sum?

[Who am I]

Dopo il pop viene fatto nuovamente un push di x, quindi lo stack rimane inalterato proprio perché i valori vengono rimessi dentro lo stack.
Lo stack prima si svuota, poi quando l' ultima chiamata (quella in cui isEmptyStack(s) ritorna true) termina viene ripopolato con i push.Se il push lo mettessi prima di sum=somma(s)+x la funzione non terminerebbe mai.
Se vuoi vedere meglio come accadono le cose ti consiglio di usare del breakpoint per vedere passo passo cosa succede.

[LeleFT]

Originariamente inviato da felpone
Uhmm..non mi è chiara questa cosa...ma la push non viene invocata quando ormai la catena delle chiamate ricorsive si è "riavvolta"ed ha sommato i valori memorizzandoli in sum?

Sì, ma tu stai guardando solo il primo passo. Quello che hai detto vale per tutti i passi successivi, ovvero, in tutti i passi successivi viene tolto un elemento, sommato e poi rimesso l'elemetno al suo posto. La chiamata alla funzione "somma" lascia inalterato lo stack che le viene passato. Quindi, al passo N, tolgo un elemento, chiamo "somma" (che, ripeto, lascia inalterato lo stack) e poi rimetto dentro l'elemento tolto (lasciando, ancora, inalterato lo stack).

Esempio pratico con uno stack di 3 elementi:

chiamo somma(stack[1 2 3])
Stack vuoto?
NO: tolgo il 3; stack = [1 2]
chiamo somma(stack[1 2])
    01) Stack vuoto?
        NO: tolgo il 2; stack = [1]
        chiamo somma(stack[1])
        02) Stack vuoto?
            NO: tolgo 1; stack = []
            chiamo somma(stack[])
            03) Stack vuoto?
                SI: lascio tutto inalterato e torno 0
            sum = 0 + 1
            push(stack, 1); stack = [1]
            ritorno 1;
        sum = 1 + 2
        push(stack, 2); stack = [1 2]
        ritorno 3
    sum = 3 + 3
    push(stack, 3); stack = [1 2 3]
    ritorno 6
Valore finale = 6
E stack inalterato

Ciao.

[felpone]

Ok,quindi la push viene invocata ad ogni "riavvolgimento" delle chiamate ricorsive precedentemente srotolate?

[Who am I]

Originariamente inviato da felpone
Ok,quindi la push viene invocata ad ogni "riavvolgimento" delle chiamate ricorsive precedentemente srotolate?

Bel modo di vederla Si in effetti è proprio così.

[felpone]

Io la vedo così ma non mi convince. In effetti la push è chiamata solamente quando si "riavvolge" tutte le chiamate ricorsive(la riga dell'istruzione push è scritta dopo la chiamata ricorsiva),quindi non capisco come faccia la push a prendere ogni elemento e inserirlo nello stack!