Site icon Wireframe

Swift의 꼬리 재귀

Natasha ElementTypehe Robot에 꼬리와 꼬리재귀에 대한 글이 올라오고 Digg에서 많은 digg을 얻었는데, 좀 이상해서 내용을 정리해본다. 링크한 글의 저자는 꼬리재귀와, 함수형 언어의 자료 구조인 리스트의 head, tail을 혼동하고 있는 듯 하다. 우선 꼬리재귀에 대해서 먼저 이야기하겠다. 꼬리 재귀는 재귀의 특별한 한 형태이다. 꼬리 재귀를 설명하기 전에 먼저 재귀(recursion)에 대해 알아보자.

재귀는 어떤 함수의 내부에서 스스로를 다시 호출하는 것을 말한다. 예를 들어서 1에서 10 까지의 자연수의 합을 구하는 과정을 재귀적인 처리를 통해서 구한다고 생각해보자.

  1. 계산은 1 + 2 + 3 + 4 + … + 10 으로 이루어지고, 편의상 이걸 +(1~10) 이라고 표현하기로 약속한다.
  2. 이 때 10까지의 합과 9까지의 합은 10만큼 차이난다, 즉 +(1~10)+(1~9) + 10 인 셈이다.
  3. +(1~n)+(1~(n-1)) + n 이 된다.

이렇게 풀어써서 복잡한데, 조금 더 이해하기 쉬운 표현으로 고쳐보면 다음과 같이 쓸 수 있다.

  1. 1…10 의 합은 1…9 의 합에 10을 더한 것이다.
  2. 1…1의 합은 1이다.

이 두 가지 원리를 이용하면 N까지의 합을 구하는 것은 (N – 1)까지의 합을 구한 다음, N을 더하기만 하면 된다는 것으로 정리할 수 있다. 즉 1~N의 합을 구하는 계산에서 1~(N-1)의 합을 구한 결과가 필요하고, 이는 자기 자신의 계산 결과를 내부에서 활용한다는 것으로 이해할 수 있다. 이를 코드로 옮겨 보면 다음과 같다.

func sumUpto(n: Int) -> Int {
    if n == 1 { return 1 }
    return supUpto(n:n - 1) + n
}

이와 같은 방식으로 작성되는 재귀 함수는 대체로 코드가 매우 간결해 보인다는 장점이 있다. 논리적으로 모든 재귀 호출은 반복 구문으로 변환이 가능하고, 반대로 모든 반복 구문은 재귀 호출의 형태로도 변환이 가능하다. 그런데 재귀 함수의 꼴은 수열의 점화식처럼 점진적으로 진행하는 관계식이 명확한 경우, 이를 그대로 코드로 바꾼 형태이기 때문에 이해하기 쉬워진다는 장점이 있다. (물론 이것은 사람에 따라, 케이스에 따라 다를 수 있다.) 다만 일반적인 프로그래밍 언어에서는 함수 호출에는 스택 프레임을 생성하는 비용이 들고, 따라서 호출 깊이에 제약이 발생한다. 즉 재귀 함수로 작성된 코드는 반복횟수에 제한이 있을 수 밖에 없다.

또한 함수 호출을 위한 스택 프레임을 생성하는데 드는 비용도 무시할 수 없다. 따라서 왠만하면 재귀 호출은 반복문으로 바꾸는 것이 성능적인 측면에서 이롭다고 할 수 있다. 그러나 이러한 패턴에 매우 숙련된 사람이 아니라면 재귀로 먼저 작성한 코드를 반복문으로 바꾸는 것에 어려움을 겪을 수 있다. 그런데 재귀함수의 어떤 형태는 반복문으로 변경하기에 아주 유리한 것들이 있는데, 그러한 유형에서 대표적인 것이 꼬리 재귀이다.

꼬리재귀 최적화

꼬리 재귀는 재귀 호출의 특별한 형태이다. 여기서 꼬리는 함수의 끝자락을 의미하며 return 구문을 말한다. 즉 꼬리 재귀는 return 구문에서 재귀 호출이 일어나는 것을 말하며, 좀 더 정확히는 재귀 호출한 결과를 그대로 리턴하는 것을 의미한다.

재귀 호출의 결과를 그대로 리턴하는 것에 주목하자. 이는 재귀 호출을 시작한 시점부터는 현재의 호출 스택에 있는 다른 어떤 정보도 필요하지 않다는 것이다. 그리고, 재귀 호출로 인해 생성될 스택 프레임은 현재 스택 프레임과 완전히 동일하다. 이 말은 현재 스택 프레임을 그대로 재활용할 수 있다는 것이다. 따라서 꼬리 재귀가 발생하면 현재 함수의 첫 부분으로 돌아가는 것으로 함수 호출을 대체할 수 있고, 추가적인 오버헤드가 필요치 않게 된다. 이러한 동작이 반복될 것임을 감안하면 성능이나 자원사용 측면에서 상당한 이점을 가질 수 있는데, 더군다나 방법도 간단하고 이러한 상황을 판정하는 패턴도 단순하다. 따라서 사람이 직접 꼬리 재귀를 반복문으로 변경하지 않고 컴파일러가 알아서 재귀 호출 형태를 반복문으로 바꿔줄 수 있는 것이다. 이렇게 기계에 의해 꼬리 재귀를 반복문으로 강제로 전환하는 것을 꼬리재귀 최적화라고 한다.

