Funzioni ricorsive

Funzioni ricorsive

By Giovanni Pedroncelli

Funzioni ricorsive

Definizione

Una funzione ricorsiva è una funzione che contiene una chiamata a se stessa.

​

​void fattoriale(int n){

.............................​

​ fattoriale(n-1);

}

Funzioni ricorsive

Schema

Per evitare che la funzione chiami infinitamente se stessa è necessario fornire un modo per uscire dalla funzione termina​ndola

​

Due elementi distinti:

​

1. Condizione di terminazione della funzione (elemento NON ricorsivo)

2. ​Passo ricorsivo (di avvicinamento alla condizione di terminazione)

Funzioni ricorsive

Esempio

int fattoriale (int n){ //INTESTAZIONE FUNZIONE​

if(n==1){ // CONDIZIONE DI TERMINAZIONE

​ return 1; // USCITA DALLA FUNZIONE

}  

return fattoriale(n-1) * n;   // CHIAMATA A SE STESSA​ E

// CONTEMPORANEAMENTE ANCHE PASSO DI AVVICINAMENTO

}​

ISTRUZIONI	n	​CHIAMATA
​Chiamata iniziale	3​	​fattoriale(3)
Condizione FALSA (3==1)	​	​
prima chiamata ricorsiva​	​	fattoriale(2) * 3
​Condizione FALSA (2==1)	​2	​
​seconda chiamata ricorsiva	​	​fattoriale(1) * 2
​CONDIZIONE VERA (1==1)	1​	​
​USCITA DALLA FUNZIONE	​	return 1​