꼬리 재귀

꼬리 재귀는 재귀 함수를 호출할 때 스택을 재사용하면서 메모리를 과도하게 사용하지 않도록 최적화하는 방법이다.

스칼라

import scala.annotation.tailrec

// 예제 1 - 꼬리재귀 팩토리얼
def factorial(x: Int): Int = {

 @tailrec
 def factorialHelper(x: Int, accumulator: Int): Int =
   if (x == 1) accumulator else factorialHelper(x - 1, accumulator * x)

 factorialHelper(x, 1)
}

// 예제 2 - 꼬리재귀 피보나치
def fibonacci(x: Int): Int = {

  @tailrec
  def fibonacciHelper(x: Int, a: Int, b: Int): Int =
    if(x == 0) a else fibonacciHelper(x - 1, b, a + b)

  fibonacciHelper(x, 0, 1)
}

참고

Scala annotation example - @tailrec