[코틀린 프로그래밍] Chapter.14 재귀 프로그래밍과 메모이제이션 프로그래밍

나를 닮았다고 한다...

이번 챕터에서는 재귀 프로그래밍에 대해서 작성해보겠습니다. 재귀는 쿨한 프로그래밍 기법이지만 잘못 사용한다면 런타임 스택 오버플로에 빠져서 효율성이 떨어지는 문제가 있습니다. 꼬리호출 최적화라고 불리는 테크닉을 이용하면 이 문제를 해결할 수 있습니다.

데이터를 저장하는 알고리즘을 사용하면 성능은 향상됩니다. 코틀린은 빌트인 메모이제이션을 지원해주지는 않지만 지금까지 배운 기술들을 사용하면 표현력이 강한 메모이제이션 기능을 쉽게 만들 수 있습니다.

---

재귀의 강점과 위험성

재귀를 사용하면 분할정복기법을 사용할 수 있습니다. 예제로 살펴보자.

// 분할정복기법 문제를 해결할 때 문제를 작게 쪼개서 각 부분의 솔루션을 구현한 후 각 결과를 합쳐서 해결하는 기법

fun sort(numbers: List<Int>): List<Int> = if (numbers.isEmpty()) { numbers } else { val pivot = numbers.first() val tail = numbers.drop(1) val lessOrEqual = tail.filter { e -> e <= pivot } val larger = tail.filter { e -> e > pivot } sort(lessOrEqual) + pivot + sort(larger) } println(sort(listOf(12, 5, 15, 12, 8, 19))) // [5, 8, 12, 12, 15, 19]

sort() 함수는 주어진 입력을 두 파트로 분리하고 두 파트를 각각 정렬합니다. 그리고 마지막으로 두 솔루션을 합쳐서 저네 솔루션을 만듭니다. 코틀린에서는 일반적인 재귀를 쉽게 지원합니다. 일반적인 재귀함수는 타입이 필요하고 타입 추론을 할 수 없습니다.

간단한 재귀 코드 예제로 살펴보겠습니다.

import java.math.BigInteger fun factorialRec(n: Int): BigInteger = if (n <= 0) 1.toBigInteger() else n.toBigInteger() * factorialRec(n - 1) println(factorialRec(5)) // 120

위 코드는 아래처럼 반복문을 이용해서 구현 가능합니다.

// 이것보단 재귀함수가 더 인식하기 편하다! fun factorialIterative(n: Int) = (1..n).fold(BigInteger("1")) { product, e -> product * e.toBigInteger()}

문제가 있다면 입력값이 크면 런타임 중에 코드가 멈추게 됩니다.

// StackOverflowError 발생... println(factorialRec(5000000))

---

꼬리호출 최적화

우리가 작성한 코드는 프로시저가 되고 생성한 바이트 코드는 결국 실행이 됩니다. factorialIterative() 함수는 반복을 사용하는 프로시저입니다. 그리고 반복을 사용하는 프로세스로 컴파일되고 실행될 것입니다. 이와 유사하게 factorialRec()는 재귀 프로시저고 재귀 프로세스로 컴파일되고 실행됩니다. 실제로 재귀 프로시저는 반복 프로세스로 컴파일 될 수 있습니다. 이런 접근이 양측의 장점을 모두 제공합니다. 즉 stack overflow 오류가 없게 되었습니다.

