Come definire una funzione ricorsiva in Ocaml
Nel linguaggio Ocaml definisco una funzione ricorsiva usando le parole let rec
let rec nomefunzione
Un esempio pratico
Creo una funzione per calcolare il fattoriale n! di un numero intero.
let rec fattoriale n =
if n=0 then 1
else n*fattoriale(n-1);;
La funzione fattoriale riceve in entrata un valore intero positivo che registra nella variabile locale n.
Se la variabile n è maggiore di zero, la funzione richiama se stessa in modo ricorsivo per moltiplicare n con il fattoriale del numero predecessore n-1.
La ricorsione termina quando n=0.
Ad esempio, richiamo la funzione fattoriale() passandogli il valore 4.
fattoriale 4;;
- : int = 24
Il risultato è 24.
In questo caso la funzione fattoriale(4) compie 4 ricorsioni.
- 4*fattoriale(3)
- 3*fattoriale(2)
- 2*fattoriale(1)
- 1*fattoriale(0)
Alla ricorsione fattoriale(0) la funzione restituisce 1
- 4*fattoriale(3)
- 3*fattoriale(2)
- 2*fattoriale(1)
- 1*1
Pertanto, alla ricorsione fattoriale(1) viene assegnato il prodotto 1*1=1
- 4*fattoriale(3)
- 3*fattoriale(2)
- 2*1
Alla ricorsione fattoriale(2) viene assegnato il prodotto 2*1=2
- 4*fattoriale(3)
- 3*2
Alla ricorsione fattoriale(3) viene assegnato il prodotto 3*2=6
- 4*6
Pertanto il risultato finale della funzione fattoriale(4) è 6*4=24.
Il fattoriale di 4! è 24.
E così via.