코틀린과 재귀호출 이야기① - tailrec 을 활용한 꼬리호출 최적화(Tail Call Optimization)

우리는 하위 문제의 솔루션을 사용해서 문제에 대한 솔루션을 공식화할 수 있다면 재귀(recursion)로 구현할 수 있습니다. 재귀는 분명 매력적이긴 하지만, 조금만 복잡해져도 코드를 파악하기가 쉽지 않습니다.

 

재귀로 큰 문제를 해결할 때는 런타임 스택 오버플로우에 빠져서 효율성이 떨어질 수 있습니다. 그래서 개발자는 이러한 문제에 빠지지 않기 위해 꼬리 호출 최적화(tail call optimization) 이라고 불리는 테크닉을 이용할 수 있습니다. 거기에 데이터를 저장하는 알고리즘을 사용하면 성능은 더욱 향상되는데요. 아쉽게도 코틀린은 빌트인 메모이제이션(memoization) 을 지원해주지는 않지만 코틀린의 풍부한 문법을 활용한다면 표현력이 강한 메모이제이션 기능을 쉽게 만들 수 있습니다.

 

이번 포스팅에서는 재귀가 가지는 힘과 한계에 대해 알아보고 꼬리호출 최적화가 이슈들을 어떻게 다루는지에 대해서도 살펴보겠습니다. 그리고 다음 포스팅에서는 재귀의 우아함을 유지하면서 성능 향상을 위해서 함수 호출의 결과를 저장하는 메모이제이션 기법도 이어서 살펴보겠습니다.

 

재귀의 강점과 위험성

재귀를 사용하면 우리는 분할정복 기법(divide and conquer)을 사용할 수 있습니다. 분할정복 기법이란, 문제를 해결할 때 문제를 작게 쪼개서 각 부분의 솔루션을 구현한 후 각 결과를 다시 합쳐서 해결하는 기법을 말합니다.

 

아래의 예제는 퀵 정렬 알고리즘을 구현하는 코틀린 코드입니다.

fun quickSort(numbers: List<Int>): List<Int> =
  if (numbers.isEmpty()) {
    numbers
  } else {
    val pivot = numbers.first()
    val tail = numbers.drop()
    val lessOrEqual = tail.filter { e -> e <= pivot }
    val larger = tail.filter { e -> e > pivot }
    quickSort(lessOrEqual) + pivot + quickSort(larger)
  }

fun main() {
  println(quickSort(listOf(12, 5, 15, 12, 8, 19)))  // [5, 8, 12, 12, 15, 19]
}

 

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

 

이번에는 팩토리얼을 구하는 함수를 각각 재귀호출과 반복문을 통하여 구현해보고 이 둘을 비교해보도록 하겠습니다.

 

먼저, 재귀호출로 구현한 팩토리얼 구하는 함수입니다.

import java.math.BigInteger

fun factorialRec(n: Int): BigInteger =
  if (n <= 0) 1.toBigInteger() else n.toBigInteger() * factorialRec(n - 1)
  
fun main() {
  println(factorialRec(5))  // 120
}

factorialRec() 함수는 0보다 작거나 같은 값을 받으면 1을 리턴하고, 0보다 큰 값을 받으면 주어진 입력을 스스로 재귀적으로 호출하여 그 결과를 곱해서 리턴합니다.

 

다음은 반복문으로 구현한 팩토리얼 함수입니다.

import java.math.BigInteger

fun factorialIterative(n: Int): BigInteger =
  (1..n).fold(BigInteger("1")) { product, e -> product * e.toBigInteger() }
  
fun main() {
  println(factorialIterative(5))  // 120
}

fold() 함수는 인자로 람다와 함께 초기값을 받는다는 점만 제외하면 reduce() 함수와 비슷한 함수입니다. 사람마다 차이가 있겠지만 일반적으로 개발자들이 코드를 파악하고 받아들이기에는 재귀 솔루션이 좀 더 좋을 것입니다.

 

