재귀 호출

재귀 호출은 함수 내부에 자기 자신을 호출하여 반복하는 형태의 호출을 말합니다.
어떤 점화식을 표현하기에 가장 직접적인 방식입니다.

피보나치 수열을 예로 든다면 피보나치의 점화식은 아래와 같습니다.

1	f(n) = f(n-1) + f(n-2) (n=0 -> 0, n=1 -> 1, n >= 0)

이를 실제 코드로 표현하면 다음과 같습니다.


fun fibo(n: Int): Int = when {
    n < 0 -> 0
    n < 2 -> n
    n >= 2 -> fibo(n - 2) + fibo(n - 1)
    else -> 0
}

위의 점화식이 코드상에 그대로 표현되는 것을 알 수 있습니다.

꼬리재귀

재귀 호출은 구현이 쉽지만 함수 호출이 많아질수록 stackoverflow의 위험에 있습니다. 그리고 함수 호출에 대한 호출 비용 역시 크기 때문에, 프로덕션 레벨에서 쉽게 사용하기 어려운 호출 방식입니다. 일반적으로 이런 경우엔 for, while 등의 반복문을 이용하여 구현하게 됩니다. 하지만 반복문으로 표현하기 어려운 몇몇 경우에는 재귀를 사용하게 되는데, 이럴 때는 꼬리 재귀 최적화를 이용하여 코드를 작성하면 문제를 해결 할 수 있습니다.

꼬리 재귀 최적화는 재귀호출 형태의 함수를 반복문 형태로 변경하여, 재귀호출로 인한 함수호출에 대한 비용을 줄일 수 있고 또한 stackoverflow의 문제에서도 자유로워집니다.

위 피보나치를 꼬리재귀형태로 구현한 코드 입니다.

fun fiboTail(n: Int): Int {
    if (n < 2) return max(n, 0)

    tailrec fun loop(n1: Int, n2:Int, i:Int): Int {
        if (i == 0) return n1 + n2
        return loop(n2, n1+n2, i - 1) 
    }

    return loop(0, 1, n - 2)
}

꼬리 재귀 최적화를 위해서는 가장 중요한 조건이 필요합니다. 재귀 호출 하는 부분이 함수 실행의 마지막이어야 합니다.(함수의 마지막 라인이 아닌 실행의 마지막이어야 합니다.) 꼬리 재귀 형태에서는 컴파일 과정에서 재귀 함수 호출을 제거하고 바이트코드 내부에 goto문을 사용하여 반복 할 수 있도록 할 수 있습니다.
또 함수앞에는 tailrec 이라는 지시어가 붙으면 컴파일러는 해당 함수가 꼬리 재귀 최적화가 가능한지 확인한 후 가능하면 꼬리재귀 최적화를 진행하여 코드를 수정합니다.

그리고 꼬리재귀 최적화는 JVM, Kotlin/native에서만 사용 가능합니다.

메모이제이션

메모이제이션은 어떤 함수의 호출 결과를 저장하여 다시 호출 될 때 저장된 값을 사용하여 함수를 호출하지 않도록 하는 최적화 기법입니다. 대부분의 경우 다이나믹 프로그래밍 알고리즘 문제를 풀 때 많이 사용하는 방법입니다. 비 꼬리 재귀 호출 형태의 피보나치 함수에 메모이제이션을 통해 최적화를 해보겠습니다.

val cache:MutableMap<Int, Int> = mutableMapOf()

fun fibo(n: Int): Int {
    if (n in cache) return cache[n]?:0

    val result = when {
        n < 0 -> 0
        n < 2 -> n
        n >= 2 -> fibo(n - 2) + fibo(n - 1)
        else -> 0
    }

    cache[n] = result

    return result
}

map 을 이용해 결과를 캐시하여 호출 량을 절대적으로 줄일 수 있게 되었습니다.
근데 이 코드는 코틀린스럽지 않습니다. 좀 더 간단하게 작성 할 수 있을까요?

함수 확장 함수

함수에 확장 함수를 추가 할 수 있는 코틀린의 특징을 이용해 아래와 같이 구현이 가능합니다.


fun <T, R> ((T) -> R).memo(): ((T) -> R) {
    val thiz = this
    val cache = mutableMapOf<T, R>()

    return {t:T -> cache.getOrPut(t) { thiz(t) } }
}

lateinit var fibo: (Int) -> Long
fibo = { n: Int ->
        when {
            n < 0 -> 0L
            n < 2 -> n.toLong()
            n >= 2 -> fibo(n - 2) + fibo(n - 1)
            else -> 0L
        }
    }.memo()

정확히는 람다에 추가되는 함수이기 때문에 위와 같이 변수 상에 람다를 할당하는 방식으로 사용해야 합니다. 제네릭을 통해 모든 형태의 함수에서 사용이 가능합니다.

델리게이트

코틀린의 델리게이트를 사용하면 아래와 같이 간략화가 가능합니다.

class Memoize<T, R>(val func: (T) -> R) {
    val cache = mutableMapOf<T, R>()

    operator fun getValue(thisRef: Any?, props: KProperty<*>) = {
        t: T ->
        cache.getOrPut(t) { func(t) }
    }
}

typealias FiboFunc = (Int) -> Long
val fibo2: FiboFunc by Memoize { n -> when {
    n < 0 -> 0L
    n < 2 -> n.toLong()
    n >= 2 -> fibo2(n - 2) + fibo2(n - 1)
    else -> 0L
} }

이렇게 선언하는 경우에는 앞의 케이스와는 다르게 lateinit var 를 이용한 지연 초기화를 하지 않아도 되기 때문에 코드가 좀 더 간결해졌다. 델리게이션으로 인해 함수내의 fibo2 재귀 호출이 간접적으로 진행되기 때문에 가능해졌습니다.

참고
다재다능 코틀린 프로그래밍
코틀린 공식문서

Kotlin - 14. Recursive & memoization

목차

재귀 호출

꼬리재귀

메모이제이션

함수 확장 함수

델리게이트