[코틀린을 다루는 기술] Kotlin에서의 재귀 함수 사용

이 글은 '길벗'사의 '코틀린을 다루는 기술'을 보고 작성한 글입니다.
더 자세한 내용은 해당 책에서 참고하시면 좋을 것 같습니다.

 

재귀와 공재귀, 꼬리 호출

만약, 팩토리얼 함수를 구현하다고 해볼까요?

fun factorial(n: Int): Long = if(n == 1) n.toLong() else n * factorial(n-1)
fun main() {
    val num = 10
    val result: Long = factorial(num)
    println("Factorial: $num -> $result")
}

일반적으로 알고 있는 재귀를 통해 팩토리얼을 구현하면 이런 형태가 될 것입니다. 하지만 현재 코드에서 팩토리얼은 10번 호출되고 이 함수의 문맥을 유지하기 위해 프로그램은 팩토리얼 함수가 가진 스택 메모리의 10배만큼을 더 사용하게 됩니다. 만약 num이 100, 1000이 되면 어떻게 될까요?

이런 문제를 해결하기 위해 공재귀를 사용하는데요. 공재귀는 재귀의 각 단계를 즉시 계산합니다. 즉, 계산을 한 번에 한 단계씩 수행합니다. 반면에, 재귀는 최종 조건에 도달할 때까지 계산이 미뤄지는 형식이죠. 그럼 위의 팩토리얼 함수를 공재귀로 바꿔보겠습니다.

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

어떤 부분이 달라졌는지 보이시나요? 재귀를 하는 함수에 파라미터를 추가로 뒀습니다. 이 파라미터는 재귀의 결과를 계산하고 다음 재귀로 넘기는 역할을 하죠. 따라서 이 함수는 스택 메모리가 누적되는 것이 아닌, 팩토리얼 함수가 정의된만큼 사용하게됩니다.

 

하지만 공재귀도 결국은 스택 공간을 사용하므로, 느리긴 하지만 언젠가는 스택 메모리를 고갈시킬 가능성이 있습니다. 이 문제를 제거하기 위해선 공재귀를 루프 형태로 바꾸는 것이 필요하다고 합니다.

 

꼬리재귀란?

이 장에서는 꼬리 재귀를 자주 언급합니다. 위키 백과에 의하면 꼬리 재귀는 재귀 함수를 호출할 때 스택을 재사용하면서 메모리를 과도하게 사용하지 않도록 최적화하는 방법이라고 합니다. 이 말은 꼬리 재귀와 공재귀가 같다는 것을 의미할까요?

꼬리재귀는 재귀 함수를 호출할 때, 재귀의 마지막(Tail)에 자기 자신을 호출하는 함수입니다. 만약 tailrec이라는 예약어를 붙이게 된다면, 이런 꼬리 재귀 호출을 루프 형태로 변환시켜줍니다. 이렇게함으로써 스택 메모리의 고갈을 방지할 수 있는 것이죠.

 

tailrec fun tailrecPrint(no: Int = 1, count: Int = 1) {
    println("tailrecPrint")
    return if(no == count) return else tailrecPrint(no - 1, count)
}

fun main(args: Array<String>) {
    tailrecPrint(3)
}

이러한 코드를 자바 코드로 디컴파일한다면?

public static final void tailrecPrint(int no, int count) {
    while(true) {
        String var2 = "tailrecPrint";
        System.out.println(var2);
        if (no == count) {
            return;
        }
        --no;
    }
}

위와 같이 루프 형태로 변환된 것을 확인할 수 있습니다.

 

참조 :
https://codechacha.com/ko/kotlin-tailrect/
https://skasha.tistory.com/54