Tail Recursion Optimization

재귀 함수는 자기 자신을 호출한다. 코드가 문제의 구조를 그대로 보여준다는 장점이 있지만, 호출이 깊어지면 스택도 함께 쌓인다.

그런데 재귀 호출이 함수의 마지막 작업이라면 이야기가 달라진다. 이전 호출로 돌아와 처리할 일이 없으므로, 컴파일러는 새 스택 프레임을 만드는 대신 현재 함수의 인자만 바꾸며 반복할 수 있다. 이것이 tail recursion optimization, 즉 꼬리 재귀 최적화다.

일반 재귀는 무엇을 기억해야 할까?

리스트 길이를 재귀로 구해보자.

def length[A](xs: List[A]): Int =
  xs match {
    case Nil       => 0
    case _ :: tail => 1 + length(tail)
  }

length(tail)이 끝나도 곧바로 반환할 수 없다. 호출 결과에 1을 더해야 하기 때문이다.

length(List(1, 2, 3))
= 1 + length(List(2, 3))
= 1 + (1 + length(List(3)))
= 1 + (1 + (1 + length(Nil)))

각 호출은 나중에 수행할 + 1을 기억해야 한다. 이 정보가 호출 스택에 쌓이고, 입력이 충분히 크면 StackOverflowError가 발생할 수 있다.

마지막 작업이 재귀 호출이라면

아직 계산하지 않은 + 1을 남겨두지 말고, 지금까지의 길이를 인자로 전달할 수 있다.

import scala.annotation.tailrec

def length[A](xs: List[A]): Int = {
  @tailrec
  def loop(remaining: List[A], count: Int): Int =
    remaining match {
      case Nil       => count
      case _ :: tail => loop(tail, count + 1)
    }

  loop(xs, 0)
}

count는 지금까지 계산한 결과를 들고 다니는 **누산기(accumulator)**다.

loop(List(1, 2, 3), 0)
loop(List(2, 3),    1)
loop(List(3),       2)
loop(Nil,           3)
→ 3

loop(tail, count + 1)이 실행된 뒤에는 이전 호출에서 할 일이 없다. 컴파일러는 이 직접적인 자기 호출을 개념적으로 다음과 같은 반복으로 바꿀 수 있다.

remaining = tail
count = count + 1
처음으로 이동

소스 코드에서는 재귀지만, 실행할 때는 새로운 호출 스택을 계속 만들지 않는 루프가 되는 셈이다.

리스트를 뒤집는 loop

리스트 뒤집기도 같은 방식으로 구현할 수 있다.

def reverse[A](xs: List[A]): List[A] = {
  @tailrec
  def loop(remaining: List[A], result: List[A]): List[A] =
    remaining match {
      case Nil          => result
      case head :: tail => loop(tail, head :: result)
    }

  loop(xs, Nil)
}

두 인자는 반복문의 상태 변수처럼 움직인다.

• remaining: 아직 처리하지 않은 원소
• result: 지금까지 뒤집어 놓은 결과

loop(List(1, 2, 3), Nil)
loop(List(2, 3),    List(1))
loop(List(3),       List(2, 1))
loop(Nil,           List(3, 2, 1))
→ List(3, 2, 1)

head :: result는 리스트 앞에 원소를 붙이므로 O(1)이다. 반면 아래 구현은 재귀 호출이 끝난 다음 :+ head를 실행해야 한다.

case head :: tail => reverse(tail) :+ head

이 호출은 마지막 작업이 아니어서 꼬리 재귀가 아니다. 매번 리스트 끝에 원소를 붙이는 비용까지 들어 전체 시간 복잡도도 O(n²)이 될 수 있다.

@tailrec은 무엇을 할까?

@tailrec은 “이 함수를 최적화하라”는 스위치라기보다 꼬리 재귀 형태인지 컴파일러가 보증하게 하는 검사 장치다.

앞의 loop처럼 함수 정의 바로 위에 @tailrec을 붙인다. 함수를 수정하다 재귀 호출 뒤에 다른 계산이 생기면 컴파일 오류가 발생한다. 조용히 일반 재귀로 바뀌어 스택 안정성을 잃는 일을 막을 수 있으므로, 꼬리 재귀를 의도한 함수에는 붙여두는 편이 좋다.

Scala/JVM에서 이 최적화는 주로 함수가 자기 자신을 직접 호출할 때 적용된다. 두 함수가 서로를 호출하는 상호 재귀까지 JVM이 일반적으로 최적화해 주는 것은 아니다.

기억할 것

• 꼬리 재귀는 재귀 호출이 함수의 마지막 작업인 형태다.
• 컴파일러는 직접적인 꼬리 재귀를 루프처럼 바꿔 호출 스택을 O(1)로 유지할 수 있다.
• 중간 결과는 누산기 인자로 전달한다.
• @tailrec을 붙이면 꼬리 재귀 조건이 깨졌을 때 컴파일 오류로 알 수 있다.
• 재귀 호출 뒤에 연산이 남아 있다면 꼬리 재귀가 아니다.