Scala Language
Recursion

Recursion de cola

Usando la recursión regular, cada llamada recursiva inserta otra entrada en la pila de llamadas. Cuando se completa la recursión, la aplicación tiene que quitar cada entrada por completo hacia abajo. Si hay muchas llamadas a funciones recursivas, puede terminar con una pila enorme.

Scala elimina automáticamente la recursión en caso de que encuentre la llamada recursiva en la posición de cola. La anotación ( @tailrec ) se puede agregar a las funciones recursivas para garantizar que se realice la optimización de la llamada de cola. El compilador luego muestra un mensaje de error si no puede optimizar su recursión.

Recursion regular

Este ejemplo no es recursivo de cola porque cuando se realiza la llamada recursiva, la función debe realizar un seguimiento de la multiplicación que debe hacer con el resultado después de que se devuelve la llamada.

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

println(fact(5))

La llamada a la función con el parámetro dará como resultado una pila que se verá así:

(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

Si intentamos anotar este ejemplo con @tailrec , obtendremos el siguiente mensaje de error: could not optimize @tailrec annotated method fact: it contains a recursive call not in tail position

Recursion de cola

En la recursión de cola, primero realiza sus cálculos y luego ejecuta la llamada recursiva, pasando los resultados de su paso actual al siguiente paso recursivo.

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))

En contraste, la traza de la pila para el factorial recursivo de la cola se parece a lo siguiente:

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

Solo existe la necesidad de realizar un seguimiento de la misma cantidad de datos para cada llamada a fact_inside porque la función simplemente está devolviendo el valor que llegó a la parte superior. Esto significa que incluso si se llama a fact_with_tail 1000000 , solo se necesita la misma cantidad de espacio que fact_with_tail 3 . Este no es el caso con la llamada no recursiva de cola, y como tales valores grandes pueden causar un desbordamiento de pila.

Recursión sin pila con trampolín (scala.util.control.TailCalls)

Es muy común obtener un error StackOverflowError al llamar a la función recursiva. La biblioteca estándar de Scala ofrece TailCall para evitar el desbordamiento de pila mediante el uso de objetos de montón y continuaciones para almacenar el estado local de la recursión.

Dos ejemplos del scaladoc de 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