꼬리재귀 최적화와 트램폴린

꼬리재귀 최적화

꼬리재귀는 재귀의 특별한 한 형태인데, 재귀호출로 받은 결과값을 추가로 계산하거나 처리하지 않고 그대로 리턴하는 형태를 말한다. 예를 들어 1부터 n 까지의 합을 구하는 함수를 재귀로 구현했다고 하면 일반적으로 다음과 같은 꼴을 생각할 수 있다.


func sum1(n: Int) -> Int { if n < 1 { return 0 } return n + sum1(n - 1) }

이를 꼬리 재귀로 만들면 다음과 같다.

func sum2(n: Int, acc: Int = 0) -> Int {
  if n < 1 { return acc }
  return sum2(n-1, acc: acc + n)
}

일반적인 재귀호출의 경우, 루프를 이용해서 구현하는 것에 비해서 부가적인 비용이 들게된다. 재귀 함수가 호출됨에 따라서 스택 프레임을 생성하고 관리하는 비용이 든다. 또한 재귀의 깊이가 깊어지는 경우에 스택 자원이 소진되어 스택 오버플로우가 발생할 수도 있다.

대신 꼬리재귀의 경우, 최종 단계의 결과가 곧 재귀호출 전체의 결과와 일치하게 된다. 따라서 컴파일러는 새로운 스택 프레임을 만들고 재귀 호출을 하지 않고, 현재 스택 프레임에서 해당 함수의 시작지점으로 점프하여 재귀 호출하는 식으로 루프로 구현한 것과 유사한 형태로 최적화 할 수 있다. 이렇게 되면 추가적인 스택을 쓰지 않게 되어 속도도 향상되고 스택 오버플로우에 대한 위험도 사라지는데, 이를 꼬리 재귀 최적화라고 한다.

Swift의 컴파일러도 이러한 꼬리재귀 최적화를 수행하는 것으로 확인되는데, 몇 가지 예외의 경우가 있다. 먼저 클래스 타입의 객체의 메소드를 재귀호출하는 경우에는 호출되는 메소드가 실행시점에 동적으로 변경될 수 있기 때문에 꼬리재귀 최적화가 적용되지 않는다. 두 번째로 꼬리 재귀 모양의 코드를 작성하더라도, 컴파일러의 ARC에 의해서 메모리 관리 코드가 부가되면서 꼬리 재귀 패턴이 적용되지 못하는 경우가 있을 수 있다. 이러한 한계 때문에 Swift의 꼬리 재귀는 최적화에 대한 예외 상황이 존재한다.

트램폴린

재귀 호출이 함수 내에서 자신을 또 호출하고, 호출하고 호출하는 식으로 내려가다가 다시 리턴하고 리턴하는 식으로 올라오는 것을 반복한다면, 트램폴린은 어떤 함수를 호출하고 그 결과를 받아서 다시 그 함수를 호출하는 식으로 일종의 루프를 도는 식으로 똑같은 함수에서 트램폴린을 타듯이 뜀뛰는 것을 의미한다.

Swift에서 재귀 호출의 한계를 극복하기 위해서 트램폴린 형태로 작성하는 예를 들어보자. 먼저 다음과 같이 enum 타입을 하나 정의한다. 이 타입은 .Done 이나 .Call 중 하나가 되는데, .Done은 재귀의 끝에서 리턴하는 타입이고, .Call은 추가적인 재귀 단계가 남았다는 의미이다.

enum Result<T> {
  case Done(T)
  case Call(() -> Result<T>)
}

그리고 함수의 본체는 다음과 같이 시작해보자.

func sum3(n: Int, acc: Int = 0) -> Int {
  func helper(n: Int, acc: Int) -> Result<Int> {
    if n < 1 { return .Done(acc) }
    return .Call({ helper(n-1, acc: n + acc) })
  }
  // ...
}

함수의 내부에 보조함수를 하나 정의하는데, 실질적인 계산을 하는 함수이다. 종료조건에 도달했을 때 .Done 타입의 값을 리턴하고, 그렇지 않는 경우에는 다음번 재귀호출에 해당하는 클로저를 리턴하게 된다. 나머지 코드를 완성해보자.

func sum3(n: Int, acc: Int = 0) -> Int {
  func helper(n: Int, acc: Int) -> Result<Int> {
    if n < 1 { return .Done(acc) }
    return .Call({ helper(n-1, acc: n + acc) })
  }
  /// 트램폴린 본체
  var res = helper(n, acc: acc)
  repeat {
    switch res {
      case let .Done(r): return r
      case let .Call(f): res = f()
    }
  } while true
}

결과값(Result)을 담는 변수를 두고, 이 변수가 최종결과 타입일 때까지 반복해서 헬퍼함수를 재호출하는 방식으로 구성된다. 이 때 return .Call({ helper(n-1, acc: n + acc) })의 모양이 좀 부자연스러우니 다음과 같이 코드를 수정하는 것도 좋다.

func sum3(n: Int, acc: Int = 0) -> Int {
  func call(@autoclosure(escaping) f: () -> Result<Int>) -> Result<Int> {
    return .Call(f)
  }
  func helper(n: Int, acc: Int) -> Result<Int> {
    if n < 1 { return .Done(acc) }
    return call(helper(n-1, acc: n+acc))
  }
  ...
}

여기서 추가한 call 함수는 표현식을 자동으로 클로저로 감싸고, 이를 Result타입으로 변환해준다. 따라서 call(helper(n-1, acc: n + acc))와 같이 조금 더 자연스러운 모양으로 코드를 변경할 수 있다.

일반화

꼬리재귀 형태의 함수는 기본적으로 이전에서 누적된 값을 받아와야 하므로 추가적인 인자를 필요로 하는 경우가 있을 수 있다. 따라서 인자의 수가 결정돼 있다면 꼬리재귀 함수를 트램폴린 구현으로 변환하는 함수를 만들 수 있다.

enum TrResult<A, B> {
  case Done(B)
  case Call(A, B)
}

func trampolinize<A, B> (body: (A, B) -> TrResult<A, B>) -> (A, B) -> B {
  return { n, acc in
    var res = body(n, acc)
    repeat {
      switch res {
        case .Done(r): return r
        case .Call(x, y): res = body(x, y)
      }
    } while true
  }
}

let sum4: (Int, Int) -> Int = trampolinize{ n, acc in
  if n < 1 { return .Done(acc) }
  return .Call(n-1, n+acc)
}

print(sum4(777_7777, 0))
// 30246911419753

위에서 살펴보면 sum4는 꼬리 재귀형태로 작성한 클로저를 트램폴린 형태로 동작하도록 한 함수가 되고, 무려 7백만번의 깊이에 대해서도 (컴파일러의 최적화 플래그 없이) 뻗지 않고 결과값을 내어준다.