**꼬리 재귀(Tail Recursion)**는 함수 내에서 재귀 호출이 가장 마지막에 실행되는 작업인 경우를 말합니다. 즉, 재귀 함수를 호출한 후에 그 반환 값을 가지고 추가적인 연산(예: 곱셈, 덧셈, 다른 함수 호출 등)을 수행하지 않고, 재귀 호출의 결과가 바로 현재 함수의 최종 결과가 되어야 합니다.
이러한 구조는 컴파일러가 꼬리 호출 최적화(TCO)를 적용하여 재귀 호출을 반복문(loop)처럼 변환할 수 있게 만들어, 스택 프레임이 계속 쌓이는 것을 방지합니다.
다음은 팩토리얼을 계산하는 함수를 꼬리 재귀 형태로 작성한 예입니다. tailrec 변경자를 사용하여 코틀린 컴파일러에게 이 함수가 꼬리 재귀임을 알립니다.
예시: 팩토리얼 (꼬리 재귀)
// 꼬리 재귀 형태의 팩토리얼 함수
tailrec fun factorialTailRecursive(n: Int, accumulator: Long = 1L): Long {
// 기본 사례: n이 1 이하이면, 누적된 결과(accumulator)를 반환
if (n <= 1) {
return accumulator
} else {
// 재귀 호출이 함수의 가장 마지막 작업입니다.
// 다음 호출로 (n-1)과 (현재 n * 이전 accumulator) 값을 전달합니다.
return factorialTailRecursive(n - 1, n * accumulator)
}
}
fun main() {
println("5! (꼬리 재귀): " + factorialTailRecursive(5)) // 출력: 120
// 매우 큰 값도 스택 오버플로 없이 계산 가능합니다.
// 예를 들어 factorialTailRecursive(20000) 호출도 잘 동작합니다.
// (결과값이 매우 커서 Long 타입 범위를 초과할 수 있으므로 주의)
println("20! (꼬리 재귀): " + factorialTailRecursive(20))
}
꼬리 재귀인 이유:
위 factorialTailRecursive 함수에서 else 블록 안의 return factorialTailRecursive(n - 1, n * accumulator) 부분이 핵심입니다.
n - 1과 n * accumulator라는 다음 호출을 위한 인자들을 계산합니다.factorialTailRecursive 함수를 호출하여 그 결과를 즉시 반환합니다.다음은 동일한 팩토리얼 계산을 하지만, 꼬리 재귀가 아닌 일반적인 재귀 형태로 작성한 예입니다.
예시: 팩토리얼 (꼬리 재귀 아님)
// 일반 재귀 (꼬리 재귀 아님)
fun factorialStandard(n: Int): Long {
// 기본 사례: n이 1 이하이면 1을 반환
if (n <= 1) {
return 1L
} else {
// 재귀 호출 factorialStandard(n - 1)의 결과를 받은 후,
// 그 결과에 현재 n을 곱하는 추가 연산이 있습니다.
return n * factorialStandard(n - 1)
}
}
fun main() {
println("5! (일반 재귀): " + factorialStandard(5)) // 출력: 120
// 매우 큰 값(예: 20000)에 대해 factorialStandard를 호출하면
// 스택 오버플로 오류(StackOverflowError)가 발생할 가능성이 높습니다.
try {
println("계산 시도: factorialStandard(20000)")
factorialStandard(20000) // StackOverflowError 발생 가능
} catch (e: StackOverflowError) {
println("20000! (일반 재귀): 스택 오버플로 발생!")
}
}
꼬리 재귀가 아닌 이유:
else 블록의 return n * factorialStandard(n - 1) 부분을 보면, factorialStandard(n - 1) 재귀 호출이 먼저 실행되고, 그 함수의 반환 값이 돌아온 후에 현재 n 값과 곱셈 연산이 수행됩니다. 이렇게 재귀 호출 이후에 추가적인 작업이 남아있으면 꼬리 재귀가 아닙니다. 따라서 컴파일러는 이를 단순 반복문으로 최적화할 수 없습니다.
**꼬리 호출 최적화(TCO)**는 특정 조건을 만족하는 꼬리 재귀 함수에 대해 컴파일러가 수행하는 최적화 기법입니다. 코틀린에서는 함수에 tailrec 변경자를 명시적으로 붙여주면 컴파일러가 이 함수를 TCO 대상으로 간주합니다.
TCO의 핵심은 재귀 호출 시 새로운 스택 프레임을 생성하는 대신, 현재 스택 프레임을 재사용하도록 코드를 변환하는 것입니다. 이는 실질적으로 재귀 함수를 **반복문(loop)**과 유사한 형태로 바꾸는 것과 같습니다. 이 덕분에 아무리 많은 재귀 호출이 일어나도 스택 메모리가 계속 증가하지 않아 스택 오버플로 오류를 방지할 수 있습니다.
sumEvenNumbersDownToZero