재귀 (Recursion) 와 꼬리 재귀 (Tail Recursion)

우리가 아는 재귀함수는 반복문을 사용하지 않고 함수 내부에서 자기 자신을 호출하는 것이다.

예제 코드는 흔히 아는 팩토리얼 n! = n * (n - 1) * (n- 2) * ... 3 * 2 * 1 로 시작한다.

fun factorial(n: Int): Int = when {
    0 -> 1
    else -> n * factorial(n - 1)
}

재귀함수는 스택 프레임에 반복되는 수 만큼 차곡차곡 쌓이기 때문에 반복되는 수가 많다면

흔히 말하는 스택 오버 플로우가 발생하게 된다.

이런 문제를 해결하기 위한 몇몇 방법들이 있는데 오늘은 꼬리 재귀를 공부한다.

꼬리 재귀란 어떤 함수가 직간접적으로 자기 자신을 호출하면서도 그 호출이 마지막 연산인 경우를 말한다.

즉, 자기 자신을 마지막에 호출하는 함수 라고 생각하면 된다.

꼬리 재귀를 사용하면 스택 프레임을 재사용하여 최적화가 가능하다.

함수형 언어를 포함한 대부분의 모던 언어들은 꼬리 재귀에 의한 컴파일러 최적화를 지원한다. 따라서 재귀는 꼬리 재귀로 최적화 해주는게 좋다.

만약 컴파일러에서 지원하지 않는다면, 가독성을 고려하여 취향대로 구현하면 된다.

꼬리 재귀는 컴파일러에서 최적화되는데 코틀린같은 경우에는 tailrec 키워드를 통해 재귀를 꼬리재귀로 최적화 할 수 있다.

tailrec fun factorial(n: Int, acc: Int = 1): Int = when (n) {
    0 -> acc
    else -> factorial(n - 1, n * acc)
}

tailrec 키워드가 붙은 재귀 함수는 컴파일러가 바이트 코드로 바꿀때 최적화 하게 되는데

내부적으로 for loop로 자동으로 변환한다.