Scala에서 꼬리재귀와 트램폴린, Stream

함수형 = 재귀함수는 아니지만 재귀함수를 많이 사용한다는 것은 틀림없을 것이다.

하지만 컴퓨터 프로그램의 구조상 함수를 호출할 때마다 스택에 값들이 쌓여 StackOverFlow를 피할 수 없다. 

이 친숙한 스택오버플로를 피하기 위한 방법들이 있다.

꼬리재귀와 트램폴린, 지연 콜렉션 Stream이다. 사실 스트림은 스택오버플로를 피하기 위한 방법은 아니다.

하지만 스택오버플로가 발생할 수 있는 문제에서 스트림을 사용, 

더 이른 스택 복귀를 통해(혹은 다른 방법으로의 접근) 문제를 해결한 경험이 있어 함께 적어둔다.

1. 꼬리재귀(Tail Recursive)

꼬리재귀는 어떤 함수가 자기 자신을 호출하되 그 호출이 함수의 마지막 연산인 경우를 말한다.

꼬리재귀는 아주 쉽게 반복문으로 변경할 수 있다. 

많은 함수형 프로그래밍 언어들의 컴파일러는 꼬리재귀를 반복문으로 최적화해준다고 한다. 

JVM 자체에서는 꼬리 재귀에 대한 최적화를 지원하지 않지만 스칼라 컴파일러의 @tailrec 어노테이션을 통해 꼬리재귀를 최적화할 수 있다.

// StackOverFlow
def factorial(n: BigInt): BigInt = {
  if(n == 1) 1
  else n * factorial(n - 1)
}

@tailrec
def factorial(n: BigInt, result: BigInt = 1): BigInt = {
  if(n == 1) result
  else factorial(n-1, n * result)
}

모든 재귀를 꼬리재귀로 바꿀 수 있느냐에 대한 의문은 항상 남는다.

2. 트램폴린(Trampoline)

트램폴린은 여러 함수가 서로 다른 함수를 호출하면서 이어져 나가는 반복을 말한다.

함수 A가 함수 B를 호출하고, 함수 B는 다시 함수 A를 호출하는 재귀일 때 트램폴린을 이용해 반복문으로 변환할 수 있다.

TailCalls Object에 있는 요소들을 사용하여 최적화하는데 이를 사용하기 위해 패키지를 import하여야 한다.

import scala.util.control.TailCalls._

def funcA(n: Int): TailRec[Int] = {
  funcB(n+1)
}

def funcB(n: Int): TailRec[Int] = {
  if(n == 100) done(100)
  else funcA(n+1)
}

결과를 래핑된 TailRec 형태가 아닌 자료형 그대로 사용하기 위해서는 result 메소드를 사용하면 된다.

3. Stream

자바8에 추가된 Stream과 비슷한 스칼라의 Stream은 지연 평가(lazy evalution)를 통해 무한한 값을 표현할 수 있다. 그 뿐 아니라 head를 제외한 값의 계산을 미룸으로써 정말 필요한 값만을 계산하도록 도와준다.

scala> Stream(1, 2, 3, 4, 5) res1: scala.collection.immutable.Stream[Int] = Stream(1, ?)

(head만을 표시한다)

Scala Standard Library의 Stream 문서를 살펴보면 피보나치 수열을 통해 스트림의 강력함을 맛볼 수 있다. (편의상 약간 수정했다)

val fibs: Stream[Int] = 
  0 #:: 1 #:: fibs.zip(fibs.tail)
                  .map(n => n._1 + n._2)

fibs.take(5).foreach(println)

이렇게 메소드를 호출하여 5번째까지의 피보나치 수열을 출력한다고 생각해 보자.

식의 가장 오른쪽 fibs.zip(fibs.tail)... 부분이 #::로 되어 있는 것을 통해 가장 오른쪽 식이 Stream이라는 사실을 알 수 있다.

Stream(0, 1) #::: x

0, 1 다음 x의 값은  x = [0, 1] zip [1] map n._1 + n._2,   = (0, 1) map n._1 + n._2,   = [1], Stream은 (0, 1, 1)

하지만 고정된 콜렉션이 아닌 fibs로 자기 자신을 호출했기 때문에 

x가 1이 되는 순간 Stream의 값은 [0, 1]이 아닌 [0, 1, 1]이 된다. 따라서 tail은 [1, 1]이 된다. 따라서 [0, 1, 1] zip [1, 1] map n._1 + n._2 의 계산이 필요하다.  x는 [1, 2], Stream은 (0, 1, 1, 2)

하지만 2가 추가되었으므로 다시,

[0, 1, 1, 2] zip [1, 1, 2] map n._1 + n._2 x는 [1, 2, 3], Stream은 (0, 1, 1, 2, 3)

같은 작업이 계속 이어짐으로써 무한히 계산되는 피보나치 수열이 만들어진다.

또, Stream은 이전 계산을 기억하는 메모이제이션도 지원한다.

val fibs: Stream[Int] =
  0 #:: 1 #:: fibs.zip(fibs.tail).map(n => {
  println("Adding %d and %d".format(n._1, n._2))
  n._1 + n._2
})

fibs take 5 foreach println
println("And then prints")
fibs take 6 foreach println


// 0
// 1
// Adding 0 and 1
// 1
// Adding 1 and 1
// 2
// Adding 1 and 2
// 3

// And then prints
//
// 0
// 1
// 1
// 2
// 3
// Adding 2 and 3
// 5

앞서 살펴본 코드에 println 구문이 추가되어 있다.

주석으로 표시한 것처럼 fibs 함수를 다시 실행했을 때 새로 계산하지 않고

이전 계산했던 결과를 사용한다는 것을 알 수 있다. 이런 특징은 장점으로도 볼 수 있지만

때로 너무 많은 계산 결과를 가지고 있어 OutOfMemory를 발생시킬 수 있다. 

Stream은 굉장히 강력한 콜렉션이다. 

하지만 예시로 든 피보나치 수열처럼 쿨하게 만들 수 있는 경우는(혹은 방법은) 흔치않고 어렵다. 

이런 방법만이 아니라 이전 계산까지의 결과를 파라미터로 가지고 다음 값을 유도하는 재귀문으로도 사용할 수 있다. 

def fibs2: Stream[BigInt] = {
  def fibRecu(n2: BigInt = 0, n1: BigInt = 1): Stream[BigInt] = n2 #:: fibRecu(n1, n2+n1)
  
  fibRecu()
}

왼쪽 결과값을 오른쪽에 넣어 호출하는 오른쪽 재귀의 형태다. 

이런 형태의 활용법은 개미수열(읽고 말하기 수열) 문제와 Ninety-Nine Scala Problems의 91번 Knight's Tour 문제를 통해 익힐 수 있다.