[Kotlin] 재귀 함수를 꼬리 재귀 함수로 변환하여 최적화하는 방법 (tailrec 사용)

꼬리 재귀 함수와 tailrec 설명 바로 가기

 

예제 1: 정수 리스트에 들어 있는 모든 원소의 합계를 구하는 함수

• 먼저 간단하게 구현하면 다음과 같다.

  • fun sum(list: List<Int>): Int = if (list.isEmpty()) 0 else list[0] + sum(list.drop(1))

  • 코드는 간단하지만 빈 리스트를 만날 때까지 스택에 메모리가 계속 쌓이게 된다.
  • 이 함수는 꼬리 재귀가 아니기 때문에 tailrec 키워드를 붙일 수 없고, 리스트 인자가 몇천 개 이상이면 이 함수를 사용할 수 없다.
• 이 함수를 꼬리 재귀 함수로 만들어보자.

  • fun sum(list: List<Int>): Int {
        tailrec fun sum_(list: List<Int>, acc: Int): Int =
            if (list.isEmpty())
                acc
            else
                sum_(list.drop(1), acc + list[0])
    
        return sum_(list, 0)
    }

  • sum_ 도우미 함수는 꼬리 재귀 함수이므로 TCE를 통해 최적화가 가능하다. 
  • 참고: 내부 도우미 함수 네이밍
    
    • 1. go, process 같은 이름으로 통일
    • 2. sum_처럼 주 함수 이름 뒤에 밑줄을 붙이기
    • 어떤 방식이든 항상 일관성을 지키는 것이 중요

 

 

예제 2: 피보나치 수열을 구하는 함수

• 먼저 이중 재귀 함수로 간단하게 구현해보자.

  • fun fibonacci(number: Int): Int =
        if (number <= 1)
            1
        else
            fibonacci(number - 2) + fibonacci(number - 1)

  • 위 함수는 한 번 호출될 때마다 재귀 호출이 두 개씩 더 생긴다. 
  • 즉, f(n)을 계산하려면 $2^n$ 개의 재귀 호출이 발생한다.
• 사용할 수 있는 피보나치 함수를 만들려면 이 함수가 꼬리 재귀를 단 하나만 사용하도록 바꿔야 한다.
• 또한, n이 조금만 커져도 f(n) 값이 너무 커지기 때문에 큰 값을 처리하는 파라미터 타입으로 변경해 줘야 한다.
• 꼬리 재귀 버전의 피보나치 함수:

  • fun fibonacci(number: Int): BigInteger {
        tailrec fun fibonacci_(val1: BigInteger, val2: BigInteger, x: BigInteger): BigInteger =
            when {
                x == BigInteger.ZERO -> BigInteger.ONE
                x == BigInteger.ONE -> val1+val2
                else -> fibonacci_(val2, val1 + val2, x - BigInteger.ONE)
            }
    
        return fibonacci_(BigInteger.ZERO, BigInteger.ONE, BigInteger.valueOf(number.toLong()))
    }

  • 다음과 같이 이중 재귀를 단일 공재귀로 바꿈으로써 성능이 월등히 향상되었다.