Tail Recursion F#
I linguaggi funzionali come F# incoraggiano l'utilizzo della ricorsione piuttosto che dell'iterazione.
Solitamente quando una funzione o un metodo ne chiamano un altro viene aggiornata la "call stack" ovvero la pila che tiene traccia appunto della posizione in cui siamo nell'esecuzione e in quale punto dobbiamo eventualmente tornare.
Nel caso di ricorsioni molto profonde si può incorrere in una stackoverflow exception in quanto la nostra pila potrebbe finire lo spazio per registrare le chiamate alla funzione ricorsiva.
Per risolvere questo problema si utilizza una tecnica chiamata "tail recursion". Questa tecnica,se supportata dal compilatore, permette di evitare l'aggiunta delle chiamate alla funzione nella call stack.
Per farlo è necessario restituire direttamente il valore ricevuto dalla successiva chiamata ricorsiva. Affinché una tecnica del genere funzioni potrebbe essere necessario l'utilizzo di un accumulatore per portarsi dietro il risultato parziale della ricorsione. Vediamo un semplice esempio con la funzione fattoriale presentata in due versioni, una senza tail recursion e una con.
let rec factorial n = if n = 1 then 1 else n * factorial(n-1)
let tailFactorial n =
let rec inner n f = if n = 1 then f else inner (n-1) (n * f)
inner n 1
let a = factorial 5
let b = tailFactorial 5
Come vediamo la prima versione ha bisogno del risultato della successiva chiamata per effettuare la moltiplicazione per n.
La seconda versione invece, in particolare la funzione inner, si porta dietro il risultato parziale del conto è restituisce direttamente il risultato della chiamata successiva. Infatti nei due rami della if restituiamo “f” il calcolo del fattoriale che ci siamo passati di volta in volta nella funzione oppure il risultato di inner dove aggiorniamo il risultato parziale f e diminuiamo n di q. Siccome la funzione inner non deve fare alcuna operazione sul risultato della chiamata ricorsiva il compilatore riconosce che non c'è bisogno di aggiornare lo stack.
È evidente che perdiamo leggermente in leggibilità in quanto abbiamo bisogno di definire una funzione che effettui la tail recursion per poi chiamarla con opportuni argomenti all’interno della funzione fattoriale.
Utilizzando la tail recursion possiamo effettuare delle ricorsioni mio profonde senza causare una stackoverflow exception tuttavia rinunciamo ad un'informazione importante come la call stack che può essere utile in caso di debugging delle applicazioni.