tailrec 어노테이션이 코틀린 컴파일러에게 지시할 내용입니다. factorialRec(0 메소드에 tailrec 키워드를 붙혀보겠습니다.

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

위 코드는 아직 동작하지 않습니다. 동일하게 런타임 에러가 발생합니다. 코틀린의 재귀를 반복으로 최적화하는 것은 호출이 마지막 위치일 경우에만 가능합니다.

n.toBigInteger() * factorialRec(n-1) 코드에서 factorialRec() 메소드가 마지막에 실행된다고 생각하고 싶습니다. 하지만 아니다. 리턴하기 전 수행하는 연산은 곱셈이다. 이 연산은 factorialRec이 완료될 때까지 기다린다. 그래서 각 재귀 호출들의 스택 사이즈가 커지는 것입니다.
다시 쉽게 정리한다면 factorialRec메서드를 호출하고 호출하고 호출하고 호출하고 마지막까지 갈때까지 Stack은 쌓이게 되고 마지막에 도착하고나서야 비로소 한개씩 실행합니다. 해결 방법으로는 곱셈을 위해 재귀 호출이 끝날때까지 기다리는 방식이 아닌 재귀 메소드 내부에서 처리하는 방법이다. 코틀린 컴파일러가 뒤에서 조용히 최적화를 해서 반복을 이용하도록 함수를 변경했다는 사실을 알 수 있다.

tailrec fun factorial(n: Int, result: BigInteger = 1.toBigInteger()): BigInteger = if (n <= 0) result else factorial(n - 1, result * n.toBigInteger()) println(factorial(5000)) // 에러가 발생하지 않는다.

최적화가 동작되는 것을 보기 위해 Factorial 클래스를 만들고 재귀 버전과 꼬리재귀 버전의 클래스를 작성해보자.

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) 1.toBigInteger() else factorial(n - 1, result * n.toBigInteger()) }

이 부분은 잘 이해가 안된다.. 차근 차근 살펴보자..... show kotlin byte...으로 두개 메소드의 차이점을 알아보자

factorialRec()의 바이트코드에서 factorialRec()를 재귀적으로 호출하기 위해서 invokevirtual 명령어가 사용되었다.
그 후 BigInteger에 multiply() 메소드가 호출되었다. 즉, 재귀 프로시저가 재귀 프로세스로 컴파일 되었다는 것을 보여준다.

반면에 factorial()의 바이트코드는 invokevirtual 재귀 호출이 전혀 없다. 대신 ifgt를 호출하고 goto로 함수의 다른 부분으로 점프한다.
즉, 재귀 프로시저가 반복을 이용하는 프로세스로 컴파일 되었다는 증거다. 코틀린이 잘했단다... 무슨말인지 모르겠다..

tailrec 최적화는 재귀가 꼬리호출일 때만 동작한다. tailrec를 사용하기 위해서 우리는 factorialRec()를 재취 호출이 마지막에 나오는 factorial()로 재작성했다. 그래서 재귀가 마지막에 나오게 되었고, 꼬리재귀로 평가 되었다. 재귀가 복잡하다면 tailrec를 사용하기 쉽지 않다.

꼬리호출 최적화는 재귀를 반복으로 변환해서 스택 레벨의 숫자를 제어한다.
이런 방법은 효츌성 측면에서 영향이 있다. 하지만! 함수를 반복적으로 호출하지 않고, 저장된 값을 리턴하면 실행을 더 빠르게 할 수 있다!!

---

메모이제이션

입력이 같다면 몇 번을 호출해도 같은 결과가 나옵니다. 저장된 값을 사용함으로써 우리는 다시 계산하는 것을 피할 수 있고 실행을 빠르게 만들 수 있습니다.

반복연산

이전에 호출이 리턴한 결과를 기억해두도록 하면 연산시간을 현저하게 줄일 수 있습니다. 후속 소출에서 값이 이미 존재한다면 재귀 호출을 하지 않고 존재하는 값을 리턴합니다.

/* 연산시간이 오래 걸리는 메소드.. */ fun fib(n: Int): Long = when (n) { 0, 1 -> 1L else -> fib(n - 1) + fib(n - 2) } println(measureTimeMillis { fib(40) }) // 3분 println(measureTimeMillis { fib(45) }) // 4초

Groovy 방식의 메모이제이션

1. memoize() 메소드를 제네릭 람다 표현식에 인젝트
2. 제네릭 람다 표현식은 T타입의 파라미터를 받고, R타입의 리턴
3. memoize()를 호출한 결과는 함수와 동일한 시그니처를 가진 함수
4. memoize() 함수에서 우리는 this를 로컬변수 original에 할당해서 오리지날 함수의 래퍼런스를 저장할 수 있다.
5. 비어있는 cache를 초기화한다.
6. T타입의 파라미터를 받고, R타입의 결과를 리턴하는 람다를 리턴한다.
7. 리턴된 함수는 결과가 존재하는지 보기 위해 캐시를 확인한다.
8. 캐시에 결과가 없다면 연산을 해서 결과를 만들고 리턴하기 전에 저장한다.
9. 이미 결과가 존재한다면 연산을 건너뛰고 저장된 값을 리턴한다.

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

