- 재귀, 공재귀, 꼬리 재귀 함수의 구현 방법을 알아본다.
- TCE를 사용해 꼬리 재귀 호출을 최적화한다.
- 람다를 재귀적으로 만든다.
- memorization을 적용해 계산 속도를 높인다.
- 재귀(recursive) : 마지막 단계부터 계산을 시작한다.
- 공재귀(corecursive) : 한 단계의 출력을 다음 단계의 입력으로 사용하는 계산 단계를 합성한 것으로, 첫 단계부터 계산을 시작한다.
- 초기 문자열 s로부터 시작해 한단계씩 변형
fun append(s: String, c: Char) = "$s$c"
fun toString(list: List<Char>, s: String): String = if (list.isEmpty()) {
s
} else {
// toString(list.slice(1 until list.size), append(s, list[0]))
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()
}공재귀와 재귀의 차이점
- 공재귀에서는 각 단계를 즉시 계산한다, 재귀 함수는 최종 조건에 도달하고 나서 이전 단계를 역순으로 계산한다. 메모리엔 현재 계산에 필요한 값만 저장된다.
- 재귀에서는 최종 조건에 도달할 때 까지 모든 단계를 어떤 형태로든 저장해야 한다. 이로 인해 메모리가 부족해질 확률이 높고, 이 문제를 피하려면 재귀 대신 공재귀를 사용하는 것이 최선이다.
중간 계산 결과를 저장하지는 않지만 공재귀도 결국은 스택 공간을 사용하기 때문에, 느리긴 하지만 언젠가 스택을 고갈시킬 가능성이 있다. 이 문제를 완전히 제거하기 위해선 공재귀를 일반적인 루프로 바꾸면 된다.
fun toString2(list: List<Char>): String {
var s = ""
for (c in list) {
s = append(s, c)
}
return s
}코틀린애는 공재귀를 자동으로 루프로 변환해주는 기능이 있다.
-
꼬리 재귀 호출 : 재귀 호출 결과를 다른 연산에 사용하지 않고 즉시 반환하는 함수
자기 자신만을 호출하다가 결과 값을 반환하는 구조로 꼬리 재귀 함수 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.1
양의 정수에 대해 작동하는 공재귀 add 함수를 작성하라. add 구현에는 +나 -를 사용하지 않고 다음 두 함수만 사용해야 한다.
fun inc(n: Int) = n + 1 fun dec(n: Int) = n - 1
- loop를 사용할 경우
fun add(a: Int, b: Int): Int { var x = a var index = b while (index > 0) { x = inc(x) index = dec(index) } return x }
- 공재귀를 사용할 경우
tailrec fun add(a: Int, index: Int): Int = if (index > 0) { add(inc(a), dec(index)) } else { a }
-
연습 문제 4.2
재귀적 계승 함수 값을 작성하라. 함수 값은 val 키워드로 정의된 함수다.
- 지연초기화를 사용하지 않으면 람다식 내부에서 factorial을 참조할 수 없다는 오류가 출력된다. 컴파일러가 factorial을 정의하던 중간에 아직 정의가 끝나지 않은 factorial을 호출했기 때문이다. 이 문제를 해결하려면 지연초기화를 사용해야 한다.
val factorial: (Int) -> Int by lazy { { n: Int -> if (n <= 1) n else n * factorial(n - 1) } }
13부터는 int로 표현할 수 있는 범위를 넘어가기 때문에 제대로 실행되지 않는다. 만약 제대로 된 값을 원한다면 Int 대신
BigInteger를 사용하면 된다.
리스트를 처리할 때 일반적으로 리스트를 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, "")
}인자 타입이 같아도 충돌이 나지 않도록, 앞으로는 도우미 함수는 주 함수_ 형식으로 네이밍 하겠다.
이중 재귀는 단계마다 자신을 두 번 호출하는 함수를 의미한다.
-
피보나치 수열은 이중 재귀 함수를 설명하는 가장 간단한 예제다.
fun fibonacci(n: Int): Int = if (n <= 1) 1 else fibonacci(n - 1) + fibonacci(n - 2)
한 번 함수를 호출할 때마다 2개의 추가 호출이 생기기 때문에 f(n)을 계산하려면 2^n개의 재귀 호출이 발생한다. 이로인해 숫자가 조금만 커져도 실행 시간이 무지막지하게 길어진다.
-
4.3 꼬리 재귀 버전의 피보나치 함수를 만들라.
return 문에서
+연산을 직접 적용하면 TCE 적용이 불가능하다. 따라서 f(n - 1)과 f(n - 2)의 계산 결과를 누적하는 인자를 하나 추가해야 한다.fun fibonacci(x: Int): BigInteger { tailrec fun fib(n1: BigInteger, n2: BigInteger, x: BigInteger): BigInteger = when { (x == BigInteger.ZERO) -> BigInteger.ONE (x == BigInteger.ONE) -> n1 + n2 else -> fib(n2, n1 + n2, x - BigInteger.ONE) } return fib(BigInteger.ZERO, BigInteger.ONE, BigInteger.valueOf(x.toLong())) }
-
4.4 makeString의 꼬리 재귀 버전을 만들어라
fun <T> makeString(list: List<T>, delim: String): String { tailrec fun makeString_(list: List<T>, acc: String): String = when { list.isEmpty() -> acc acc.isEmpty() -> makeString_(list.tail(), "${list.head()}") else -> makeString_(list.tail(), "$acc$delim${list.head()}") } return makeString_(list, "") }
-
4.5 sum, toString, makeString을 정의할 때 쓸 수 있는 꼬리 재귀 제네릭 함수를 만들어라.
fun <T, U> foldLeft(list: List<T>, z: U, f: (U, T) -> U): U { tailrec fun foldLeft(list: List<T>, acc: U): U = if (list.isEmpty()) { acc } else { foldLeft(list.tail(), f(acc, list.head())) } return foldLeft(list, z) }
-
4.6 forLeft와 반대 방향으로, 공재귀 대신 재귀를 사용하는 foldRight를 작성하기
fun <T, U> foldRight(list: List<T>, identity: U, f: (T, U) -> U): U = if (list.isEmpty()) { identity } else { f(list.head(), foldRight(list.tail(), identity, f)) } fun string(list: List<Char>): String = foldRight(list, "") { c, s -> prepend(c, s) }
-
4.7 fold를 사용해 reverse 함수 정의하기
fun <T> reverse(list: List<T>): List<T> = foldLeft(list, listOf(), { newList: List<T>, elem: T -> listOf(elem) + newList }) fun main(args: Array<String>) { println(reverse(listOf(1, 2, 3)).joinToString()) // 3, 2, 1 }
-
4.8 두 리스트를 연결하지 않고,
리스트 + 원소를 사용해 reverse 함수를 만들기fun <T> prepend(list: List<T>, elem: T): List<T> = foldLeft(list, listOf(elem), { newList: List<T>, elm: T -> newList + elm }) fun <T> reverse(list: List<T>): List<T> = foldLeft(list, listOf(), ::prepend)
-
4.9 시작, 끝, x → x+1로 리스트를 만드는 함수의 루프 기반 구현 작성
fun range(start: Int, end: Int): List<Int> { val result: MutableList<Int> = mutableListOf() var index = start while (index < end) { result.add(index) index++ } return result }
-
4.10 임의의 타입과 조건에 대해서만 작동하게 4.9 수정
fun <T> unfold(seed: T, f: (T) -> T, p: (T) -> Boolean): List<T> { val result: MutableList<T> = mutableListOf() var elem = seed while (p(elem)) { result.add(elem) elem = f(elem) } return result }
-
4.11 4.10으로 4.9를 구현
fun range(start: Int, end: Int): List<Int> = unfold(start, { it + 1 }, { it < end })
-
4.12 4.9의 재귀 버전을 작성
fun range(start: Int, end: Int): List<Int> = if (end <= start) listOf() else prepend(range(start + 1, end), start)
-
4.13 4.10의 재귀 버전을 작성
fun <T> unfold(seed: T, f: (T) -> T, p: (T) -> Boolean): List<T> = if (p(seed)) prepend(unfold(f(seed), f, p), seed) else listOf()
-
4.14 4.10의 꼬리재귀 버전 작성
fun <T> unfold(seed: T, f: (T) -> T, p: (T) -> Boolean): List<T> { tailrec fun unfold_(acc: List<T>, seed: T): List<T> = if (p(seed)) unfold_(acc + seed, f(seed)) else acc return unfold_(listOf(), seed) }
메모화(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)}-
4.16 unfold처럼 작동하는 iterate 함수를 작성하라
fun <T> iterate(seed: T, f: (T) -> T, n: Int): List<T> { tailrec fun iterate_(acc: List<T>, seed: T): List<T> = if (acc.size < n) { iterate_(acc + seed, f(seed)) } else { acc } return iterate_(listOf(), seed) }
-
4.17 T → U 타입 함수를 List 타입 리스트의 모든 원소에 적용해 만든 List 타입의 리스트를 돌려주는 map 함수를 만든다.
fun <T, U> map(list: List<T>, f: (T) -> U): List<U> { tailrec fun map_(acc: List<U>, list: List<T>): List<U> = if (list.isEmpty()) { acc } else { map_(acc + f(list.head()), list.tail()) } return map_(listOf(), list) }
한 번 계산한 적이 있는 값이라면, 캐시에 저장해 뒀다가 똑같은 계산이 반복될 때 꺼내 쓰면 됨
입력의 가짓수가 많지 않다면 모든 결과를 메모리에 저장해도 되나, 만약 가짓수가 많다면 소프트 참조나 약한 참조를 사용하는 것이 좋다.
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)
}
}fun longComputation(number: Int): Int {
println("계산 실행")
return number
}
fun main(args: Array<String>) {
val memoizedLongComputation = Memoizer.memoize(::longComputation)
val result1 = memoizedLongComputation(43)
val result2 = memoizedLongComputation(43)
}
// 실행 결과 "계산 실행"이 1회 출력된다.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 }
}
}메모화한 함수는 인자가 같으면 항상 같은 결과를 내놓는다. 단지 결괏값을 반환하는데 걸리는 시간이 달라질 뿐이다. 원래 함수가 순수 함수라면 메모화한 함수도 순수 함수다.