Scala Language
재귀

꼬리 재귀

정규 재귀를 사용하면 각 재귀 호출은 다른 항목을 호출 스택에 푸시합니다. 재귀가 완료되면 응용 프로그램에서 각 항목을 다시 팝 어라운드해야합니다. 많은 재귀 함수 호출이 있으면 거대한 스택으로 끝날 수 있습니다.

스칼라는 꼬리 위치에서 재귀 호출을 찾으면 자동으로 재귀를 제거합니다. 꼬리 호출 최적화가 수행되도록 주석 ( @tailrec )을 재귀 함수에 추가 할 수 있습니다. 컴파일러는 재귀를 최적화 할 수없는 경우 오류 메시지를 표시합니다.

정규 재귀

재귀 호출이 만들어지면 함수는 호출이 반환 된 후에 결과와 관련된 곱셈을 추적해야하기 때문에이 예제는 꼬리 재귀가 아닙니다.

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

println(fact(5))

매개 변수를 사용하는 함수 호출은 다음과 같은 스택을 생성합니다.

(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

이 예제에 @tailrec 으로 주석을 추가하려고하면 다음 오류 메시지가 나타납니다. could not optimize @tailrec annotated method fact: it contains a recursive call not in tail position

꼬리 재귀

꼬리 재귀에서는 먼저 계산을 수행 한 다음 재귀 호출을 실행하여 현재 단계의 결과를 다음 재귀 단계로 전달합니다.

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

반대로 꼬리 재귀 팩토리얼에 대한 스택 추적은 다음과 같습니다.

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

fact_inside 호출 할 때마다 동일한 양의 데이터를 추적 할 필요가 있습니다. 왜냐하면 함수가 단순히 바로 위에있는 값을 반환하기 때문입니다. 즉, fact_with_tail 1000000 이 호출 fact_with_tail 3 과 같은 양의 공간 만 필요합니다. 이것은 비 꼬리 재귀 호출과 관련이 없으므로 큰 값으로 인해 스택 오버플로가 발생할 수 있습니다.

트램펄린으로 스택리스 재귀 (scala.util.control.TailCalls)

재귀 함수를 호출하는 동안 StackOverflowError 오류를 얻는 것은 매우 일반적입니다. 스칼라 표준 라이브러리는 힙 개체 및 연속을 사용하여 재귀의 로컬 상태를 저장함으로써 스택 오버플로를 피하기 위해 TailCall 을 제공합니다.

TailCalls의 scaladoc 에서 나온 두 가지 예

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