Kotlin에서의 tailrec 이해하기

재귀는 함수가 자기 자신을 호출하는 방식입니다. 그러나 재귀를 과도하게 사용하면 스택 오버플로우와 같은 문제에 직면할 수 있습니다. Kotlin은 이 문제를 해결하기 위한 강력한 키워드, tailrec을 제공합니다.

---

재귀와 스택

먼저 기본적인 CS 관점에서 보면, 프로그램은 함수 호출을 스택 메모리에 저장합니다. 일반적인 재귀 호출마다 새로운 스택 프레임이 추가됩니다. 이러한 스택 프레임이 너무 많아지면, 스택 오버플로우가 발생합니다.

Tail Recursion과 tailrec

Tail Recursion은 재귀의 특별한 형태입니다. 함수의 마지막 연산이 자기 자신의 호출인 경우를 의미합니다. 이러한 특징 덕분에 컴파일러나 인터프리터는 재귀 호출을 반복문처럼 최적화할 수 있습니다.

Kotlin에서 tailrec 키워드는 이러한 최적화를 명시적으로 요청하는 방법입니다. tailrec이 붙은 함수는 컴파일러에 의해 최적화되어, 새로운 스택 프레임을 생성하지 않고 재사용합니다. 결과적으로 깊은 재귀 호출도 안전하게 처리할 수 있습니다.

---

사용 예시

1. 일반적인 재귀를 사용한 팩토리얼 계산

fun factorial(n: Int): Int {
    return if (n == 1) 1 else n * factorial(n - 1)
}

이 함수는 n이 감소하면서 재귀적으로 호출됩니다. 그러나 큰 n 값에 대해 호출하면 스택 오버플로우 오류가 발생합니다.

2. tailrec을 사용한 팩토리얼 계산

tailrec fun factorial(n: Int, accumulator: Int = 1): Int {
    return if (n == 1) accumulator else factorial(n - 1, n * accumulator)
}

이 버전은 이전 값들의 누적 결과를 accumulator로 전달합니다. 함수의 마지막 행동은 자신을 다시 호출하는 것이므로, tailrec으로 표시될 수 있습니다. 이로 인해 이 함수는 n이 아무리 크더라도 안전하게 실행됩니다.

---

값 변화 관찰하기

tailrec factorial 함수를 factorial(5)로 호출한다고 가정해봅시다:

1. 첫 번째 호출: n = 5, accumulator = 1
2. 두 번째 호출: n = 4, accumulator = 5
3. 세 번째 호출: n = 3, accumulator = 20
4. 네 번째 호출: n = 2, accumulator = 60
5. 다섯 번째 호출: n = 1, accumulator = 120
6. 반환 값: 120

위의 과정에서 스택 프레임이 추가되지 않습니다. 컴파일러는 재귀 호출을 반복문처럼 처리합니다.

---

tailrec과 일반 재귀의 차이점

1. 스택 사용: 일반 재귀는 각 호출마다 스택 프레임을 추가합니다. tailrec은 스택 프레임을 재사용합니다.
2. 성능: tailrec은 최적화되므로 깊은 재귀 호출에서도 안전하며, 일반 재귀에 비해 더 빠릅니다.
3. 사용 조건: 모든 재귀 함수가 꼬리 재귀가 될 수는 없습니다. 꼬리 재귀는 함수의 마

지막 연산이 해당 함수의 호출일 때만 사용할 수 있습니다.

---

tailrec이 사용 가능한 경우와 재귀만 사용 가능한 경우

1. tailrec 사용 가능: 함수의 마지막 동작이 해당 함수의 호출일 때. 위의 팩토리얼 예제와 같이 중간 결과를 누적 인자로 전달하는 경우가 일반적입니다.
2. 재귀만 사용 가능: 함수의 마지막 동작 이외에도 함수를 호출해야 하는 경우. 예를 들면, 트리를 순회하거나 복잡한 데이터 구조를 탐색할 때입니다.

---

시나리오: 피보나치 수열

1. 일반적인 재귀

fun fibonacci(n: Int): Int {
    if (n <= 1) return n
    return fibonacci(n - 1) + fibonacci(n - 2)
}

이 코드는 간단하지만 효율적이지 않습니다. 작은 n에 대해서도 같은 값을 여러 번 계산합니다.

2. tailrec 사용

tailrec fun fibonacci(n: Int, a: Int = 0, b: Int = 1): Int {
    return if (n == 0) a else fibonacci(n - 1, b, a + b)
}

이 버전은 두 개의 연속된 피보나치 수를 인자로 전달합니다. 이렇게 하면 각 호출에서 중복 계산 없이 다음 숫자만 계산합니다.

---

값 변화 관찰하기 (fibonacci(5)의 경우)

1. 첫 번째 호출: n = 5, a = 0, b = 1
2. 두 번째 호출: n = 4, a = 1, b = 1
3. 세 번째 호출: n = 3, a = 1, b = 2
4. 네 번째 호출: n = 2, a = 2, b = 3
5. 다섯 번째 호출: n = 1, a = 3, b = 5
6. 여섯 번째 호출: n = 0, a = 5, b = 8
7. 반환 값: 5

---

이 글을 통해 Kotlin의 tailrec 키워드와 그 원리에 대해 깊게 알아보았습니다. 이러한 최적화를 활용하면, 깊은 재귀 호출에서도 안전하고 효율적인 코드를 작성할 수 있습니다.