[Kotlin] tailrec(꼬리 재귀)란

 

1. 꼬리 재귀란?

꼬리 재귀(Tail Recursion)는 함수의 마지막 연산이 재귀 호출임을 의미합니다.

일반적인 재귀 호출과는 다르게, 꼬리 재귀는 함수가 자신을 호출함과 동시에 종료 됩니다.

이러한 특성 때문에, 꼬리 재귀는 컴파일러나 인터프리터에 의해 루프로 변환될 수 있습니다.

 

 

2. 꼬리 재귀의 기본 사용 방법

Kotlin에서는 tailrec 키워드를 사용해 꼬리 재귀 함수를 작성할 수 있습니다. 팩토리얼 계산을 예를 들어보죠.

 

(1) 기본 재귀 함수 (꼬리 재귀 함수 ❌)

fun factorial(n: Int): Long {
    return if (n <= 1) {
        1
    } else {
        n * factorial(n - 1)
    }
}

이 코드는 n * factorial(n - 1)이라는 연산을 수행하기 때문에,

재귀 호출이 끝나고 나서야 이전의 함수 호출 결과를 이용해 곱셈을 수행할 수 있습니다.

따라서 각 재귀 호출마다 새로운 스택 프레임이 필요하게 됩니다.

 

일반적인 재귀 함수는 자신을 호출할 때마다 스택에 새로운 프레임을 생성하여 함수의 상태를 저장합니다.

이것은 메모리를 많이 차지하고, 호출 수가 많아지면 스택 오버플로우를 일으킬 수 있습니다.

 

(2) 꼬리 재귀 함수

tailrec fun factorial(n: Int, acc: Long = 1): Long {
    return if (n <= 1) {
        acc
    } else {
        factorial(n - 1, n * acc)
    }
}

이 코드는 n * acc의 결과를 다음 재귀 호출에 바로 전달하므로,

각 재귀 호출이 끝나는 즉시 스택 프레임을 제거할 수 있습니다. 이로 인해 메모리 사용량이 크게 줄어듭니다.

꼬리 재귀 함수는 자신을 호출한 후 추가적인 연산없이 바로 결과를 반환합니다.

즉, 함수의 마지막 연산이 재귀 호출입니다.

 

이런 특성으로 인해 컴파일러나 인터프리터는 꼬리 재귀 함수를 처리할 때

현재의 스택 프레임을 재활용하고, 새로운 스택 프레임을 생성하지 않아도 됩니다.

이를 통해 메모리 사용량을 크게 줄일 수 있으며, 스택 오버플로우를 방지할 수 있습니다.

 

 

3. 꼬리 재귀와 유무에 따른 성능 차이

(1) 메모리 사용량

일반적인 재귀 함수는 함수를 호출할 때마다 스택에 새로운 프레임을 생성해 함수의 상태를 저장합니다.
따라서 재귀 호출이 많아질수록 메모리 사용량이 증가한다는 뜻입니다.

반면, 꼬리 재귀를 사용하면 새로운 스택 프레임을 생성하지 않고
현재의 스택 프레임을 재사용합니다. 이로 인해 메모리 사용량이 크게 줄어들 수 있죠.

(2) 실행 속도

일반적인 재귀 함수는 함수 호출과 반환 과정에서 스택 프레임을 생성하고 제거하는 비용이 발생합니다.
이로 인해 프로그램의 실행 속도가 느려질 수 있습니다.

반면, 꼬리 재귀를 사용하면 이러한 비용이 발생하지 않기 때문에 프로그램의 실행 속도가 빨라질 수 있습니다.

 

두 코드의 차이를 그림으로 확인하면 더 크게 와닿을 것 같습니다.

- 꼬리 재귀를 사용하지 않은 경우:
   factorial(5)
   -> 5 * factorial(4)
   --> 4 * factorial(3)
   ---> 3 * factorial(2)
   ----> 2 * factorial(1)
   -----> 1
   <---- 2
   <--- 6
   <-- 24
   <- 120

- 꼬리 재귀를 사용한 경우:
   factorial(5, 1)
   -> factorial(4, 5)
   -> factorial(3, 20)
   -> factorial(2, 60)
   -> factorial(1, 120)
   -> 120

 

 

4. 스택 오버플로우와 꼬리 재귀

스택 오버플로우는 프로그램이 사용하는 스택 메모리가 너무 커져서 스택의 용량을 초과할 때 발생하는 오류입니다.

재귀함수는 자신을 다시 호출하며, 이때마다 새로운 스택 프레임이 생성됩니다.

만약 재귀 호출이 너무 많아져서 스택 공간을 모두 사용하게 되면 스택 오버플로우가 발생합니다.

 

하지만 꼬리 재귀는 함수의 마지막 연산이 재귀 호출이므로, 이미 사용한 스택 프레임을 재활용할 수 있습니다.

이렇게 한다면 함수 호출이 많아지더라도 스택 오버플로우를 방지할 수 있습니다.

 

 

5. 꼬리 재귀의 활용

꼬리 재귀는 재귀 호출이 많아질 경우 스택 오버플로우를 방지하는데 큰 역할을 합니다.

예를 들어, 사용자로부터 입력을 받는 상황을 가정해보죠.

사용자가 잘못된 입력한다면, 에러 메시지를 출력하고 다시 입력을 받아야 합니다.

꼬리 재귀는 이것을 반복문 없이 구현할 수 있습니다.

tailrec fun inputView(prompt: String): String {
    print(prompt)
    val userInput = readLine()
    
    return if (userInput.isValid()) {
        userInput
    } else {
        inputView("Invalid input. $prompt")
    }
}

위의 코드는 사용자 입력이 유효하지 않은 경우 자신을 다시 호출합니다.

이렇게 하면 재귀 호출이 많아져도 스택 오버플로우가 발생하지 않습니다.

 

 

🖇️ tailrec 정리

tailrec 키워드가 붙은 함수는 함수의 마지막 작업이 자기자신을 호출 하는 형태여야 한다.
tailrec 키워드는 구현된 함수가 꼬리 재귀여야 함을 컴파일러에 알리고,
함수가 실제로 꼬리 재귀가 아닌 경우 컴파일러가 오류를 출력하도록 한다.
함수의 내용이 변경되어, 더이상 꼬리 재귀가 아닐 경우 예기치 못한 성능 저하를 방지할 수 있다.