Site icon Wireframe

꼬리재귀와 트램폴린

꼬리 재귀(tail recursion)는 함수가 내부에서 자신을 재귀 호출할 때, 재귀 호출한 결과를 그대로 리턴하는 모양을 만드는 것이다. 이는 return 구문의 모양에 의해서 쉽게 판별할 수 있고, 재귀 호출의 결과 값에 대해서 추가적인 처리를 하지 않기 때문에 컴파일러가 쉽게 최적화할 후 있다. 재귀 호출의 결과를 그대로 사용한다는 것은, 재귀 호출을 수행하는 시점에 함수 내부의 지역 변수를 더 이상 사용하지 않는 것을 의미하므로 함수 호출에 의한 새로운 스택 프레임을 생성하는 대신, 현재 스택 프레임을 재활용할 수 있다. 따라서 꼬리 재귀는 반복 연산의 모양으로 변환이 가능하며, 이 과정은 기계적으로 처리될 수 있다.

꼬리 재귀는 컴파일러가 꼬리재귀 최적화를 지원하지 않는다면, 재귀 깊이에 한계가 있다는 단점이 있다. 따라서 재귀 호출 자체를 직접적인 반복문으로 변경할 수 있도록 재귀 호출을 수행할 함수를 리턴하는 것으로 스택 오버플로우를 회피할 수 있다.

예제 – 피보나치 수열의 일반항

재귀 최적화에 단골로 등장하는 문제인 피보나치 수열의 일반항을 구하는 문제를 예로 들어보자. 피보나치 수열은 1, 1, 2, 3, 5, 8, …. 로 이어지는 수열로 앞의 두 항의 합이 연속되는 수열이다. 따라서 n 항은, n이 2보다 작으면 1을, 2 이상이면 앞의 두 항을 더하여 리턴한다. 성능을 고려하지 않고 재귀의 형태로 작성한 코드는 아래와 같으며, 이 코드는 n이 조금만 커져도 매우 느려진다.

def fibonacci(n: int) -> int:
  if n < 2:
    return 1
  return fibonacci(n - 1) + fibonacci(n - 2)

꼬리 재귀

피보나치 수열을 꼬리 재귀로 작성해보자. 입력이 n으로 주어졌을 때, 재귀호출은 n회만큼 일어나며 각각의 호출은 필요한 정보를 모두 인자로 넘겨주어야 한다. 따라서 남은 호출 횟수 및 직전 두 항의 값을 전달한다.

def fib_tail(n:int, a:int=1, b:int=1) -> int:
  if n == 0:
    return a
  return fib_tail(n - 1, b, a + b):

파이썬이 꼬리재귀 최적화를 지원하지 않는 것과는 별개로, 위 코드는 불필요한 계산을 반복하지 않기 때문에 훨씬 빠르게 작동한다. 하지만 꼬리 재귀 깊이에 한계가 있다. 시스템마다 다를 수 있겠지만, 기본적인 파이썬의 최대 허용 재귀 깊이는 3000회 정도이다.

# 현재 재귀 깊이 구하기
import sys
print(sys.getrecursionlimit())
# 3000

# sys.setrecursionlimit() 을 사용하면 재귀 깊이를 변경할 수 있긴 하다.

트램폴린

트램폴린 기법은 꼬리 재귀를 약간 변형한 것으로, 재귀 호출의 결과를 리턴하는 대신, 재귀 호출을 수행하는 함수나 클로저를 만들고 이를 리턴하는 것이다. 다음과 같은 형식을 사용할 수 있다.

def _trampoline_helper(n: int, a: int=0, b: int=1):
  if n < 2:
    return b
  return lambda: _trampoline(n - 1, b, a + b)

def fib_tram(n):
  fn = _trampoline_helper(n, 0, 1)
  while callable(fn):
    fn = fn()
  return fn

트램폴린은 보통 별도의 헬퍼 함수를 만들어서 사용하는데, 이 함수는 기저 케이스에 도달하면 결과 값을 리턴하지만, 그렇지 않은 경우에는 자신을 호출하는 함수를 생성하여 리턴한다. 실제 사용할 함수는 헬퍼 함수의 결과가 호출가능한 함수이면 반복하여 호출하고, 그렇지 않으면 최종 결과가 나온 것으로 확인하여 리턴한다.

이 방식은 꼬리 재귀 형태를 다시 변형하여 실질적으로는 반복문에 의해서 실행되기 때문에, 재귀 호출 깊이 제한에 의한 제약을 받지 않는다는 장점이 있다.대신에 함수 객체를 매번 생성하는 오버헤드가 있기 때문에 꼬리 재귀보다는 조금 느린 경향을 보인다.

개선된 트램폴린

트램폴린 도우미 함수는 실질적은 연산을 담당하면서, 최종 결과값이나, 다시 자기자신을 호출하는 함수를 리턴한다. 이 때 자기 자신을 호출하는 함수는, 자기 자신을 호출할 때 필요한 인자값 전체에 대한 정보와 같다고 할 수 있다. 따라서 트램폴린 도우미 함수가 리턴하는 값은 다음의 정보를 가지고 있다고 해석할 수 있다.

따라서 함수가 아닌 다시 호출할 때 필요한 인자 정보를 리턴하도록 개선해보자. 그리고 완료 여부를 함께 리턴해주면 되겠다.

def _trampoline_helper_2(n: int, a: int=0, b: int=1):
  if n < 2:
    return (False, b)
  return (True, (n - 1, b, a + b))

def fib_tram2(n):
  flag, res = _trampoline_helper_2(n, 0, 1):
  while flag:
    res = _rampoline_helper_2(*res)
  return res

부록 : Swift 구현

위 코드를 Swift 에서 구현한 방식을 소개한다. 참고로 Swift에서 꼬리 재귀 최적화가 제대로 이루어지지 않는 것인지, 트램폴린으로 구현한 것이 훨씬 더 빠르게 작동한다.


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

func helper(n: Int, a: Int, b: Int) -> TrampolineHelper<Int> 
{
    if n < 2 { return .done(b) }
    return { helper(n:n-1, a:b, b:a + b) }
}

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