Scala Language
Rekursion

Rekursion för svans

Med hjälp av regelbunden rekursion skjuter varje rekursivt samtal en annan post till samtalstacken. När rekursionen är klar måste applikationen visa varje inlägg helt tillbaka. Om det finns mycket rekursiva funktionssamtal kan det sluta med en enorm stack.

Scala tar bort rekursionen automatiskt om den hittar det rekursiva samtalet i svansläge. Annotationen ( @tailrec ) kan läggas till rekursiva funktioner för att se till att optimering av svanssamtal utförs. Kompilatorn visar sedan ett felmeddelande om den inte kan optimera din rekursion.

Regelbunden rekursion

Det här exemplet är inte rekursivt med svansen eftersom när det rekursiva samtalet görs måste funktionen hålla reda på multiplikationen som den behöver göra med resultatet efter att samtalet återgår.

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

println(fact(5))

Funktionssamtalet med parametern resulterar i en bunt som ser ut så här:

(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

Om vi försöker kommentera detta exempel med @tailrec vi följande felmeddelande: could not optimize @tailrec annotated method fact: it contains a recursive call not in tail position

Rekursion för svans

I svansrekursion utför du först dina beräkningar och sedan utför du det rekursiva samtalet och överför resultaten från ditt nuvarande steg till nästa rekursiva steg.

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

Däremot ser stapelspåret för den rekursiva faktorns svans ut på följande sätt:

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

Det finns bara behovet av att hålla reda på samma mängd data för varje samtal till fact_inside eftersom funktionen helt enkelt returnerar värdet som den fick till toppen. Detta betyder att även om fact_with_tail 1000000 kallas, behöver den bara samma mängd utrymme som fact_with_tail 3 . Detta är inte fallet med det icke-svansrekursiva samtalet, och eftersom sådana stora värden kan orsaka ett stacköverskridande.

Stapell rekursion med trampolin (scala.util.control.TailCalls)

Det är mycket vanligt att få ett StackOverflowError fel när du kallar rekursiv funktion. Scala standardbibliotek erbjuder TailCall för att undvika översvämning av staplar genom att använda högobjekt och fortsättningar för att lagra rekursionens lokala tillstånd.

Två exempel från scaladoc från 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