복잡한 문제를 해결할 때 가능하다면 반복문을 사용한 솔루션보다 재귀 솔루션을 사용하는 것이 더 이해하기 쉽지만, 안타깝게도 재귀는 반복문 솔루션이 겪지 않는 문제를 일으킵니다. 글의 서두에서 잠깐 언급한 것처럼, 재귀는 함수 수택을 증가시키고, 스택이 위험할 정도로 큰 레벨에 도달하면 프로그램이 뻗어버립니다.

 

예를 들어보겠습니다. 위에서 작성한 factorialIterative() 와 factorialRec() 함수에 아주 큰 값을 처리하도록 해보겠습니다.

fun main() {
  println(factorialIterative(50000))  // OK
  println(factorialRec(50000))  // Runtime Error : StackOverflow !
}

 

재귀를 이용한 솔루션이 이해하기에는 더 쉬울 수 있어도, 문제 풀이에는 적절하지 않습니다. 그래서 성능을 최우선으로 하는 알고리즘 문제 풀이 등에서는 재귀는 웬만하면 사용하지 않으려 하기도 합니다.

 

그렇다면 저 런타임 스택 오버플로우 문제를 어떻게 해결할 수 있을까요?

이제 꼬리호출 최적화(tail call optimization) 를 통해 위 문제를 해결해보겠습니다.

 

꼬리호출 최적화(Tail Call Optimization)

우리가 작성한 코드는 프로시저가 되고 생성된 바이트 코드는 결국 실행이 된다는 사실을 기억해봅시다. factorialIterative() 함수는 반복을 사용한 프로시저입니다. 그리고 반복을 사용하는 프로세스로 컴파일되고 실행될 것입니다.

 

이와 유사하게 factorialRec() 는 재귀 프로시저고 재귀 프로세스로 컴파일되고 실행될 것입니다. 하지만 여기서 반전이 있는데요. [컴퓨터 프로그램의 구조와 해석] 책에 의하면 실제로는 재귀 프로시저는 반복 프로세스로 컴파일될 수 있다는 것입니다. 이 말이 사실이라면 우리는 코드를 이해하기 쉬운 재귀로 작성하고, 런타임 시에는 보다 효율적인 반복으로 행동하게 할 수 있을 것입니다.

 

그리고 이 것이 가능하게 해주기 위해 코틀린은 tailrec 키워드를 제공해주고 있습니다. tailrec 을 사용한다면 우리는 코틀린 컴파일러에게 해당 함수를 반복을 사용한 프로시저로 처리하게 지시할 수 있습니다.

 

그렇다면 이제 factorialRec() 함수를 다시 작성해보겠습니다.

import java.math.BigInteger

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

앞에서 작성했던 factorialRec() 함수 맨 앞에 tailrec 이라는 키워드를 붙여줬습니다. 이러면 된 걸까요?

그렇지 않나 봅니다. 실행해봤더니 정상 동작하지 않습니다. 자세히 살펴보니 코틀린은 우리에게 "a function is marked as tial-recursive but no tial calls are found" 라고 경고를 해주고 있었습니다.

 

우리가 기억해야 할 것은 코틀린의 재귀를 반복으로 최적화하는 것은 호출이 마지막 위치일 경우에만 가능하다는 것입니다.

 

factorialRec() 함수의 n.toBigInteger() * factorialRec(n - 1) 코드를 보면 마치 factorialRec() 호출이 마지막에 실행된다고 착각할 수 있습니다. 하지만 함수가 리턴하기 전 수행하는 연산은 곱셈 연산입니다. 왜냐하면 곱셈 연산이 factorialRec() 함수 호출이 완료될 때까지 기다렸다가 해당 결과 값으로 곱셈을 하기 때문이지요. 그래서 각 재귀 호출들의 스택 사이즈가 커지는 것이기도 합니다.

 

Tail Call 이란, 재귀 호출이 진짜로 함수의 마지막 연산인 호출을 의미합니다. 이번에는 함수 이름을 factorial() 로 수정하고, 재귀 호출이 함수의 마지막 연산이 되도록 유의하여 코드를 다시 작성해보겠습니다. 

