[Kotlin]tailrec(꼬리재귀)

tailrec이란?

tailrec은 꼬리재귀(tail recursive)라는 의미로, 추가적인 연산이 없이 자신 스스로 재귀적으로 호출하다가 어떤 값을 리턴하는 함수를 의미

자신만 반복적으로 호출하는 재귀함수(tailrec)는 while과 같이 루프를 사용하는 코드로 변환이 가능함.

• 재귀함수가 호출되면서 소비되는 스택을 아낄 수 있음 (스택이 각 중간 재귀 상태를 추적할 필요가 없음)
• 루프는 동일한 결과를 출력하면서 재귀함수보다 더 적은 자원을 사용

 

재귀함수와 꼬리재귀

팩토리얼을 재귀함수로 구현해보자!

fun factorial(n: Int): Int {
    return when (n) {
        1 -> n
        else -> n * factorial(n-1)  // 재귀 호출
    }
}

재귀함수를 꼬리재귀로 작성해보자!

tailrec fun factorial (n: Int, acc: Int = 1): Int {
    return when (n) {
        1 -> acc
        else -> factorial(n-1, acc*n)   // 재귀함수가 스스로 자신만을 호출하다 값을 리턴함
    }
}

재귀를 호출할 때 추가적인 연산이 필요하다면? 일반 재귀함수

재귀를 호출할 때 자신만을 반복적으로 호출한다면? 꼬리 재귀함수

 

유의사항

함수에 'tailrec'이라는 키워드를 붙이면 꼬리재귀가 선언된다.

하지만 꼬리재귀가 아닌 함수에 tailrec 키워드를 붙이면 컴파일을 할 때, 루프 코드로 변경되지 않는다. (꼬리재귀가 아니기 때문)