PHpullh
학습 라이브러리/Kotlin/꼬리 재귀 (Tail Recursion)

KOTLIN · 함수

꼬리 재귀 (Tail Recursion)

tailrec 키워드는 꼬리 재귀 함수를 반복문으로 최적화합니다. 스택 오버플로 없이 재귀를 사용할 수 있습니다.

함수고급tailrecrecursionoptimizationstack-safe

핵심 설명

tailrec 키워드는 꼬리 재귀 함수를 반복문으로 최적화합니다. 스택 오버플로 없이 재귀를 사용할 수 있습니다.

Kotlin code

tailrec fun factorial(n: Long, acc: Long = 1L): Long =
    if (n <= 1) acc
    else factorial(n - 1, n * acc)

tailrec fun gcd(a: Int, b: Int): Int =
    if (b == 0) a else gcd(b, a % b)

tailrec fun findIndex(
    list: List<Int>, target: Int, index: Int = 0
): Int = when {
    index >= list.size -> -1
    list[index] == target -> index
    else -> findIndex(list, target, index + 1)
}

fun main() {
    println(factorial(20))        // 2432902008176640000
    println(gcd(48, 18))          // 6
    println(findIndex(listOf(3, 7, 1, 9), 1)) // 2
}

학습 팁

tailrec이 적용되려면 재귀 호출이 함수의 마지막 연산이어야 합니다. 컴파일러가 최적화 불가 시 경고를 표시합니다.

주의할 점

factorial(n - 1) * n처럼 재귀 호출 뒤에 연산이 있으면 꼬리 재귀가 아닙니다. 누산기(accumulator) 패턴으로 변환하세요.

자주 묻는 질문

꼬리 재귀 (Tail Recursion)란 무엇인가요?

tailrec 키워드는 꼬리 재귀 함수를 반복문으로 최적화합니다. 스택 오버플로 없이 재귀를 사용할 수 있습니다.

꼬리 재귀 (Tail Recursion) 학습 시 주의할 점은 무엇인가요?

factorial(n - 1) * n 처럼 재귀 호출 뒤에 연산이 있으면 꼬리 재귀가 아닙니다. 누산기(accumulator) 패턴으로 변환하세요.