[Kotlin] 꼬리 재귀 함수

재귀 (Recursive)

재귀 함수는 특정 조건이 반복되면 자신을 호출하는 함수다. 재귀 함수의 가장 대표적인 예로 특정 수의 factorial 를 구하는 식이 있습니다.

fun factorial(n: Int, acc: Int): Int {
    return if (n <= 0) {
        acc
    } else {
        factorial(n-1, n*acc)
    }
}

위 코드는 매우 간결하지만 성능적으로 효율적인 코드는 아니다. 숫자가 커질 수록 call stack이 계속 쌓이게 되며 성능이 떨어지며 Call stack이 한계치까지 도달하면 Stack over flow 에러 를 발생시킬수 있는 다분히 위험한 코드입니다.

tailrec

코틀린에는 위와 같은 재귀 알고리즘을 반복문으로 변경해주는 기능을 제공한다. 따라서 성능 저하 및 Stack over flow 에러를 회피할 수 있게 됩니다.. 함수 앞에 tailrec 키워드를 붙이게 되면 코틀린 컴파일러가 컴파일시 위의 재귀 함수를 아래와 같이 반복문으로 변경해줍니다.

public static final int factorial(int n, int acc) {
    for (int n2 = n; n2 > 0; n2--) {
        acc *= n2;
    }
    return acc;
}

tailrec 를 사용할 때 조심해야 할 점은 재귀를 호출하는 코드에 추가적인 연산이 포함이 되면 안된다는 것입니다.

tailrec fun fact(k : Int) : Int {
  if (k==0) return 1
  else return k * fact(k-1)
}

컴파일을 하게 되면 아래와 같이 워닝이 발생합니다.

w: C:\Users\rlawj\IdeaProjects\DesignPattern\src\main\kotlin\ClassTest.kt: (8, 1): A function is marked as tail-recursive but no tail calls are found
w: C:\Users\rlawj\IdeaProjects\DesignPattern\src\main\kotlin\ClassTest.kt: (12, 13): Recursive call is not a tail call

이 말의 즉슨 위 코드는 반복문으로 변환되지 않는다는 것입니다.

위 코드를 해결하기 위해 아래와 같이 수정하여 문제를 해결할수 있습니다.

fun fact(k : Int) : Int {
    tailrec fun factTail(m : Int, n : Int) : Int {
        return if (m == 0) n
        else factTail(m -1, m * n)
    }
    return factTail(k, 1)
}

Reference

코틀린 프로그래밍