꼬리 재귀

위키백과, 우리 모두의 백과사전.
둘러보기로 가기 검색하러 가기

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

스칼라

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[1]

각주[편집]

  1. “Annotations | Scala Documentation”. 2018년 3월 4일에 확인함.