import java.math.BigInteger

tailrec fun factorial(n: Int, result: BigInteger = 1.toBigInteger()): BigInteger =
  if (n <= 0) result else factorial(n - 1, result * n.toBigInteger())
  
fun main() {
  println(factorial(5))  // 120
}

 

코드를 실행해보면 예상했던 결과가 나오고, 이제 아무런 경고도 나오지 않습니다. 이런 점을 봤을 때 코틀린 컴파일러가 뒤에서 조용히 최적화를 해서 반복을 사용한 프로시저로 함수를 변경했다는 사실을 알 수 있습니다.

 

그럼 앞서 factorialRec() 함수로는 런타임 스택 오버플로우를 일으켰던 50000 이란 숫자를 다시 입력해보겠습니다.

fun main() {
  println(factorial(50000)) // OK
}

결과가 매우 길어서 본문에는 첨부하지 않았지만, 이번에는 스택 오버플로우가 발생하지 않고 정상적으로 결과를 출력하는 것을 확인할 수 있습니다. 이는 tailrec 키워드를 통한 수정이 최적화를 이끌어 냈다는 증거로 볼 수 있겠습니다.

 

하지만 조금 찝찝할 수 있습니다. 아무리 결과를 직접 눈으로 확인했다지만, 컴파일된 결과를 직접 본 것도 아닌데 결과만으로 최적화됐다고 하다니.. 믿지 못할 수도 있습니다. 그래서 factorialRec() 함수와 tailrec 키워드를 적용한 factorial() 함수의 바이트 코드를 비교해봤습니다.

 

public final static factorialRec(I)Ljava/math/BigInteger;
   // ...
   L9
    LINENUMBER 34 L9
    ILOAD 0
    ICONST_1
    ISUB
    INVOKESTATIC MainKt.factorialRec (I)Ljava/math/BigInteger;
    ASTORE 2
   // ...

public final static factorial(ILjava/math/BigInteger;)Ljava/math/BigInteger;
   // ...
   L1
    LINENUMBER 37 L1
    ILOAD 0
    IFGT L2
    ALOAD 1
    GOTO L3
   // ...
   L10
    ASTORE 1
    ISTORE 0
    GOTO L0
   // ...

먼저 factorialRec() 의 바이트 코드에서 factorialRec() 를 재귀적으로 호출하기 위해서 INVOKEVIRTUAL 명령어가 사용되었습니다. 그리고 위 코드에선 생략됐지만 그 후 BigInteger 의 multiply() 메소드가 호출됩니다. 이는 재귀 프로시저가 재귀 프로세스로 컴파일됐다는 것을 보여줍니다.

 

반면에 tailrec 키워드를 적용한 factorial() 의 바이트코드는 INVOKEVIRTUAL 재귀 호출이 전혀 없습니다. 대신 IFGT 를 호출하고, goto 로 함수의 다른 부분으로 점프를 합니다. 이는 재귀 프로시저가 반복을 이용하는 프로세스로 컴파일됐다는 증거로 충분합니다.

 

정리를 하자면 tailrec 최적화는 재귀가 꼬리호출일 때만 동작합니다. tialrec 을 사용하기 위해서 우리는 factorialRec() 를 재귀 호출이 마지막에 오도록 factorial() 함수로 재작성 했습니다. 그래서 재귀가 마지막에 나오게 되었고, 꼬리 재귀로 평가되었습니다. 만약 재귀가 복잡하다면 tailrec 을 사용하는 것이 쉽지 않을 수도 있고 심지어 불가능 할 수도 있습니다.

 

꼬리호출 최적화는 재귀를 반복으로 변환해서 스택 레벨의 숫자를 제어합니다. 이런 방법은 효율성 측면에서 큰 향상을 가져옵니다. 하지만 함수를 반복적으로 호출하지 않고 저장된 값을 리턴한다면 실행을 더 빠르게 할 수 있는데요. 바로 메모이제이션 기법입니다. 이에 대해서는 다음 포스팅에서 이어서 다루겠습니다.