Scala Language
Rekurencja

Rekurencja ogona

Używając zwykłej rekurencji, każde wywołanie rekurencyjne wypycha kolejny wpis na stos wywołań. Po zakończeniu rekursji aplikacja musi usunąć wszystkie wpisy z powrotem do końca. Jeśli istnieje wiele wywołań funkcji rekurencyjnych, może to zakończyć się ogromnym stosem.

Scala automatycznie usuwa rekurencję w przypadku znalezienia rekurencyjnego połączenia w pozycji ogona. Adnotację ( @tailrec ) można dodać do funkcji rekurencyjnych, aby zapewnić optymalizację wywołania ogona. Następnie kompilator wyświetla komunikat o błędzie, jeśli nie może zoptymalizować rekurencji.

Regularna rekurencja

Ten przykład nie jest rekurencyjny, ponieważ po wykonaniu wywołania rekurencyjnego funkcja musi śledzić mnożenie, które musi zrobić z wynikiem po powrocie połączenia.

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

println(fact(5))

Wywołanie funkcji z parametrem spowoduje, że stos będzie wyglądał następująco:

(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

Jeśli spróbujemy @tailrec adnotację do tego przykładu za pomocą @tailrec , otrzymamy następujący komunikat o błędzie: could not optimize @tailrec annotated method fact: it contains a recursive call not in tail position

Rekurencja ogona

W rekursji ogona najpierw wykonuje się obliczenia, a następnie wykonuje wywołanie rekurencyjne, przekazując wyniki bieżącego kroku do następnego kroku rekurencyjnego.

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

W przeciwieństwie do tego, ślad stosu dla rekurencyjnej silni rekurencyjnej wygląda następująco:

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

Konieczne jest jedynie śledzenie tej samej ilości danych dla każdego wywołania fact_inside ponieważ funkcja po prostu zwraca wartość, którą dostała na sam szczyt. Oznacza to, że nawet jeśli zostanie fact_with_tail 1000000 , potrzebuje tylko tyle samo miejsca co fact_with_tail 3 . Nie dzieje się tak w przypadku wywołania nie rekurencyjnego i jako takie duże wartości mogą spowodować przepełnienie stosu.

Rekurencja bez stosu z trampoliną (scala.util.control.TailCalls)

Podczas wywoływania funkcji rekurencyjnej bardzo często występuje błąd StackOverflowError . Standardowa biblioteka Scala oferuje TailCall, aby uniknąć przepełnienia stosu, używając obiektów i kontynuacji do przechowywania lokalnego stanu rekurencji.

Dwa przykłady ze skaladoku 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