[C] Problema funzioni ricorsive

[ale_picci]

Ciao ragazzi? potete gentilmente spiegare come funziona questo stralcio di codice per n =4?
Non mi è ancora chiaro il funzionamento.
Vi ringrazio a tutti in anticipo.

int funct (int n)
{
int i, ris = 0;
if (n == 0)
return 1;

for (i = 1; i <= n; i *= 2)
ris += i;

ris += funct(n-1);

return ris;
}

[scimmiaparlante]

Se chiamo funct(4) restituirà:
1+2+4+(1+2+(1+2+(1+(1)))).

La funzione chiamata su 4 aggiunge a ris, inizialmente 0, le potenze di 2 inferiori o uguali a 4, partendo da 2^0 (dato che nel for l'incremento avviene raddoppiando): aggiunge quindi 1,2 e 4.
A quel punto incrementa ris del valore della funzione calcolata per n = 3, che deve essere quindi eseguita.
La funzione viene così chiamata su 3 e farà la stessa cosa sulla SUA istanza di ris incrementandola di 1 e poi 2, quindi del valore della funzione per n=2. Stessa cosa finché non avviene la chiamata su n = 0; che termina immediatamente ritornando 1.
Quindi può concludere la funzione per n = 1, che ritorna funct(1) = 1+funct(0) = 2,
poi la funzione per n = 2, che ritorna funct(2) = 1+2+funct(1) = 1+2+2 = 5,
poi la funzione per n = 3, che ritorna funct(3) = 1+2+funct(2) = 1+2+5 = 8,
poi la funzione per n = 4, che ritorna funct(4) = 1+2+4+funct(3) = 1+2+4+8 = 15.

[ale_picci]

Grazie, purtroppo non ho ancora capito l'esercizio. devo entrare nell'ottica delle funzioni ricorsive.
Potresti spiegarmelo meglio perfavore?

[scimmiaparlante]

Allora, cerca di capire che avviene nella memoria:
Quando tu chiami funct(4), viene allocato lo spazio necessario alla funzione. In questo spazio ci saranno memorizzati i, n e ris relativi alla chiamata appena fatta. La funzione viene eseguita normalmente fino al punto in cui abbiamo

ris += funct(n-1);

In questo momento, riguardo alla chiamata di funct(4), in memoria avremo i valori i = 8, n = 4, ris = 7.
A questo punto ris deve essere incrementato di funct(n-1).
L'unico modo per sapere quanto vale funct(n-1) = funct(3) è eseguire la funzione: l'esecuzione di funct(4) potresti quindi in un certo senso vederla come "sospesa", in attesa di sapere il risultato.
Dobbiamo quindi eseguire funct(3) dall'inizio e il tutto avviene come sopra: si alloca lo spazio per delle nuove istanze di i, n e ris che saranno totalmente indipendenti da quelle precedenti, che giacciono per ora dimenticate più in basso nello stack. L'esecuzione della funzione su 3 prosegue indipendentemente e si arriverà di nuovo al punto in cui si deve eseguire

ris += funct(n-1);

A quel punto la situazione in memoria sar� del tipo

---------- -|
- 3 - n |
---------- |
- 4 - i | -> appartengono a funct(3)
---------- |
- 3 - ris |
---------- -|

(altre cose che omettiamo)

---------- -|
- 4 - n |
---------- |
- 8 - i | -> appartengono a funct(4)
---------- |
- 7 - ris |
---------- -|

A questo punto la cosa si ripete finchè non si avrà la chiamata a funct(0)
Questa volta non si esegue tutto il codice, ma si ritorna subito perchè nell'if iniziale c'è la condizione di uscita

    
if (n == 0)
    return 1;

Nota che tutte le funzioni ricorsive devono avere un caso base, altrimenti si continua a chiamare all'infinito, senza mai terminare.
In questo momento la situazione sarà del tipo:

---------- -|
- 1 - n |
---------- |
- 2 - i | -> appartengono a funct(1)
---------- |
- 2 - ris | -----------> Qui è già stato aggiunto funct(0) che vale 1
---------- -|

(altre cose che omettiamo)

---------- -|
- 2 - n |
---------- |
- 4 - i | -> appartengono a funct(2)
---------- |
- 3 - ris |
---------- -|

(altre cose che omettiamo)

---------- -|
- 3 - n |
---------- |
- 4 - i | -> appartengono a funct(3)
---------- |
- 3 - ris |
---------- -|

(altre cose che omettiamo)

---------- -|
- 4 - n |
---------- |
- 8 - i | -> appartengono a funct(4)
---------- |
- 7 - ris |
---------- -|

Funct(1) giunge così al termine, essendo stata calcolata funct(0).
Viene quindi deallocato il suo spazio e il suo valore di ritorno viene sommato al ris di funct(2)

---------- -|
- 2 - n |
---------- |
- 4 - i | -> appartengono a funct(2)
---------- |
- 5 - ris |
---------- -|

(altre cose che omettiamo)

---------- -|
- 3 - n |
---------- |
- 4 - i | -> appartengono a funct(3)
---------- |
- 3 - ris |
---------- -|

(altre cose che omettiamo)

---------- -|
- 4 - n |
---------- |
- 8 - i | -> appartengono a funct(4)
---------- |
- 7 - ris |
---------- -|

Può terminare quindi funct(2) e il valore che ritorna lo sommiamo al ris di funct(3)



---------- -|
- 3 - n |
---------- |
- 4 - i | -> appartengono a funct(3)
---------- |
- 8 - ris |
---------- -|

(altre cose che omettiamo)

---------- -|
- 4 - n |
---------- |
- 8 - i | -> appartengono a funct(4)
---------- |
- 7 - ris |
---------- -|

Infine termina funct(3) e il suo valore di ritorno è sommato al ris di funct(4)

---------- -|
- 4 - n |
---------- |
- 8 - i | -> appartengono a funct(4)
---------- |
- 15 - ris |
---------- -|

funct(4) ritorna il suo ris = 15.

Spiegarlo scrivendo non è così facile. Ti consiglio di cercare in giro qualche animazione che lo faccia visualizzare bene e che utilizzi qualche funzione che abbia un senso pratico più evidente di questo, come la successione di Fibonacci (fib(n) = fib(n-1) + fib(n-2)) o il calcolo di un fattoriale (fatt(n) = n*fatt(n-1)).
In alternativa puoi usare un debugger visuale e scorrere le istruzioni del programma vedendo in che ordine sono eseguite e come cambiano le variabili.



NOTA: il forum ha collassato tutti gli spazi multipli nei "disegnini", comunque sia il senso è che ogni blocchetto appartiene ad un' istanza diversa della funzione

[oregon]

Questi concetti possono non essere semplici da comprendere (almeno non immediati), se non hai CHIARISSIMO il funzionamento dello STACK e di come questo interviene tra le varie chiamate delle funzioni (ricorsive o non).

Se pensi di non essere sicurissimo del suo funzionamento, fai un passo indietro e studia bene lo STACK e la sua importanza nella chiamata di funzioni.

[ale_picci]

è meglio forse usare qualche programma che mi mostra le varie istruzioni. Sapresti consigliarmi qualcuno? Grazie di cuore

[ale_picci]

ma bisogna partire da n=4, e poi scendere sino ad arrivare ad n=0 giusto??

[oregon]

Non usi un ambiente di compilazione integrato con debugger?

[ale_picci]

no per il momento. mi potresti consigliare qualcuno?