[Kotlin] tailrec 꼬리 재귀 함수에 대하여 알아보기

Tailrec(꼬리 재귀)란,

---

재귀 함수 내부의 재귀 호출에서 반환된 결괏값을 갖고 어떤 추가 연산도 수행하지 않으며 즉시 반환하는 식으로 작성된 재귀 함수를 꼬리 재귀(tail recursion) 함수라 합니다.

여기서 꼬리 재귀 함수를 알아가기 전에 재귀 함수를 간단히 알아봐야겠습니다.

재귀 함수란,

---

재귀 함수는 함수 내에서 자기 자신을 호출하는 방식으로 동작하는 함수를 말합니다. 이것은 간단하게 코드를 작성하고 이해하기 쉽게 만들 수 있지만, 재귀 호출이 깊어지면 스택 오버플로우와 같은 문제가 발생할 수 있습니다. 

재귀 함수란,

---

재귀 함수는 함수 내에서 자기 자신을 호출하는 방식으로 동작하는 함수를 말합니다. 이것은 간단하게 코드를 작성하고 이해하기 쉽게 만들 수 있지만, 재귀 호출이 깊어지면 스택 오버플로우와 같은 문제가 발생할 수 있습니다. 

코드로 보는 '재귀 함수'와  '꼬리 재귀 함수'

---

피보나치 수를 활용해서 재귀 함수와 꼬리 재귀 함수를 알아보겠습니다.

 

1. 재귀 함수 코드

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

 

2. 꼬리 재귀 함수 코드

tailrec fun fibonacciTailrec(n: Int, a: Int = 0, b: Int = 1): Int {
    return when (n) {
        0 -> a
        1 -> b
        else -> fibonacciTailrec(n - 1, b, a + b)
    }
}

 

이 두 함수는 피보나치 수를 계산하는 데 사용되는 코드입니다. 그러나 재귀 함수의 경우에는 재귀 호출 과정에서 매번 스택에 함수의 활성 레코드가 쌓이므로 스택 오버 플로우의 위험이 있습니다. 반면에 꼬리 재귀 함수는 컴파일러에 의해 반복문으로 최적화될 수 있으며, 스택을 쌓지 않고 재활용되므로 더욱 효율적입니다.

꼬리 재귀 함수의 특징과 장점 

---

• 최적화 가능한 재귀 구조 : 꼬리 재귀 함수는 컴파일러가 반복문으로 최적화할 수 있는 구조를 가지고 있습니다. 그래서 스택 오버 플로우의 위험을 감소시키고 성능을 향상할 수 있습니다.
• 스택 메모리 최적화 : 꼬리 재귀 함수는 반복문으로 변환되므로 스택에 각 호출의 프레임을 계속 쌓지 않고 동일한 스택 프레임을 재사용할 수 있습니다. 

이러한 이유로 Kotlin에서는 코드의 간단성과 성능 향상을 동시에 얻고자 할 때, 특히 재귀 함수를 사용해야 하는 상황에서는 꼬리 재귀 함수를 고려해 보고 사용하면 좋을 것 같습니다.