앞서 예로 들었던 sumUpto(n:) 은 꼬리 재귀의 형태가 아니다. 일반적인 재귀를 꼬리 재귀로 변환하기 위한 전략으로는 지금까지의 계산 결과를 인자로 전달하도록 함수의 디자인을 변경하는 것이 있다. 따라서 대부분의 꼬리 재귀 함수는 다음과 같은 인자 구성을 가진다.

  1. 계산을 종료할 것인지를 알려주는 기저 조건을 인자로 받는다.
  2. 직전까지의 누적 계산 결과를 인자로 받는다.
  3. 대부분 기저 조건에서는 누적 계산 결과를 그대로 리턴한다.

이 원칙을 고려해서 sumUpto(n:)을 꼬리 재귀로 변경해보자.

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

하스켈과 같은 언어는 반복문에 해당하는 문법이 존재하지 않는 대신에 재귀를 사용하여 반복 연산을 수행한다. (모든 반복문과 재귀호출형태는 변환 가능하다고 했다. 이는 이미 수학적으로도 증명된 사실이다.) 그리고 이러한 언어로 쓰여진 코드를 살펴보면 대부분이 이처럼 꼬리 재귀의 형태를 가지고 있는 경우가 많다.

Swift의 꼬리재귀 최적화에 관해

Swift 컴파일러는 꼬리 재귀 최적화를 수행하는 것으로 알려져 있지만, 실제로는 적용되지 않는 경우도 많이 있다. 이는 ARC라고 불리는 컴파일러에 의해 수행되는 메모리 관리 시스템 때문이다. ARC는 객체의 생성과 릴리즈 시점을 고려해서 자동으로 메모리 해제 코드를 삽입한다. 이 과정에서 프로그래머가 꼬리 재귀 호출의 형태로 코드를 작성했더라도, 메모리 관리 코드가 삽입되면서 꼬리 재귀가 아닌 코드가 될 수 있기 때문이다.

대신에 꼬리 재귀의 형태는 역시 아주 간단한 방법으로 트램폴린 기법으로 변형이 가능하다. 트램폴린은 꼬리 재귀 함수를 확장한 형태로, 꼬리 재귀 호출의 결과를 리턴하는 대신에, 재귀 호출을 수행하는 코드를 함수의 형태로 리턴하는 것이다. 따라서 반복문을 통해 함수의 리턴 형식이 호출 가능한 함수이면 다시 한 번 호출하는 식으로 변환하는 것이다.

enum TrampolineResult<T> {
  case done(T)
  case call(() -> TrampolineResult<T>)
}

func helper(n: Int, acc: Int) -> TrampolineResult<Int> {
    if n == 0 { return .done(acc) }
    return .call({ helper(n:n - 1, acc:acc + n) })
}

func sumUptoTram(n: Int) -> Int {
    var res = helper(n:n, acc:0)
    while true {
        switch res {
            case let .done(x): return x
            case let .call(f): res = f()
        }
    }
}

심지어 이 코드는 단순 반복문에 대한 최적화가 들어가기 때문인지 꼬리 재귀 형태로 작성한 것보다 수십 배 빠르게 작동한다. ARC때문에 꼬리재귀 최적화가 작동하지 않는 것인지, 아니면 단순 반복문일 때의 실행 코드 예측에 따른 최적화가 강력한 것인지는 모르겠지만, 이 정도의 실행 시간 차이는 좀 의외이다.

위 코드에서는 도우미 함수가 자기 자신을 호출하는 클로저를 리턴하는데, 클로러를 생성하는데 소요되는 오버헤드가 존재한다. 더 빠른 성능을 위해서는 클로저를 직접 생성하기 보다는, 함수 호출에 필요한 파라미터만 리턴하는 식으로 코드를 개선하여 더욱 빠르게 작동할 수 있게 한다.

enum TrampolineResult2<A, B> {
    case done(B)
    case call(A, B)
}

func helper(n: Int, acc: Int) -> TrampoilneResult<Int, Int>
{
    if n == 0 { return .done(acc) }
    return .call(n - 1, acc + 1)
}

func sumUptoTram2(n: Int) -> Int {
    var res = helper(n:n, acc:0)
    while true {
        switch res {
            case .done(x): return x
            case .call(n, acc): res = helper(n:n, acc:acc)
        }
    }
}
    Exit mobile version