3.4.5 꼬리 재귀 함수

코틀린은 꼬리 재귀(tail recursive) 함수에 대한 최적화 컴파일을 지원한다. 이번에는 어떤 정수 배열에 대한 이진 검색(binary search)을 수행하는 함수를 작성해보자. 배열이 오름차순으로 정렬돼 있다고 가정하고, 검색 함수를 재귀적으로 작성하자.

tailrec fun binIndexOf(
  x: Int,
  array: IntArray,
  from: Int = 0,
  to: Int = array.size
): Int {
  if (from == to) return -1
  val midIndex = (from + to - 1) / 2
  val mid = array[midIndex]
  return when {
    mid < x ->binIndexOf(x, array, midIndex + 1, to)
    mid > x ->binIndexOf(x, array, from, midIndex)
    else ->midIndex
  }
}

이 정의는 이진 검색의 아이디어를 깔끔하게 보여준다. 하지만 일반적으로 비재귀 버전과 비교해보면, 성능 차원에서 약간의 부가 비용이 발생하고 스택 오버플로(stack overflow)가 발생할 가능성이 있다. 하지만 코틀린에서는 함수에 tailrec을 붙이면 컴파일러가 재귀 함수를 비재귀적인 코드로 자동으로 변환해준다. 그 결과 양쪽의 장점, 즉 재귀 함수의 간결함과 비재귀 루프의 성능만을 취할 수 있다. 즉, 앞에서 본 함수는 다음 코드와 같다.