[Kotlin][프로그래밍 개념] Tail Recursion Optimization (Tail Call Optimization)

출처

ChatGPT

---

Tail Recursion Optimization 또는 Tail Call Optimization(TCO)는 함수가 tail call로 끝나는 재귀 호출을 최적화하여 스택 메모리 사용을 줄이는 기법이다. 이 최적화는 함수 호출을 효율적으로 처리해 StackOverflowError를 방지할 수 있다.
 

1. Tail Recursion(꼬리 재귀)란?

Tail Recursion이란, 함수의 마지막 동작이 자신을 호출하는 형태의 재귀를 말한다. 즉, 함수가 재귀적으로 호출될 때 그 결과가 곧바로 반환되어 더 이상의 계산이 필요없는 경우를 말한다.
 
아래 함수는 tail recursive이다.

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

 
여기서 tailRecFactorial 함수의 마지막 동작은 tailRecFactorial(n - 1, n * accmulator)을 호출하는 것이다. 호출된 후에는 아무런 추가 작업이 없다. 이와 같은 형태를 tail call이라고 부른다.
 

2. Tail Recursion Optimization의 원리

Tail Recursion Optimization은 tail recursive 함수 호출 시 새로운 스택 프레임을 생성하지 않고 현재 스택 프레임을 재사용하도록 최적화하는 것이다.
 
보통의 재귀 호출은 각 호출마다 새로운 스택 프레임을 생성해 메모리에 저장한다. 이러한 방식은 재귀 깊이가 깊어질수록 많은 스택 메모리를 소비하고, 결국 StackOverflowError를 발생시킬 수 있다.
 
그러나 tail call의 경우 현재 스택 프레임을 재사용할 수 있다. 왜냐하면 호출이 완료된 후에 할 일이 더 이상 없기 때문이다. 따라서 컴파일러가 스택을 덮어쓰고, 새로운 스택 프레임을 추가하지 않으므로 메모리 사용이 효율적이다.
 

3. Tail Recursion Optimization의 예제

일반 재귀와 Tail Recursion을 비교해보자.
 

일반 재귀(Non-Tail Recursion) 예제

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

 
이 함수는 factorial(n - 1) 호출 후에 'n * ' 연산을 수행해야 한다. 따라서 이 재귀는 tail recursive가 아니다.
 
Tail Recursive 예제

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

 
이 함수는 tail recursive이다. tailRecFactorial(n - 1, n * accumulator)이 마지막으로 호출되는 함수이며, 그 후에 다른 작업을 수행하지 않는다.
 
Tail Recursion Optimization이 작동한다면, tailRecFactorial은 재귀적으로 호출되지만 스택 프레임이 추가되지 않고 현재 스택 프레임을 재사용한다.
 

4. Kotlin에서 Tail Recursion Optimization 적용

코틀린에서는 tailrec 키워드를 사용해 Tail Recursion Optimization이 가능함을 명시적으로 요청할 수 있다.

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

 
여기서 tailrec 키워드를 사용하면 코틀린 컴파일러가 이 함수가 tail call 임을 인식하고 최적화를 적용할 수 있다. 만약 함수가 tail call이 아닌 경우, 컴파일러는 오류를 발생시킨다.
 
 
※ 자바는 Tail Recursion Optimization을 지원하지 않는다. 하지만 대체하는 방법들이 존재한다.

• 관련 글 -> [Java] Tail Recursion Optimization 대체 방법

 

5. Tail Recursion Optimization의 장점

효율적인 메모리 사용

Tail Recursion Optimization을 통해 스택 메모리를 절약할 수 있으며, 이는 StackOverflowError를 방지한다.

더 나은 성능

최적화된 코드는 더 적은 메모리를 사용하고, 스택 오버헤드가 없기 때문에 더 빠르게 실행될 수 있다.

가독성 및 유지보수성

재귀적인 접근 방식을 유지하면서도 스택 사용을 줄일 수 있으므로, 복잡한 반복 구조보다 간결하고 이해하기 쉬운 코드 작성이 가능하다.
 

6. 제약 사항 및 주의점

• 모든 컴파일러가 Tail Recursion Optimization을 지원하는 것은 아니다. 예를 들어, 자바의 표준 JDK는 Tail Recursion Optimization을 자동으로 지원하지 않지만, Kotlin 컴파일러는 tailrec 키워드로 이를 지원한다.

• 관련 글 -> [Java] Tail Recursion Optimization 대체 방법

• 재귀 호출이 반드시 함수의 마지막 동작이어야 하며, 다른 연산이 뒤따라서는 안 된다.
• 재귀 호출이 필요한 모든 문제에 Tail Recursion Optimization을 적용할 수 있는 것은 아니다. 알고리즘의 특성에 따라 최적화 가능 여부가 결정된다.

 

결론

Tail Recursion Optimization은 재귀 호출의 성능을 향상시키고 메모리 사용을 줄이는 중요한 최적화 기법이다. Kotlin과 같은 현대적인 언어는 이를 직접적으로 지원하며, 이 기법을 잘 활용하면 효율적인 재귀 알고리즘을 작성할 수 있다. tailrec 키워드를 사용해 명시적으로 컴파일러에게 최적화를 요청하는 것이 좋으며, 이를 통해 코드의 안정성과 성능을 모두 개선할 수 있다.