재귀는 프로그래밍에서 중요한 역할을 한다. 거기에 데이터를 저장하는 알고리즘을 사용하면 성능은 향상된다. 코틀린은 빌트인 메모이제이션을 지원해주지는 않지만 지금까지 배운 기술들을 사용하면 표현력이 강한 메모제이션 기능을 쉽게 만들 수 있다.
📌 재귀의 강점과 위험성
재귀를 사용하면 분할정복기법을 사용할 수 있다.
✍ 퀵 정렬
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)))sort() 함수는 주어진 입력을 두 파트로 분리하고 두 파트를 각각 정렬한다. 그리고 마지막으로 두 솔루션을 합쳐서 전체 솔루션을 만든다.
재귀 솔루션을 만들려면 노력이 필요하지만, 재귀는 매우 표현력이 좋다.
✍ factorialRec()
fun factorialRec(n: Int): BigInteger =
if (n <= 0) 1.toBigInteger() else n.toBigInteger() * factorialRec(n - 1)
println(factorialRec(5))factorialRec( ) 함수는 0보다 작은 값을 받으면 1을 리턴하고, 0보다 큰 값을 받으면 주어진 입력을 스스로를 재귀적으로 호출한 결과를 곱해서 리턴한다.
아래처럼 반복문을 이용해서 구현 할 수도 있다.
fun factorialRec(n: Int) =
(1..n).fold(BigInteger("1")) { product, e -> product * e.toBigInteger() }
fold() 함수는 아규먼트로 람다와 함께 초기값을 받는다는 점만 제외하면 "내부 반복" 에서 다룬 reduce()와 비슷한 함수이다.
복잡한 문제를 해결할 때 가능하다면 반복 솔루션보다는 재귀 솔루션을 사용하는 것이 더 이해하기 쉽다. 하지만 재귀는 반복 솔루션이 겪지 않는 문제를 일으킨다. 재귀는 스택을 증가시키고, 스택이 위험할 정도로 큰 레벨에 도달하면 프로그램리 뻗어버린다.
✍ ERROR
println(factorialRec(500000)) //java.lang.StackOverflowError이러한 문제를 해결하기 위해서는 꼬리 호출 최적화를 해야한다.
📌 꼬리 호출 최적화
factorialRec()는 재귀 프로시저이고 재귀 프로세스로 컴파일러되고 실행될 것이다. 만약 재귀 프로시저가 반복프로세스로 컴파일 될 수 있다면 stack overflow 오류를 줄일 수 있을것이다.
✍ tailrec
tailrec fun factorialRec(n: Int): BigInteger =
if (n <= 0) 1.toBigInteger() else n.toBigInteger() * factorialRec(n - 1)
println(factorialRec(50000))
💻 출력
factorial.kts:5:1: warning: a function is marked as tail-recursive but no tail calls are found
tailrec fun factorialRec(n: Int): BigInteger =
factorial.kts:6:58: warning: recursive call is not a tail call
if (n <= 0) 1.toBigInteger() else n.toBigInteger() * factorialRec(n - 1)tailrec 키워드를 붙였지만 아직 동작 하지 않는다.
코틀린의 재귀를 반복으로 최적화하는 것은 호출이 마지막 위치일 경우에만 가능하다.
n.toBigInteger() * factorialRec(n - 1)factorialRec(n - 1) 마지막으로 실행된다고 생각하겠지만 함수가 리턴하기 전 수행하는 연산은 곱셈 연산이다. 이 연산은 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))tailrec 최적화는 재귀가 꼬리호출일 때만 동작한다. tailrec을 사용하기 위해서 factorial()를 재귀 호출이 마지막에 나오는 factorial()을 재작성했다.
📌 메모이제이션
알고리즘 기법인 다이나믹 프로그램밍에서 하위 문제를 해결하는 솔루션을 재귀적으로 사용해서 전체 문제를 해결한다. 하지만 일반적인 재귀와 다르게 다이나믹 프로그래밍은 재귀를 사용할 때 하위 문제의 결과를 저장해 다시 사용한다.
반복연산
✍ 피보나치 수열
fun fib(n: Int): Long = when (n) {
0, 1 -> 1L
else -> fib(n - 1) + fib(n - 2)
}
println(measureNanoTime { fib(40) }) // Abount 3 milliseconds
println(measureNanoTime { fib(45) }) //Abount than 4 secondsfib() 함수는 주어진 값이 2보다 작을 경우 1을 리턴하고, 나머지 경우에는 2개의 재귀함수 호출의 결과를 연산해서 결과를 리턴한다.
n이 45인 경우 실행시간이 더 늘어났다. 만약 이전 결과를 기억해두면 연산시간을 현저하게 줄일 수 있다.
Groovy방식의 메모이제이션
메모이제이션을 다루기 위한 다이나믹한 동작이 필요하다. 함수가 호출됐을 때 캐시를 체크래 데이터가 존재하는지 확인하고 데이터가 없을 경우 함수를 호출해야 한다.
람다 표현식을 이용해 이러한 로직을 구현 할 수 있다.
함수에 메소드를 인젝트하는 방법을 이용해 람다에 memoize() 메소드를 만들것이다.
✍ memoize()
fun <T, R> ((T) -> (R)).memoize(): ((T) -> R) {
val original = this
val cache = mutableMapOf<T, R>()
return { n: T -> cache.getOrPut(n) { original(n) } }
}memoize() 메소드를 제네릭 람다 표현식에 인젝트했다. 제네릭 람다 표현식은 T타입의 파라미터를 받고, R타입의 리턴을 한다. memoize() 함수의 리턴타입은 memoize()가 인젝트된 메소드의 타입과 같은 타입의 람다 표현식이다.
memoize() 함수에서 this를 로컬변수 original에 할당해서 오리지널 함수의 레퍼런스를 저장할 수 있다. 그리고 비어있는 cashe를 초기화한다.
리턴된 함수는 결과가 존재하는지 보기 위해 캐시를 확인한다. 캐시에 결과가 없다면 연산을 해서 결과를 만들고 리턴하기 전에 저장한다. 이미 결과가 존재한다면 저장된 값을 리턴한다.
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) })
println(measureTimeMillis { fib(15) })
println(measureTimeMillis { fib(500) })lateinit를 이용해서 코틀린에게 fib 변수를 나중에 초기화 하겠다고 알린다. memoiz() 함수는 주어진 람다 표현식을 받고 그 람다를 memoiz() 함수 안에 있는 변수 original에 저장한다. 드리고 새로운 람다 표현식을 리턴한다.
💻 출력
0
0
0연산 시간이 현저히 줄어들었다.
memoiz() 함수는 파라미터 하나만 사용하는 모든 함수에 사용 가능하다. 이 솔루션에는 장/단점이 있다. 장점은 람다 표현식을 메모제이션을 사용하도록 만들었기 때문에 코드가 훨씬 간결하다. 하지만 fib를 정의해야 하고 fib에 람다 표현식을 할당해야 한다.
델리게이트를 이용한 메모이제이션
✍ 델리게이트
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) }
}
}뎅이게이트는 내부적으로 캐시를 가지고 있고, 오리지널 함수는 func 프로퍼티를 가지고 있다. 그리고 getValue() 함수가 값이 캐시에 없을 경우 오리지널 함수를 실행시키는 람다 표현식을 리턴한다.
val fib: (Int) -> Long by Memoize { n: Int ->
when (n) {
0, 1 -> 1L
else -> fib(n - 1) * (n - 2)
}
}
메모이제이션 어플리케이션은 델리게이트를 사용할 때 훨씬 깔끔하다.
println(measureTimeMillis { fib(40) })
println(measureTimeMillis { fib(15) })
println(measureTimeMillis { fib(500) })💻 출력
0
0
1
다이나믹 프로그래밍에 메모이제이션 적용하기
다이나믹 프로그래밍은 메모이제이션을 이용해서 재귀호출을 매우 효율적으로 만드는 알고리즘 기법이다. 캐싱하고 함수호출의 결과를 다시 사용하는 방법으로 다이나믹 프로그래밍은 반복적인 재귀함수 호출을 제거한다.
다이나믹 프로그래밍은 최적화 문제를 위해서 가능한 솔루션들을 재귀적으로 탐색하는데 사용된다.
예를 들어 길이가 1,2...7 일때 가격이 2,4,5,6,10,17 ,17 달러이다. 가장 많은 수익을 올릴 수 있는 방법은 무엇일까?
✍ max price
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 Fibdelegate.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(cutPrice, max)
}
}
prices 변수는 길이와 가격을 가지고 있는 이뮤터블 맵이다. maxPrice 변수는 Int로 길이를 받고 해당 길이의 최고 가격을 Int로 리턴해주는 람다를 참조한다. maxprice 변수의 호출을 인터셉트하는 델리게이트는 fold() 메소드를 이용해서 최대값을 계산한다.
1 부터 length-1 사이의 범위에 있는 모든 cutLength에서 우리는 이전에 계산된 최고값과 막대기를 두조각으로 잘라서 cutLength와 length-cutlength 로 만들었을 때의 가격 중 높으 것을 선택한다.
길이가 1 ~ 7일때 maxPrice() 함수를 이용해서 각 길이의 최고 가격을 찾는다.
💻 출력
For length 1 max price is 2
For length 2 max price is 4
For length 3 max price is 6
For length 4 max price is 8
For length 5 max price is 10
For length 6 max price is 17
For length 7 max price is 19
출처 : 다재다능 코틀린 프로그래밍
