Tail recursion

Cos'è la tail recursion

Un'operazione tail recursive è una ricorsione in cui non devono essere svolti altri calcoli nelle chiamate intermedie al ritorno della ricorsione.

A cosa serve

La tail recursion (o ricorsione di coda) è una tecnica di programmazione per risparmiare lo spazio di memoria usato per memorizzare i valori intermedi di ogni chiamata ricorsiva.

Come funziona

I valori parziali della ricorsione sono memorizzati in uno spazio accumulatore. Ogni chiamata ricorsiva accede e modifica il valore parziale nello stesso spazio.

Esempio

Per comprendere la tail recursion faccio un esempio pratico usando il linguaggio funzionale Ocaml.

Questo script calcola il fattoriale di un numero.

let rec fattoriale (n) =
match n with
1 -> 1
| _ -> n*fattoriale(n-1)

Per calcolare il fattoriale di 5

fattoriale(5)

Lo script svolge n=5 ricorsioni

fattoriale(5)
5*fattoriale(4)
4*fattoriale(3)
3*fattoriale(2)
2*fattoriale(1)
1

In ogni ricorsione resta in sospeso il calcolo parziale che deve essere memorizzato in uno spazio di memoria diverso.

Quindi, complessivamente la ricorsione utilizza n=5 indirizzi dello spazio memoria.

In generale lo spazio di memoria usato da questa ricorsione per calcolare il fattoriale di un generico numero n è proporzionale a n.

Lo stesso risultato posso ottenerlo con uno spazio di memoria inferiore tramite la tail recursion.

let rec fattoriale (n,acc) =
match n with
1 -> acc
| _ -> fattoriale(n-1,n*acc)

In questo caso il risultato parziale viene trasmesso tramite la variabile acc (spazio accumulatore) in ogni ricorsione.

Quindi, al termine della ricorsione non devono essere svolti altri calcoli.

Ad esempio, calcolo il fattoriale di 5

fattoriale (5,1)
fattoriale (4,1*5)
fattoriale (3,1*5*4)
fattoriale (2,1*5*4*3)
fattoriale (1,1*5*4*3*2)

La ricorsione passa come parametro una coppia di valori composta dal numero su cui calcolare fattoriale (n) e dai prodotti già calcolati sui successori (acc)

Complessivamente sono usati sempre due indirizzi di memoria.

Anche se ci fossero un milione di chiamate ricorsive, lo spazio usato per memorizzare i risultati parziali è sempre n=2 ossia la variabile acc e la variabile n.

Pur essendo un processo ricorsivo ha la stessa complessità spaziale di un processo iterativo.

E così via.