FUNZIONI RICORSIVE

Le funzioni ricorsive sono quelle che dentro al codice hanno un’invocazione a se stesse, questa funzione ha un istruzione di controllo che interrompe la successione di chiamate quando si verificano certe condizioni, lavora su un insieme ampio di valori, risultando più comprensibile e più facile della funzione iterativa, l’esempio più noto di questo tipo di funzione è il calcolo del fattoriale di un numero intero, ad esempio:

int fact(int n) {

if ( n <= 1 ) //istruzione di controllo

return 1;

return n * fact(n-1); }

Per ottenere la soluzione, basta moltiplicare tra di loro i risultati parziali così ottenuti procedendo a ritroso.

FUNZIONI RICORSIVE 2

Perchè nelle funzioni ricorsive si procede a ritroso?

Perchè le funzioni ricorsive usano lo stack; per ogni funzione c’è una zona di

memoria in cui si trovano le variabili locali della funzione, la zona di memoria del

main si trova nel punto più basso dello stack, ogni volta che si richiama una

funzione viene creata una zona di memoria sopra a questa.

Chiamata 3

MAIN

Chiamata 1

Chiamata 2

STACK

FUNZIONI RICORSIVE 3

Dopo aver riempito lo stack ed aver finito l’esecuzione, il

programma svuota lo stack e comincia a fare i calcoli con le variabili che sono state salvate nelle zone di memoria, nel caso

della funzione fattoriale, farà la moltiplicazione di tutte le variabili.