Scala Language
ricorsione

Ricorsione di coda

Usando la ricorsione regolare, ogni chiamata ricorsiva spinge un'altra voce nello stack di chiamate. Quando la ricorsione è completata, l'applicazione deve far scattare ogni voce fino in fondo. Se ci sono molte chiamate ricorsive, può finire con uno stack enorme.

Scala rimuove automaticamente la ricorsione nel caso in cui trovi la chiamata ricorsiva in posizione di coda. L'annotazione ( @tailrec ) può essere aggiunta alle funzioni ricorsive per garantire che venga eseguita l'ottimizzazione delle chiamate tail. Il compilatore mostra quindi un messaggio di errore se non è in grado di ottimizzare la ricorsione.

Ricorsione regolare

Questo esempio non è ricorsivo di coda perché quando viene effettuata la chiamata ricorsiva, la funzione deve tenere traccia della moltiplicazione che deve fare con il risultato dopo il ritorno della chiamata.

def fact(i : Int) : Int = {
   if(i <= 1) i
   else i * fact(i-1)
}

println(fact(5))

La chiamata alla funzione con il parametro darà come risultato una pila simile a questa:

(fact 5)
(* 5 (fact 4))
(* 5 (* 4 (fact 3)))
(* 5 (* 4 (* 3 (fact 2))))
(* 5 (* 4 (* 3 (* 2 (fact 1)))))
(* 5 (* 4 (* 3 (* 2 (* 1 (fact 0))))))
(* 5 (* 4 (* 3 (* 2 (* 1 * 1)))))
(* 5 (* 4 (* 3 (* 2))))
(* 5 (* 4 (* 6)))
(* 5 (* 24))
120

Se proviamo ad annotare questo esempio con @tailrec , otterremo il seguente messaggio di errore: could not optimize @tailrec annotated method fact: it contains a recursive call not in tail position

Ricorsione di coda

Nella ricorsione di coda, si eseguono prima i calcoli e quindi si esegue la chiamata ricorsiva, passando i risultati del passaggio corrente al successivo passo ricorsivo.

def fact_with_tailrec(i : Int) : Long = {
   @tailrec
   def fact_inside(i : Int, sum: Long) : Long = {
      if(i <= 1) sum
      else fact_inside(i-1,sum*i)
   }
   fact_inside(i,1)
}

println(fact_with_tailrec(5))

Al contrario, la traccia dello stack per il fattoriale ricorsivo della coda ha il seguente aspetto:

(fact_with_tailrec 5)
(fact_inside 5 1)
(fact_inside 4 5)
(fact_inside 3 20)
(fact_inside 2 60)
(fact_inside 1 120)

C'è solo la necessità di tenere traccia della stessa quantità di dati per ogni chiamata a fact_inside perché la funzione sta semplicemente restituendo il valore che ha ottenuto fino in cima. Ciò significa che anche se viene chiamato fact_with_tail 1000000 , è necessaria solo la stessa quantità di spazio di fact_with_tail 3 . Questo non è il caso con la chiamata non ricorsiva alla coda e in quanto tali valori di grandi dimensioni possono causare un overflow dello stack.

Ricorsione senza pila con trampolino (scala.util.control.TailCalls)

È molto comune ottenere un errore StackOverflowError mentre si chiama la funzione ricorsiva. La libreria standard di Scala offre TailCall per evitare l'overflow dello stack utilizzando oggetti heap e continuazioni per memorizzare lo stato locale della ricorsione.

Due esempi dallo scaladoc di TailCalls

import scala.util.control.TailCalls._
    
def isEven(xs: List[Int]): TailRec[Boolean] =
  if (xs.isEmpty) done(true) else tailcall(isOdd(xs.tail))
    
def isOdd(xs: List[Int]): TailRec[Boolean] =
  if (xs.isEmpty) done(false) else tailcall(isEven(xs.tail))

// Does this List contain an even number of elements?
isEven((1 to 100000).toList).result

def fib(n: Int): TailRec[Int] =
  if (n < 2) done(n) else for {
    x <- tailcall(fib(n - 1))
    y <- tailcall(fib(n - 2))
  } yield (x + y)

// What is the 40th entry of the Fibonacci series?
fib(40).result