Scala Language
Rekursion

Schwanzrekursion

Bei der regulären Rekursion wird bei jedem rekursiven Aufruf ein weiterer Eintrag in den Aufrufstapel verschoben. Wenn die Rekursion abgeschlossen ist, muss die Anwendung jeden Eintrag ganz nach unten ziehen. Wenn es viele rekursive Funktionsaufrufe gibt, kann dies zu einem riesigen Stack führen.

Scala entfernt automatisch die Rekursion, falls der rekursive Aufruf in Endposition gefunden wird. Die Annotation ( @tailrec ) kann zu rekursiven Funktionen hinzugefügt werden, um sicherzustellen, dass die Optimierung der @tailrec durchgeführt wird. Der Compiler zeigt dann eine Fehlermeldung an, wenn er Ihre Rekursion nicht optimieren kann.

Regelmäßige Rekursion

Dieses Beispiel ist nicht rekursiv, da die Funktion beim Aufruf des rekursiven Aufrufs die Multiplikation verfolgen muss, die sie mit dem Ergebnis zu tun hat, nachdem der Aufruf zurückgekehrt ist.

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

println(fact(5))

Der Funktionsaufruf mit dem Parameter führt zu einem Stack, der wie folgt aussieht:

(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

Wenn Sie versuchen, dieses Beispiel mit @tailrec zu kommentieren, wird die folgende Fehlermeldung could not optimize @tailrec annotated method fact: it contains a recursive call not in tail position

Schwanzrekursion

Bei der Tail-Rekursion führen Sie zuerst Ihre Berechnungen aus. Anschließend führen Sie den rekursiven Aufruf aus und übergeben die Ergebnisse Ihres aktuellen Schritts an den nächsten rekursiven Schritt.

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

Im Gegensatz dazu sieht die Stapelverfolgung für die rekursive Faktorsicht aus dem Schwanz folgendermaßen aus:

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

Es ist nur erforderlich, für jeden Aufruf von fact_inside die gleiche Datenmenge zu fact_inside da die Funktion einfach den Wert fact_inside den sie direkt nach oben erhalten hat. Das heißt, auch wenn fact_with_tail 1000000 aufgerufen wird, benötigt es nur so viel Platz wie fact_with_tail 3 . Dies ist bei einem nicht rekursiven Aufruf nicht der Fall, und große Werte können einen Stapelüberlauf verursachen.

Stapellose Rekursion mit Trampolin (scala.util.control.TailCalls)

Es ist sehr üblich, beim Aufrufen der rekursiven Funktion einen StackOverflowError Fehler zu erhalten. Die Scala-Standardbibliothek bietet TailCall an, um einen Stapelüberlauf zu vermeiden, indem Heap-Objekte und Fortsetzungen verwendet werden, um den lokalen Zustand der Rekursion zu speichern.

Zwei Beispiele aus dem scaladoc von 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