Kotlin - 재귀함수로 Factorial 구현하기

Factorial은 n!으로 표현하며 1부터 n까지의 숫자를 모두 곱하는 것입니다.

 n! = 1 * 2 * 3 * .... (n-1) * n

루프를 이용한 구현

간단히 루프를 이용하여 factorial을 구현할 수 있습니다. 아래 코드는 n만큼 루프를 돌고 숫자를 모두 곱해주었습니다. 변수명 acc는 accumulation의 약자로 축적된 값을 의미합니다

fun factorialLoop(n: Int): Int {
    var acc = 1
    for (number in 1..n) {
        acc *= number
    }
    return acc
}

println("loop - factorial(10) : ${factorialLoop(10)}" )

# 결과
loop - factorial(10) : 3628800

재귀함수를 이용한 구현

factorial은 재귀로도 구현할 수 있습니다. acc는 축적된 값을 의미하며 1부터 시작합니다. n번의 계산을 하면 되기 때문에 재귀함수로 factorial함수가 n번 호출되도록 하였습니다. 계산된 값은 다음 호출로 전달되며 결과를 리턴하게 됩니다.

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

println("recursion - factorial(10): ${factorial(10, 1)}" )

# 결과
recursion - factorial(10): 3628800

tailrec을 이용하여 성능 개선

tailrec은 꼬리재귀를 의미하며, 꼬리재귀인 함수에 이 키워드를 붙여주면, 코드가 빌드될 때 루프 형태로 변환됩니다. 즉, 구현은 재귀로 하지만 실제로 동작하는 것은 루프입니다. 재귀함수가 호출될 때마다 스택이 소모되어 성능에 좋지는 않습니다. 재귀로 구현하는 것이 편하신 분은 이 키워드를 사용하는 것이 재귀함수의 성능 문제를 해결할 수 있습니다. 하지만 이 키워드는 꼬리재귀에 대한 것만 가능합니다.

이렇게 키워드를 사용할 수 있습니다.

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

tailrec에 대한 자세한 내용은 Kotlin - tailrec(꼬리재귀)에 대해서 알아보기 를 참고해주세요.