Scala Language
Récursivité

Récursion de la queue

En utilisant la récursivité régulière, chaque appel récursif pousse une autre entrée sur la pile d'appels. Lorsque la récursivité est terminée, l'application doit désactiver chaque entrée. S'il y a beaucoup d'appels de fonctions récursives, cela peut aboutir à une énorme pile.

Scala supprime automatiquement la récursivité au cas où elle trouve l'appel récursif en position de queue. L'annotation ( @tailrec ) peut être ajoutée aux fonctions récursives pour garantir que l'optimisation de l'appel de la queue est effectuée. Le compilateur affiche alors un message d'erreur s'il ne peut pas optimiser votre récursivité.

Récursion régulière

Cet exemple n'est pas récursif en queue car lorsque l'appel récursif est effectué, la fonction doit garder une trace de la multiplication nécessaire avec le résultat après le retour de l'appel.

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

println(fact(5))

L'appel de fonction avec le paramètre entraînera une pile qui ressemble à ceci:

(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 nous essayons d’annoter cet exemple avec @tailrec nous aurons le message d’erreur suivant: could not optimize @tailrec annotated method fact: it contains a recursive call not in tail position

Récursion de la queue

En récursivité, vous effectuez d'abord vos calculs, puis vous exécutez l'appel récursif, en passant les résultats de votre étape actuelle à l'étape récursive suivante.

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 revanche, la trace de la pile pour la factorielle récursive de la queue ressemble à ceci:

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

Il suffit de garder la trace de la même quantité de données pour chaque appel à fact_inside car la fonction renvoie simplement la valeur qui lui a été fact_inside . Cela signifie que même si fact_with_tail 1000000 est appelé, il ne nécessite que la même quantité d'espace que fact_with_tail 3 . Ce n'est pas le cas avec l'appel non récursif, et de telles valeurs peuvent provoquer un débordement de pile.

Récursivité sans empilement avec trampoline (scala.util.control.TailCalls)

Il est très courant d'obtenir une erreur StackOverflowError lors de l'appel d'une fonction récursive. La bibliothèque standard Scala offre TailCall pour éviter le débordement de la pile en utilisant des objets de pile et des continuations pour stocker l'état local de la récursivité.

Deux exemples du 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