Scala Language
Herhaling

Staart recursie

Met behulp van reguliere recursie, duwt elke recursieve oproep een andere vermelding op de oproepstapel. Wanneer de recursie is voltooid, moet de toepassing elk item helemaal naar beneden verwijderen. Als er veel recursieve functie-aanroepen zijn, kan dit een enorme stapel opleveren.

Scala verwijdert automatisch de recursie voor het geval de recursieve oproep in staartpositie wordt gevonden. De annotatie ( @tailrec ) kan worden toegevoegd aan recursieve functies om ervoor te zorgen dat optimalisatie van staartoproepen wordt uitgevoerd. De compiler geeft vervolgens een foutmelding weer als deze uw recursie niet kan optimaliseren.

Regelmatige recursie

Dit voorbeeld is niet recursief, omdat wanneer de recursieve oproep wordt gedaan, de functie de vermenigvuldiging moet bijhouden die het moet doen met het resultaat nadat de oproep is teruggekomen.

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

println(fact(5))

De functieaanroep met de parameter resulteert in een stapel die er als volgt uitziet:

(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

Als we proberen dit voorbeeld te annoteren met @tailrec , krijgen we het volgende foutbericht: could not optimize @tailrec annotated method fact: it contains a recursive call not in tail position met @tailrec could not optimize @tailrec annotated method fact: it contains a recursive call not in tail position

Staart recursie

Bij staartrecursie voert u eerst uw berekeningen uit en voert u vervolgens de recursieve aanroep uit, waarbij u de resultaten van uw huidige stap doorgeeft aan de volgende recursieve stap.

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

Het stack-trace voor de staartrecursieve faculteit ziet er daarentegen als volgt uit:

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

Het is alleen nodig om voor elke aanroep van fact_inside dezelfde hoeveelheid gegevens bij te fact_inside omdat de functie eenvoudigweg de waarde die het helemaal heeft bereikt, fact_inside . Dit betekent dat zelfs als fact_with_tail 1000000 wordt genoemd, het slechts dezelfde hoeveelheid ruimte nodig heeft als fact_with_tail 3 . Dit is niet het geval met de niet-staart-recursieve aanroep en als zodanig kunnen grote waarden een stapeloverloop veroorzaken.

Stackless recursie met trampoline (scala.util.control.TailCalls)

Het is heel gebruikelijk om een StackOverflowError fout te krijgen tijdens het aanroepen van de recursieve functie. Standaard Scala-bibliotheek biedt TailCall om stapeloverloop te voorkomen door heap-objecten en continuaties te gebruiken om de lokale status van de recursie op te slaan.

Twee voorbeelden uit de scaladoc van 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