8.8 꼬리 재귀 제거(Tail Recursion Elimination, TRE)

Haxe 4.1.0 이후

재귀는 피보나치 수 계산이나 트리 순회 같은 일부 작업을 푸는 자연스러운 방법이에요. 쓰기, 읽기, 이해하기 쉽습니다. 하지만 재귀 대신 루프로 같은 작업을 푸는 것보다 런타임에 더 많은 계산 자원을 사용합니다.

예를 들어 노드 트리의 루트를 찾는 루프 기반 함수:

static function getRoot(node:Node):Node {
    var root = node;
    while(root.parent != null) {
      root = root.parent;
    }
    return root;
  }

그 재귀 대응물은 더 깔끔해 보일 수 있지만, 추가 함수 호출 때문에 성능이 더 나쁠 수 있어요:

static function getRoot(node:Node):Node {
    if(node.parent == null) {
      return node;
    }
    return getRoot(node.parent);
  }

Haxe 컴파일러는 4.1.0부터 재귀 호출로 끝나는 함수에 대해 자동 재귀-루프 변환을 수행할 수 있습니다. 이 최적화는 정적 분석기로 (컴파일 인자에 -D analyzer-optimize를 추가해) 자동 활성화됩니다. TRE가 활성화된 상태에서 앞서 언급한 재귀 getRoot 함수가 컴파일된 구문 트리에서 이렇게 보입니다:

static function getRoot(node:Node) {
  while (true) {
    if (node.parent == null) return node;
    node = node.parent;
  }
}

재귀 호출은 컴파일 시 자동으로 루프로 대체됩니다.

TRE 최적화 자격이 되려면 함수는 여러 요구사항을 충족해야 해요:

함수의 마지막 연산이 재귀 호출이다. 그 호출이 if나 else 표현식 안에 있어도 마찬가지다.
함수가 dynamic 접근자를 가지지 않는다.
static 메서드이거나 final 메서드(final method)이거나 지역 명명 함수(local named function)이다.

출처: Tail Recursion Elimination (TRE)

본문

TRE

컴파일러는 재귀 호출로 끝나는 함수를 while (true) 루프로 변환해 함수 호출 오버헤드를 없앱니다. -D analyzer-optimize로 활성화된 정적 분석기에 포함됩니다.

자격 요건

마지막 연산이 재귀 호출이고, dynamic 접근자가 없으며, static/final/지역 명명 함수여야 합니다.

더 알아보기

Loop unrolling