lateinit : 코틀린은 정적 변수를 사용한다. 하지만 lateinit을 선언하여 난 잊지 않았어 ~ 이따가 선언할꺼야라고 코틀린에게 알려준다.

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

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

델리게이트는 내부적으로 캐시를 가지고 있고, 오리지날 함수는 func 프로퍼티를 가지고 있습니다. getValue() 함수가 값이 캐시에 없을 경우 오리지날 함수를 실행시키는 람다표현식을 리턴합니다.

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

fib 함수를 만들 때 델리게이션을 적용해보겠습니다.

val fib: (Int) -> Long by Memoize { n: Int -> when (n) { 0, 1 -> 1L else -> fib(n - 1) + fib(n - 2) } } println(measureTimeMillis { fib(40) }) // 0 println(measureTimeMillis { fib(50) }) // 0 println(measureTimeMillis { fib(500) }) // 1

정리

- 재귀는 크기가 큰 문제에서는 사용이 불가하다. (StackOverflow)
- 코틀린은 이런 문제를 tailrec을 제공해서 재귀호출을 사용하는 코드에 꼬리재귀 최적화를 제공
- 코틀린이 내부적으로 재귀를 반복으로 바꿔주어 개발자는 스택 오버프로를 걱정할 필요없다.
- 코틀린이 메모이제이션 함수를 직접 제공해주진 않지만 연산결과를 메모이즈하거나 캐싱하는 기능을 만들 수 있다.

---

번외) 재귀함수를 이용하여 카테고리를 불러와보자

먼저 DB에 저장되어있는 카테고리 필드 정보는 아래와 같습니다.

@Document(collection = "category") @Schema(hidden = true) data class StoreCategory( @Schema(description = "카테고리 키") var id: ObjectId? = null, @Schema(description = "뎁스") var depth: Int? = null, @Schema(description = "카테고리명") var name: String? = null, @Schema(description = "부모카테고리번호") @Field(value = "parent_id") var parentId: ObjectId? = null )

parentId로 하위 카테고리로 조합할 수 있는 구조입니다.

먼저 가장 상위 카테고리를 세팅하는 메소드입니다.

/** * 카테고리 조회 * @param storeId Long? * @return List<StoreCategoryDTO> */ private fun getCategory(storeId: Long?): List<StoreCategorySearchDTO> { val response = categoryRepository.selectByStoreId(storeId) return response .filter { it.depth == 0 } .map { StoreCategorySearchDTO( categoryId = it.id.toString(), categoryName = it.name, categoryDepth = it.depth, childrenCategoryInfo = getChildCategories(it.id, response.groupBy { it.parentId }) ) } }

DB에서 카테고리를 조회하여 depth가 0인 정보를 설정합니다. 그리고 다시 getChildCategories 메소드를 호출합니다.

/**+ * 자식 카테고리 생성 및 조회 재귀함수 * @param parentId ObjectId? * @param groupResponse Map<ObjectId?, List<StoreCategory>> * @return List<StoreChildCategoryDTO>? */ fun getChildCategories( parentId: ObjectId?, groupResponse: Map<ObjectId?, List<StoreCategory>> ): List<StoreCategorySearchDTO>? { val storeCategories = groupResponse[parentId] ?: return null return storeCategories.map { StoreCategorySearchDTO( categoryId = it.id.toString(), categoryName = it.name, categoryDepth = it.depth, parentCategoryId = it.parentId.toString(), childrenCategoryInfo = getChildCategories(it.id, groupResponse) ) } }

getChildCategories는 재귀함수로 하위 카테고리 정보가 null 일때까지 호출하여 데이터를 세팅합니다.