꼬리 재귀와 Trampoline In Scala

def unsafeSum(n: Int): Int =  
  if (n == 1) 1  
  else n + unsafeSum(n - 1)  
  
println(s"sum = ${unsafeSum(100000)}")

// 실행결과
// Exception in thread "main" java.lang.StackOverflowError
//     at dogs.MyApp$.unsafeSum(Main.scala:8)
//     at dogs.MyApp$.unsafeSum(Main.scala:8)
//     at dogs.MyApp$.unsafeSum(Main.scala:8)
//     at dogs.MyApp$.unsafeSum(Main.scala:8)

def safeSum(n: Int, acc: Int): Int =  
  if (n == 0) acc  
  else safeSum(n - 1, n + acc)  
  
println(s"sum = ${safeSum(100000, 0)}")

// 실행결과
// sum = 705082704

def safeSum_optimized(initial_n: Int, initial_acc: Int): Int = {  
  var n = initial_n  
  var acc = initial_acc  
  
  while (true) {  
    if (n == 0)  
      return acc  
    else {  
      val next_n = n - 1  
      val next_acc = n + acc  
      n = next_n  
      acc = next_acc  
    }  
  }  
  
  ??? // Not reachable  
}

import scala.annotation.tailrec  
  
@tailrec // 꼬리재귀가 아니므로 컴파일에러  
def unsafeSum(n: Int): Int =  
  if (n == 1) 1  
  else n + unsafeSum(n - 1)  
  
@tailrec
def safeSum(n: Int, acc: Int): Int =  
  if (n == 0) acc  
  else safeSum(n - 1, n + acc)

// 함수를 추상화한 것입니다.
trait Function

// 값을 리턴함을 의미합니다.
case class Return(value: Int) extends Function
// 다른 함수의 호출을 의미합니다. 호출할 함수는 lazy 하게 얻어집니다.
case class LazyCall(getFunc: () => Function) extends Function
// 실제 로직을 의미합니다. 주어진 func 를 호출후 그 결과에 대해서 postFunc 를 실행하는 것을 의미합니다.
case class Logic(func: Function, postFunc: Int => Function) extends Function

// 함수를 해석/실행하여 값을 반환하는 역할을 합니다. (꼬리재귀를 만족함을 알 수 있습니다.)
@tailrec
def run(function: Function): Int =
  function match {
    case Return(value) => value
    case LazyCall(getFunc) => run(getFunc())
    case Logic(func, postFunc) =>
      // 논리적으로 func -> postFunc 순으로 실행되야합니다.
      // run(postFunc(run(func)) 처럼 하면 꼬리재귀를 만족시킬 수 없기 때문에 아래와 같이 해야합니다.
      func match {
        // Logic 안의 func 가 Return 인 경우는 리턴값에 대하여 postFunc 를 바로 호출해주면 됩니다.
        case Return(value) => run(postFunc(value))
        // Logic 안의 func 가 LazyCall 인 경우는 getFunc 를 호출하므로써 laziness 만 없애줍니다.
        case LazyCall(getFunc) => run(Logic(getFunc(), postFunc))
        // Logic 안에 Logic 이 있는 경우에는 두 개의 Logic 을 이어붙여주면 됩니다.
        case Logic(_func, _postFunc) =>
          // 논리적으로 _func -> _postFunc -> postFunc 순으로 실행되야합니다.
          run(Logic(
            _func,
            result => Logic(_postFunc(result), postFunc)
          ))
      }
  }

// 결과를 반환하는 것이 아니라 함수를 추상화한 객체를 반환합니다.
def sum(n: Int): Function =
  if (n == 1)
    Return(1)
  else
    Logic(
      // LazyCall 이 () => Function 을 인자로 받기 때문에 여기서 재귀호출이 발생하지 않습니다.
      LazyCall(() => sum(n - 1)),
      result => Return(n + result)
    )

def factorial(n: Int): Function =
  if (n == 1)
    Return(1)
  else
    Logic(
      LazyCall(() => factorial(n - 1)),
      result => Return(n * result)
    )

def fibo(n: Int): Function =
  if (n < 2)
    Return(n)
  else
    Logic(
      // 1. fibo(n - 1) 의 값을 먼저 구한다음, 
      LazyCall(() => fibo(n - 1)),
      firstResult =>
        Logic(
          // 2. 그다음으로 fibo(n - 2) 의 값을 구하고,
          LazyCall(() => fibo(n - 2)),
          // 3. 1번과 2번의 결과를 더한 값을 반환한다.
          secondResult => Return(firstResult + secondResult)
        )
    )

import scala.util.control.TailCalls._

def sum(n: Int): TailRec[Int] =
  if (n == 1) done(1)
  else tailcall(sum(n - 1).map(_ + n))

def factorial(n: Int): TailRec[Int] =
  if (n == 1) done(1)
  else tailcall(factorial(n - 1).map(_ * n))

def fibo(n: Int): TailRec[Int] =
  if (n < 2) done(n)
  else tailcall(
    for {
      firstResult  <- factorial(n - 1)
      secondResult <- factorial(n - 2)
    } yield firstResult + secondResult
  )

println(sum(100000).result)