코틀린을 다루는 기술 4장 정리 - 재귀, 공재귀, 메모화
코틀린을 다루는 기술 4장을 읽고 정리한 내용입니다.
요약된 표현이 많기에 보다 자세한 설명은 책을 통해 확인하실 수 있습니다.
4장까지 읽고 나서야 이 책의 정수는 연습문제 라는 것을 알게 되었다. 하나씩 직접 풀어보면서 코틀린 코드 작성의 다양한 기법을 훈련하는게 좋겠지만, 정리글에서는 연습문제까지 다루지는 않을 생각이다.
개요
- 재귀, 공재귀, 꼬리 재귀 함수의 구현 방법을 알아본다.
- TCE를 사용해 꼬리 재귀 호출을 최적화한다.
- 람다를 재귀적으로 만든다.
- memorization을 적용해 계산 속도를 높인다.
4.1 공재귀와 재귀
둘다 자기 자신을 호출하는 함수지만, 계산이 처음 시작되는 시점에서 차이가 있다.
- 재귀(recursive) : 마지막 단계부터 계산을 시작한다.
- 공재귀(corecursive) : 한 단계의 출력을 다음 단계의 입력으로 사용하는 계산 단계를 합성한 것으로, 첫 단계부터 계산을 시작한다.
문자열 리스트를 하나의 문자열로 변환하는 코드를 공재귀로 작성해보자.
- toString()이 호출되면 초기 문자열 s로부터 시작해 한단계씩 계산을 진행한다 ("abc" -> "abc1" -> "abc12"...)
fun append(s: String, c: Char) = "$s$c"
fun toString(list: List<Char>, s: String): String = if (list.isEmpty()) {
s
} else {
toString(list.drop(1), append(s, list.first())) // 같은 표현
}
fun main(args: Array<String>) {
println(toString(listOf('1', '2', '3'), "abc")) // abc123
}- List만 있어도 되도록 개선하기
- 코틀린은 자신을 호출하는 함수의 타입을 추론할 수 없다. 안쪽 함수는 자기 자신을 호출하는 함수라 타입을 명시해야 한다.
fun append(s: String, c: Char) = "$s$c"
fun toString(list: List<Char>): String {
fun toString(list: List<Char>, s: String): String = if (list.isEmpty()) {
s
} else {
toString(list.drop(1), append(s, list.first()))
}
return toString(list, "")
}
fun main(args: Array<String>) {
println(toString(listOf('1', '2', '3'))) // 123
}만약 append 대신 아래의 메서드만 사용 가능하다면?
fun prepend(s: String, c: Char) = "$c$s"-
공재귀를 그대로 사용할 경우, 리스트의 첫번째 요소 대신 마지막 요소를 이용해 단계별로 진행함
만약 리스트 대신 단일 연결리스트를 사용할 경우 매우 비효율적
fun toString(list: List<Char>, s: String): String = if (list.isEmpty()) { s } else { toString(list.subList(0, list.size - 1), prepend(s, list.last())) } -
재귀로 구현할 경우, 재귀는 최종 조건(
list.isEmpty())에 도달하기 전까지는 계산이 미뤄지고, 중간 결과는 stack 메모리에 저장된다.fun toString(list: List<Char>, s: String): String = if (list.isEmpty()) { s } else { prepend(toString(list.subList(1, list.size)), list.first()) }
재귀 함수와 공재귀 함수 구분
함수가 계산의 일부분으로 자기 자신을 호출한다면 그 함수는 재귀적이다.
그렇지 않다면 자기 자신을 호출하더라도 진정한 재귀 함수가 아니다.
아래의 코드는 재귀적인 메서드를 통해 구현했지만, 실제로 이 함수는 무한 루프로 변환할 수 있는 공재귀 함수다.
특정한 계산이 없고, 종료 조건도 없다. 종료 코드가 없기 때문에 진정한 재귀가 아니다.
fun hello() {
hello()
}공재귀와 재귀의 차이점
- 공재귀에서는 각 단계를 즉시 계산한다, 재귀 함수는 최종 조건에 도달하고 나서 이전 단계를 역순으로 계산한다. 메모리엔 현재 계산에 필요한 값만 저장된다.
- 재귀에서는 최종 조건에 도달할 때 까지 모든 단계를 어떤 형태로든 저장해야 한다. 이로 인해 메모리가 부족해질 확률이 높고, 이 문제를 피하려면 재귀 대신 공재귀를 사용하는 것이 최선이다.
4.2 꼬리 호출 제거
중간 계산 결과를 저장하지는 않지만 공재귀도 결국은 스택 공간을 사용하기 때문에, 느리긴 하지만 언젠가 스택을 고갈시킬 가능성이 있다. 이 문제를 완전히 제거하기 위해선 공재귀를 일반적인 루프로 바꾸면 된다.
fun toString2(list: List<Char>): String {
var s = ""
for (c in list) {
s = append(s, c)
}
return s
}꼬리 호출 제거 (TCE, Tail Call Elimination)
코틀린에는 공재귀를 자동으로 루프로 변환해주는 기능이 있다.
-
꼬리 재귀 호출 : 재귀 호출 결과를 다른 연산에 사용하지 않고 즉시 반환하는 함수
자기 자신만을 호출하다가 결과 값을 반환하는 구조로 꼬리 재귀 함수 O
fun toString(list: List<Char>, s: String): String = if (list.isEmpty()) { s } else { toString(list.drop(1), append(s, list.first())) }결과 값에
trim()이라는 추가적인 연산을 수행하므로 꼬리 재귀 함수 Xfun toString(list: List<Char>, s: String): String = if (list.isEmpty()) { s } else { toString(list.drop(1), append(s, list.first())).trim() } -
코틀린에서 함수 앞에
tailrec키워드를 앞에 붙이면 꼬리 호출을 제거할 수 있다. 재귀 대신 루프를 사용한 코드로 변경된다. -
tailrec을 붙이고 디컴파일 해보기
-
Kotlin으로 작성한 코드
tailrec fun toString(list: List<Char>, s: String): String = if (list.isEmpty()) { s } else { toString(list.drop(1), append(s, list.first())) } -
디컴파일 결과 코틀린이 이 함수가 꼬리 재귀임을 감지하고 TCE를 적용했다.
@NotNull public static final String toString(@NotNull List list, @NotNull String s) { while(true) { Intrinsics.checkParameterIsNotNull(list, "list"); Intrinsics.checkParameterIsNotNull(s, "s"); if (list.isEmpty()) { return s; } List var10000 = CollectionsKt.drop((Iterable)list, 1); s = append(s, (Character)CollectionsKt.first(list)); list = var10000; } }
-
재귀를 공재귀로 변환하기
재귀가 공재귀보다 메모리 제약이 크다는 단점이 있으나, 재귀에는 코드 작성이 단순하다는 장점이 있다.
// 1..n까지의 합을 구하는 함수
// 재귀를 사용했을 때
fun sum(n: Int): Int = if (n < 1) 0 else n + sum(n - 1)
// 루프를 사용했을 때
fun sum(n: Int): Int {
var result = 0
for (i in 0..n) {
result += n
}
return result
}자기 자신을 호출할 때마다 s + i와 i + 1의 계산 결과를 넘겨주면 공재귀로 변환이 가능하다.
앞에 tailrec을 붙여 TCE를 적용하면 루프를 사용하는 것과 동일한 동작이 된다.
fun sum(n: Int): Int {
tailrec fun sum(s: Int, index: Int): Int =
if (index > n) s else sum(s + index, index + 1)
return sum(0, 0)
}4.3 재귀 함수와 리스트
리스트를 처리할 때 일반적으로 리스트를 0번 요소와 0번 요소를 제외한 나머지 두 부분으로 쪼개서 처리한다. 0번 요소를 head, 나머지를 tail이라 부른다. 리스트의 머리와 꼬리를 돌려주는 확장 함수를 정의하자.
fun <T> List<T>.head(): T = if (isEmpty()) {
throw IllegalArgumentException("head called on empty list")
} else {
this[0]
}
fun <T> List<T>.tail(): List<T> = if (isEmpty()) {
throw IllegalArgumentException("tail called on empty list")
} else {
drop(1)
}- 아까 전 작성했던 toString()에 확장 함수 head(), tail()를 적용해서 더 직관적으로 표현할 수 있다.
fun toString(list: List<Char>): String {
tailrec fun toString_(list: List<Char>, s: String): String =
if (list.isEmpty()) s else toString_(list.tail(), append(s, list.head()))
return toString_(list, "")
}인자 타입이 같아도 충돌이 나지 않도록, 앞으로는 도우미 함수는 주 함수_ 형식으로 네이밍 하겠다.
이중 재귀 함수(doubly recursive function)
이중 재귀는 단계마다 자신을 두 번 호출하는 함수를 의미한다.
-
피보나치 수열은 이중 재귀 함수를 설명하는 가장 간단한 예제다.
fun fibonacci(n: Int): Int = if (n <= 1) 1 else fibonacci(n - 1) + fibonacci(n - 2)한 번 함수를 호출할 때마다 2개의 추가 호출이 생기기 때문에 f(n)을 계산하려면 2^n개의 재귀 호출이 발생한다. 이로인해 숫자가 조금만 커져도 실행 시간이 무지막지하게 길어진다.
4.4 메모화(memorization)
메모화(memorization)는 계산 결과를 메모리에 저장해 나중에 같은 계산을 다시 수행하지 않고 결과를 바로 반환하는 기법이다. 어떤 계산 결과가 여러번 필요할 때 계산을 반복하지 않기 위해 사용한다.
루프를 사용할 때 메모화 적용
fun fibonacciLoop(n: Int): Int {
var first = 1
var second = 1
return when (n) {
1 -> first
2 -> second
else -> {
var current = first + second
for (num in 3..n) {
current = first + second
first = second // f(n - 1)을 저장
second = current // f(n)을 저장
}
current
}
}
}이런 기법은 안전한 프로그래밍 원칙을 위배하는 것처럼도 보인다. 함수를 메모화하려면 상태를 유지해야 하는데, 이 상태가 부수 효과에 해당하기 때문이다. 그러나 같은 인자를 사용하면 항상 같은 결과가 나오므로, 안전한 프로그래밍 원칙을 위반하지 않는다.
재귀함수에 메모화 적용
fun fibo(number: Int): String {
tailrec fun fibo_(
acc: List<BigInteger>,
acc1: BigInteger,
acc2: BigInteger,
x: BigInteger
): List<BigInteger> =
when (x) {
BigInteger.ZERO -> acc
BigInteger.ONE -> acc + (acc1 + acc2)
else -> fibo_(acc + (acc1 + acc2), acc2, acc1 + acc2, x - BigInteger.ONE)
}
val list = fibo_(listOf(), BigInteger.ONE, BigInteger.ZERO, BigInteger.valueOf(number.toLong()))
return list.joinToString()
}암시적 메모화 사용하기
피보나치 수열 1, 1, 2, 3, 5, 8...을 다음과 같이 튜플의 집합으로도 볼 수 있다.
(1, 1), (2, 3), (5, 8)... 튜플로부터 다음 튜플을 만들어낼 수 있다.
val fibo = { (a, b): Pair<BigInteger, BigInteger> -> Pair(b, a + b)}자동 메모화 사용하기
한 번 계산한 적이 있는 값이라면, 캐시에 저장해 뒀다가 똑같은 계산이 반복될 때 꺼내 쓰면 된다. 입력의 가짓수가 많지 않다면 모든 결과를 메모리에 저장해도 되나, 만약 가짓수가 많다면 소프트 참조나 약한 참조를 사용하는 것이 좋다.
class Memoizer<T, U> private constructor() {
private val cache = ConcurrentHashMap<T, U>()
private fun doMemoize(function: (T) -> U): (T) -> U = { input ->
cache.computeIfAbsent(input) {
function(it)
}
}
companion object {
fun <T, U> memoize(function: (T) -> U): (T) -> U =
Memoizer<T, U>().doMemoize(function)
}
}앞서 작성한 Memoizer를 활용해 연산 결과를 캐싱해보자
fun longComputation(number: Int): Int {
println("계산 실행")
return number
}
fun main(args: Array<String>) {
// memoizedLongComputation(43)의 연산 결과가 캐싱되어, "계산 실행"은 1번만 출력된다.
val memoizedLongComputation = Memoizer.memoize(::longComputation)
val result1 = memoizedLongComputation(43)
val result2 = memoizedLongComputation(43)
}다인자 함수의 메모화 구현하기
3장에서 얘기했듯 다인자 함수는 존재하지 않는다. 여러 인자를 받는 것처럼 보이는 함수는 둘 중 하나에 속한다
- 튜플의 함수 : 인자로
Pair를 사용하면 된다. - 함수를 반환하는 함수를 반환하는... 커리된 함수 : 커리한 함수의 각 단계가 반환하는 함수를 각각 메모화 해야한다.
val f3 = { x: Int -> { y: Int -> { z: Int -> x + y - z } } }
// 인자가 3개인 함수 메모화
val f3m = Memoizer.memoize { x: Int ->
Memoizer.memoize { y: Int ->
Memoizer.memoize { z: Int -> x + y - z }
}
}4.5 메모화한 함수는 순수 함수인가
메모화한 함수는 인자가 같으면 항상 같은 결과를 내놓는다. 단지 결괏값을 반환하는데 걸리는 시간이 달라질 뿐이다. 원래 함수가 순수 함수라면 메모화한 함수도 순수 함수다.
이 챕터에선 코틀린의 joinToString(), append()와 동일한 연산을 하는 문자열 함수들이 예제로 등장했다. 코틀린에서 이 함수들의 실제 구현을 살펴보면 공재귀는 커녕 전부 for문으로 구현되어 있다. 여기까지 읽으면서도 반복문으로 작성 가능한 코드를 굳이 재귀로 표현하는게 가독성 측면에서 더 유리한 상황이 얼마나 있을까?(=이걸 어따 써먹지;;) 싶었다. 그래도 tailrec이라는 강력한 키워드의 존재를 새롭게 알게됐다.
'if (study) > Java & Kotlin' 카테고리의 다른 글
| 코틀린을 다루는 기술 5장 정리 - 리스트로 데이터 처리하기 (0) | 2020.07.18 |
|---|---|
| 코틀린을 다루는 기술 3장 정리 - 함수로 프로그래밍하기 (2) | 2020.07.05 |
| [Kotlin] *(Star-projections)과 Any의 차이점 (0) | 2020.04.17 |
