[C] Problema funzioni ricorsive

[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