꼬리 재귀 함수

정의

재귀함수의 최적화 방법

원리

재귀 함수시, 함수에 계산해야할 나머지 명령어가 남아 있다면, 스택 메모리에 그대로 함수가 기다리게 됨, 이와는 반대로 이후에 계산할게 없다면, 스택메모리에 함수를 남기지 않아도 되므로, 최적화가 가능함. 이를 꼬리 재귀함수Tail Recursion 라고 부름

꼬리 재귀 함수 Tail Recursion
꼬리 호출 제거 tail call elimination
꼬리 호출 최적화 tail calll optimization

How to

재귀함수의 리턴부분에 함수 호출이 아닌 다른 연산자가 붙지 않도록 만듭니다.

컴파일러

원리 특성상, 컴파일러, 즉 사용 언어에서 지원을 해주어야 사용 가능함.
C++, C#, Kotlin, Swift은 꼬리 재귀 최적화를 지원하며, Scala는 JVM 위에서 동작하는데, 꼬리 재귀 최적화를 지원함.
Java는 꼬리 재귀 최적화를 지원하지 않음.

예제-factorial calculation, Kotlin

재귀함수

Kotlin

fun main() {
    println(TailFactorialRecursive(5, 1))
    println(NormalFactorialRecursive(5))
}

tailrec fun TailFactorialRecursive(n: Int, sum: Int): Int {
    if (n == 1) {
        return sum
    }
    return TailFactorialRecursive(n - 1, n * sum)
}


fun NormalFactorialRecursive(n: Int): Int {
    if (n == 1) {
        return 1
    }
    return n * NormalFactorialRecursive(n - 1)
}

Explaination

NormalFactorialRecursive는 보통 재귀함수이며 n * NormalFactorialRecursive(n - 1)를 리턴 합니다.
TailFactorialRecursive는 꼬리 재귀함수이며, FactorialRecursive(n - 1, n * sum)를 리턴합니다.