kodagi4.md

4장 재귀, 공재귀, 메모화

• 재귀, 공재귀, 꼬리 재귀 함수의 구현 방법을 알아본다.
• TCE를 사용해 꼬리 재귀 호출을 최적화한다.
• 람다를 재귀적으로 만든다.
• memorization을 적용해 계산 속도를 높인다.

4.1 공재귀와 재귀

• 재귀(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"

1. 공재귀를 그대로 사용할 경우, 리스트의 첫번째 요소 대신 마지막 요소를 이용해 단계별로 진행함

   만약 리스트 대신 단일 연결리스트를 사용할 경우 매우 비효율적

   fun toString(list: List<Char>, s: String): String = if (list.isEmpty()) {
   		s
   } else {
   		toString(list.subList(0, list.size - 1), prepend(s, list.last()))
   }

2. 재귀로 구현할 경우

   재귀는 최종 조건(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()이라는 추가적인 연산을 수행하므로 꼬리 재귀 함수 X

  fun 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를 사용하면 된다.

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.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)
  }

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)}

• 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 }
                }
            }

4.5 메모화한 함수는 순수 함수인가

메모화한 함수는 인자가 같으면 항상 같은 결과를 내놓는다. 단지 결괏값을 반환하는데 걸리는 시간이 달라질 뿐이다. 원래 함수가 순수 함수라면 메모화한 함수도 순수 함수다.