Kotlin에서의 꼬리 재귀와 피보나치 수열

재귀는 함수가 자신을 다시 호출하는 프로그래밍 패턴입니다. Kotlin에서는 꼬리 재귀(tail recursion) 최적화를 지원하는데, 이것이 바로 tailrec 키워드의 역할입니다. 그렇다면 꼬리 재귀 최적화를 활용하여 피보나치 수열을 어떻게 구현할 수 있을까요? 이 문제를 해결하기 위해 아래와 같은 코드를 작성해 보았습니다.

// Recursion/Fibonacci.kt
package recursion
import atomictest.eq

fun fibonacci(n: Int): Long {
  // 내부에서 사용할 꼬리 재귀 함수를 정의합니다.
  tailrec fun fibonacci(
    n: Int,             // 남은 재귀 호출 횟수
    current: Long,      // 현재 피보나치 수
    next: Long          // 다음 피보나치 수
  ): Long {
    // n이 0일 경우, 현재의 피보나치 수를 반환합니다.
    if (n == 0) return current
    // 아닐 경우, n을 1 감소시키며 다음 두 피보나치 수를 인자로 재귀 호출합니다.
    return fibonacci(
      n - 1, next, current + next)
  }
  // 내부 함수를 초기 값과 함께 호출하여 결과를 반환합니다.
  return fibonacci(n, 0L, 1L)
}

fun main() {
  (0..8).map { fibonacci(it) } eq
    "[0, 1, 1, 2, 3, 5, 8, 13, 21]"
  fibonacci(22) eq 17711
  fibonacci(50) eq 12586269025
}

이 코드는 다소 복잡해 보이지만, 주요 아이디어는 내부 함수를 사용하여 꼬리 재귀를 구현하는 것입니다. 그렇다면 이 코드의 각 부분은 어떤 역할을 하는 것일까요?

1. fun fibonacci(n: Int): Long { ... }:

   • 외부 함수입니다. 사용자가 호출하는 함수입니다. 이 함수 내부에서 꼬리 재귀 함수를 정의하고 호출합니다.

2. tailrec fun fibonacci(n: Int, current: Long, next: Long): Long { ... }:

   • 꼬리 재귀로 구현된 내부 함수입니다. 외부 함수에서 호출되며, 실제 피보나치 수열을 계산합니다.

3. if (n == 0) return current:

   • 재귀 호출이 끝나는 기저 조건(base case)입니다. n이 0이면 현재의 피보나치 수를 반환합니다.

4. return fibonacci(n - 1, next, current + next):

   • 이 부분은 함수의 꼬리 위치에 있으며, 재귀 호출을 수행합니다. n을 1 감소시키고, current와 next 값을 갱신하여 함수를 다시 호출합니다.

5. return fibonacci(n, 0L, 1L):

   • 외부 함수에서 내부 함수를 호출하는 부분입니다. 초기 피보나치 값인 0과 1을 시작으로 수열을 계산하기 시작합니다.

6. fun main() { ... }:

   • 이 함수는 위에서 정의한 피보나치 함수를 테스트하기 위한 메인 함수입니다.

값 변화 관찰하기

fibonacci(3)을 호출해보면 값은 다음과 같이 변화합니다:

1. 첫 번째 호출: n = 3, current = 0, next = 1
2. 두 번째 호출: n = 2, current = 1, next = 1
3. 세 번째 호출: n = 1, current = 1, next = 2
4. 네 번째 호출: n = 0, current = 2, next = 3 → 2를 반환

이러한 방식으로 tailrec을 사용하면 재귀 호출이 깊어져도 스택 오버플로우 문제 없이 안정적으로 코드를 실행할 수 있습니다.

이 포스트를 통해 Kotlin에서 tailrec을 활용한 피보나치 수열 구현 방법을 살펴보았습니다. 이러한 패턴은 꼬리 재귀가 가능한 다양한 문제에 적용할 수 있으므로, Kotlin 개발에 있어서 매우 유용한 패턴 중 하나입니다.