Tailrec?
Tailrec은 언어 차원에서 제공하는 기능으로 해당 키워드가 명시된 함수가 꼬리 재귀의 조건에 부합하지 않으면 IDE에서 경고 메시지를 주고, 컴파일러 최적화가 발생하지 않는다.
꼬리 재귀란?
꼬리 재귀란 어떤 함수가 직간접적으로 자기 자신을 호출하면서도 그 호출이 마지막 연산인 경우를 뜻한다.
그리고 이 마지막 연산인 호출을 '꼬리 호출'이라 한다.
여기서 주의할 점은 마지막 호출에서 재귀 함수만 호출되어야 한다는 것이다.
일반적으로 재귀 호출이 반복되면서 깊이가 깊어지면 스택 오버플로우가 발생할 수 있는데, 꼬리 호출일 때는
스택 오버플로우가 발생하지 않는다.
왜냐하면 컴파일러가 해당 문제를 일으키는 스택 프레임을 재사용하기 때문이다.
이 경우 재귀를 사용했지만, 반복문을 사용한 것처럼 최적화할 수 있다.
아래의 factorial의 경우 재귀 함수가 스스로 자신만을 재호출 하고 값을 리턴하는 구조이기 때문에 꼬리 재귀의
형태를 가지고 있다. tailrec 키워드를 사용하여 반복하도록 만들 수 있다.
fun factorial(n: Int, acc: Int): Int {
return if (n <= 0) {
acc
} else {
factorial(n-1, n*acc)
}
}
fun main(args: Array<String>) {
println("factorial(10) : ${factorial(10, 1)}" )
}
하지만 아래의 경우 재귀 함수만을 호출하는 게 아닌 뭔가 추가적인 연산이 들어갔으므로 꼬리 재귀가 아니게 된다.
fun factorial_plus_n(n: Int, acc: Int): Int {
return if (n <= 0) {
acc
} else {
1 + factorial_plus_n(n-1, n*acc)
}
}
tailrec 키워드를 사용하여 만든 factorial 함수
override fun onCreate(savedInstanceState: Bundle?) {
super.onCreate(savedInstanceState)
setContentView(R.layout.activity_main)
//-----
factorial(5)
//-----
}
private tailrec fun factorial(n: Int, acc: Int = 1) : Int =
if(n == 1) acc else factorial(n - 1, n * acc)
또한 tailrec 키워드를 붙인다고 해서 무조건 '루프 코드'로 변경해주는 것이 아니고, 꼬리 재귀일 경우에만 루프 코드로 바뀐다. 혹여 아닌 코드에 붙이면 경고 메시지가 뜬다.
'Kotlin' 카테고리의 다른 글
[Kotlin] Flow (0) | 2021.08.13 |
---|---|
[Kotlin] 리스트를 통한 명령형 방식과 함수형 방식 비교 (0) | 2021.08.04 |
[Kotlin] 커링(Currying) 함수 (0) | 2021.08.03 |
[Kotlin] Sealed Class (0) | 2021.07.30 |
[코틀린] apply, with, let, also, run의 용도 (0) | 2021.03.17 |