14. 재귀 프로그래밍과 메모제이션 프로그래밍

다재다능 코틀린 프로그래밍 책으로 코틀린 스터디를 진행하면서 발표를 위해 준비했던 글입니다.

---

코틀린에서는 일반적인 재귀를 쉽게 지원하지만 일반적인 재귀함수에는 리턴 타입이 필요하다.

코틀린으로 팩토리얼을 재귀로 구현해보자.

import java.math.BigInteger

fun factorialRec(n: Int): BigInteger =
    if (n <= 0) 1.toBigInteger() else n.toBigInteger() * factorialRec(n - 1)

재귀는 가독성이 좋지만 사이즈가 크다면 StackOverflowError를 만날 수 있다.

이럴 때 tailrec 키워드로 꼬리호출 최적화를 할 수 있다.

import java.math.BigInteger

tailrec fun factorialRec(n: Int): BigInteger =
    if (n <= 0) 1.toBigInteger() else n.toBigInteger() * factorialRec(n - 1)
println(factorialRec(50000))

이렇게 간단하게 tailrec만 붙여주면 꼬리호출 최적화가 될 것 같지만 그렇지만은 않다.

factorialRec(50000) 에 대한 결과가 출력되지 않는다.

꼬리호출 최적화는 재귀 호출이 마지막 위치일 경우에만 가능하다.

위 예제의 마지막연산은 factorialRec 메소드가 아닌 * 연산이다.

tailrec fun factorial(n: Int, result: BigInteger = 1.toBigInteger()): BigInteger =
    if (n <= 0) result else factorial(n - 1, result * n.toBigInteger())
println(factorial(50000))

factorial 연산이 마지막 연산이 됨으로써 진짜 꼬리호출 최적화가 되고 결과도 출력된다.

최적화가 동작되는 것을 직접 살펴보자.

import java.math.BigInteger

object Factorial {
    fun factorialRec(n: Int): BigInteger =
        if (n <= 0) 1.toBigInteger() else n.toBigInteger() * factorialRec(n - 1)

    tailrec fun factorial(n: Int, result: BigInteger = 1.toBigInteger()): BigInteger =
        if (n <= 0) result else factorial(n - 1, result * n.toBigInteger())
}

앞에서 봤던 일반적인 재귀 호출과 꼬리호출 최적화를 해준 재귀호출을 팩토리얼 클래스로 만들어주고 명령어로 코드를 컴파일 후 바이트코드를 생성하였다.

kotlinc-jvm Factorial.kt
javap -c -p chapter14.Factorial

private chapter14.Factorial();
    Code:
       0: aload_0
       1: invokespecial #8                  // Method java/lang/Object."<init>":()V
       4: return

  public final java.math.BigInteger factorialRec(int);
    Code:
        ...
      42: invokevirtual #29                 // Method factorialRec:(I)Ljava/math/BigInteger;
    ...  

  public final java.math.BigInteger factorial(int, java.math.BigInteger);
    Code:
      ...
      27: ifgt          35
      30: aload         8
      32: goto          90
            ...
      87: goto          14
      90: areturn

factorialRec() 바이트 코드에서는 factorialRec()를 재귀적으로 호출하기 위해 invokevirtual 명령어가 사용된 반면에 factorial() 바이트 코드에선 invokevirtual 명령어가 전혀 없이 goto로 함수의 다른 부분으로 점프를 했다. 이는 재귀가 반복으로 컴파일 되었다는 증거이다.

메모제이션

메모제이션 없이 재귀를 사용한 피보나치수의 구현은 아래와 같다.

fun fib(n: Int): Long = when (n) {
    0, 1 -> 1L
    else -> fib(n - 1) + fib(n - 2)
}
println(fib(5)

fib 함수에 인자로 5정도만 넘겨도 굉장히 느리게 결과가 출력된다.

Groovy 방식의 메모이제이션

fun <T, R> ((T) -> R).memoize(): ((T) -> R) {
    val original = this
    val cache = mutableMapOf<T, R>()
    return { n: T -> cache.getOrPut(n) { original(n) } }
}

lateinit var fib: (Int) -> Long
fib = { n: Int ->
    when (n) {
        0, 1 -> 1L
        else -> fib(n - 1) + fib(n - 2)
    }
}.memoize()

println(fib(500))

확장함수를 사용해 Groovy 방식으로 메모제이션을 구현했다. mutableMap에 value가 있는지 확인하고 없으면 연산을 해서 리턴하기 전에 저장하고 vlaue가 있으면 그 값을 꺼내는 방식이다.

메모제이션을 적용하기 전엔 5정도도 느리게 실행됐던게 500을 넣어도 빨리 실행된다.

델리게이트를 이용한 메모제이션

import kotlin.reflect.KProperty

class Memoize<T, R>(val func: (T) -> R) {
    private val cache = mutableMapOf<T, R>()
    operator fun getValue(thisRef: Any?, property: KProperty<*>) = { n: T ->
        cache.getOrPut(n) { func(n) }
    }
}

val fib: (Int) -> Long by Memoize { n: Int ->
    when (n) {
        0, 1 -> 1L
        else -> fib(n - 1) + fib(n - 2)
    }
}

print(fib(40))

by 키워드로 델리게이트를사용하면 훨씬 깔끔하게 메모제이션할 수 있다.

DP 막대자르기에 문제에 메모제이션 적용

길이가 1 ~ 7 까지 있을 때 가격이 2, 4, 5, 7, 10 ,17, 17 이다. 길이가 주어질 때 가장 많은 수익을 올릴 수 있는 방법을 찾는 문제이다.

val prices = mapOf(1 to 2, 2 to 4, 3 to 6, 4 to 7, 5 to 10, 6 to 17, 7 to 17)
val maxPrice: (Int) -> Int by Memoize { length: Int ->
    val priceAtLength = prices.getOrDefault(length, 0)
    (1 until length).fold(priceAtLength) { max, cutLength ->
        val cutPrice = maxPrice(cutLength) + maxPrice(length - cutLength)
        Math.max(cutLength, max)
    }
}