Tail Recursion

꼬리재귀

Natasha ElementTypehe Robot에 꼬리재귀에 대한 글이 올라오고 Digg에서 많은 digg을 얻었는데, 좀 이상해서 내용을 정리해본다.

재귀와 꼬리재귀

순수 함수형 언어에서는 변수의 개념이 없고 재귀를 통해서 이를 구현하게 되는데, 함수형 언어가 아닌 일반적인 프로그래밍 언어에서는 호출스택1을 통해서 함수 흐름제어를 하고 있고, 이 호출 스택의 크기가 제한되어 있기 때문에 재귀의 깊이가 깊어지면 스택 오버플로우가 발생하게 된다.

재귀 알고리듬은 디버깅이 좀 어려워지는 단점은 있지만 보통은 코드가 간결해지고, 특정 문제의 경우에는 루프보다도 재귀적인 사고방식을 통하는 것이 문제를 쉽게 풀 수 있게도 한다. 예를 들어 트리 구조 데이터의 탐색이나 유클리드의 호제법 구현은 루프보다는 재귀적인 접근법이 매우 효율적이다.

하지만 재귀는 함수호출을 많이 쓰게 되고 따라서 시스템은 스택프레임을 그만큼 많이 써야하는 문제가 있다. 이는 성능 저하의 이슈나 스택 오버플로우의 위험을 안고 있기 때문에 재귀적인 접근으로 시작하되 구현은 루프를 권장하는 경우가 많다. 꼬리 재귀는 이 둘의 장점을 동시에 취하는 것이다.

꼬리재귀는 루틴의 끝에서 재귀가 일어난다는 말이다. 즉, 재귀로 얻은 값을 그대로 리턴하고, 재귀 결과에 대한 별도 처리를 하지 않는 것이다. 이 경우에는 서브루틴 호출이 아닌 점프로 치환이 가능하기 때문에 쉽게 루프 구조로 변환이 가능하다. 꼬리 재귀 최적화를 지원하는 (GCC의 경우 -O2부터) 컴파일러들은 꼬리재귀형태의 코드를 쓰면 알아서 루프로 바꿔준다. (일반 재귀를 루프로 바꾸는 것은 수학적으로는 가능하다고 증명되어 있으나 방법이 어렵다.) 단, 일반적인 재귀는 꼬리재귀의 형태로 바꾸는 것이 많이 어렵지 않다.

head, tail과 재귀

일반적으로 루프를 돌기 위해서는 종료 조건을 기억하고 있는 변수가 있어야 한다. 예를 들어 1~10의 합을 구하는 다음 루프를 보자.

int i, sum=0;
for(i=0;i<10;i++){
    sum += (i+1)
}

이는 동일한 처리를 10회 반복하기 위해서 for 문을 사용하는데, 루프가 끝나는 조건을 검사하기 위해서는 루프의 매 시행마다 값이 변하는 변수를 유지해야 하는 부담이 있다. 만약 재귀를 쓴다면 이러한 플래그를 쓸 필요가 없을 거다. 아래는 이를 재귀함수로 변경한 것이다.

int getSumUpElementTypeo(int i) {
    if (i==1) {
        return 1;
    } return i + getSumUpElementTypeo(i - 1)
}

이 함수는 아쉽게도 꼬리 재귀가 아니다. return 문에서 재귀하긴하지만 재귀 결과에 다시 i를 더하기 때문이다. 이를 꼬리 재귀로 바꾸려면 다음과 같이 한다.

int _getSumUpto(int i, int sum) {
    if (i == 1) {
        return sum + 1;
    } return _getSumUpto(i-1, sum+i);
}

int getSumUpElementTypeo(int i){
    return _getSumUpto(i, 0);
}

만약 하스켈에서 재귀를 통해서 합을 구하는 함수를 쓴다면 다음과 같이 쓸 수 있을 거다.

getSumUpto :: Num -> Num
getSumUpto 1 = 1
getSumUpto x = x + getSumUpto (x - 1)

이쯤에서 중간 정리를 하자면, 꼬리 재귀는 재귀의 한 형태이며, 이는 호출스택을 재사용하거나 점프를 통해서 실질적으로는 루프를 도는 형태로 쉽게 최적화가 가능한 모양의 재귀를 일컬을 뿐이며, 함수형 언어에서의 재귀와는 상관없다. 다만 함수형 언어에서는 리스트의 맨 첫원소를 head, 그 나머지를 tail 이라고 부를 뿐이고, 이는 함수형 언어가 재귀를 전혀 다른 컨셉으로 이해한다고 봐야 한다.

함수형 언어에서 재귀

앞서 함수형 언어에서는 반복문2이 없기에 반복문을 재귀로 표현한다고 했는데, 본질적으로 함수형 언어의 코드는 프로그램 소스인 동시에 수학적 함수 정의와 거의 동일하기 때문에 재귀는 일종의 점화식으로 봐야 한다.

이를 극명하게 드러내는 부분이 피보나치 수열 정의이다.

fib :: Num a => a -> a -> [a]
fib x y = x:(fib y (x+y))

main = print $ take 10 $ fib 0 1

즉 재귀는 연속열형태의 자료형(리스트)에서 앞원소와 그 다음원소 사이의 관계를 정의하는 것으로 보는 것이 더 보편적이라 하겠다. 함수형 언어의 맵, 리듀스도 그러한 맥락으로 봐야 한다. 리스트 맵핑은 하스켈에서 다음과 같이 표현한다.

mymap :: (a -> b) -> [a] -> [b]
mymap f [] = []
mymap f (x:xs) = (f x):(mymap f xs)

이를 파이썬에서 재귀적으로 표현하면 다음과 같다.

def mymap(func, iterable):
    return [func(iterable[0])] + mymap(func, iterable[1:])

하지만 이는 각 재귀 깊이마다 새로운 리스트 사본을 생성하게 되므로 효율이 떨어진다. 맵, 필터는 파이썬에서는 리스트 축약이라는 표현을 즐겨 사용하게 된다. (그리고 이는 파이썬 함수나 루프보다도 더 빠르다.) 이것은 내부적으로 함수형 언어의 맵핑과 유사하게 동작한다.

doubled = [x*2 for x in iterable]

맵리듀스

하지만 함수형 언어들이 전적으로 재귀에 의존하는 것은 아니다. 왜냐하면 반복(iteration)이 필요한 경우는 주로 일련의 값 시퀀스의 각 원소들을 차례로 처리하기 위한 순회의 개념이기 때문에 리스트를 앞에서부터나 뒤에서부터 축약해 나가는 리듀스 및 각 원소를 다른 리스트로 맵핑하거나 필터링할 수 있다. 이러한 맵리듀스는 명확한 표현(짧고도 이해하기 쉽다)는 장점때문에 파이썬을 비롯한 많은 현대 언어에 영향을 주었다. 대부분 ‘함수형 언어의 특성을 도입했다’는 것은 이 맵리듀스 기능을 들여오는 것을 의미한다. (최근엔 C++에도 이런 기능이 들어갔다고…)

  • 반복을 리스트 순회의 개념으로 바꾼 fast enumeration (for … in …)
  • 리스트를 다른 리스트로 사상하는 함수나 표현(map)
  • 리스트를 필터링하는 함수나 표현
  • 리스트를 리듀스하는 함수나 표현

Swift역시 파이썬과 하스켈로부터 큰 영향을 받아 이런 특성을 잘 반영한다. (축약 노테이션만 추가되면 좋겠다.)

리듀스

리스트의 합계를 구하거나, 최대 값을 찾는 것은 이 리듀스를 사용한다. 하스켈의 활용법을 보자.

sum' [] i = i
sum' (x:xs) i = sum'(xs x+i)

--print $ sum [1..10] 0
--> 55

max' [] = 0
max' (x:xs) | x > max'(xs) = x
            | otherwise = max'(xs)

파이썬에서는 reduce 함수가 내장함수로 만들어져 있다. (map, filter 함수도 있지만 리스트 축약을 권장한다.)

sum_ = reduce(lambda x, y: x + y , range(1, 11), 0)
max_ = reduce(lambda x, y: max(x, y), range(1, 11), 1)

Swift의 Array 타입도 .reduce 함수를 지원한다.

func reduce<ElementType>(initial:ElementType, func:(ElementType, ElementType)->ElementType)) -> ElementType

대충 이런식으로 타입정의가 돼 있을 거고

let sum_ = Array(1...10).reduce(0, +) // +도 함수로 취급함. 
let max_ = Array(1...10).reduce(1){max($0, $1)}

결론

함수형 패러다임의 개념이 널리 퍼지기 이전에 재귀는 ‘기묘한 코드를 만드는 위험한 수법’과 같이 생각되던 때가 있었다. 그래서 많은 경우 재귀는 꼬리재귀나 루프의 형태로 벼경하여 작성하였고 지금도 그렇게 하고 있다. 함수형 언어에서의 재귀는 이러한 재귀호출의 개념보다는 연속열 내 두 원소간의 관계에 집중한 일종의 점화식 표현이며, 이는 맵리듀스라는 함수형 언어 고유의 무기로 발전했고, 다시 다른 패러다임의 언어에서 이 방식을 많이 도입하고 있다.

끗.

Swift 컴파일러는 꼬리재귀 최적화를 지원한다. 하지만 꼬리재귀 최적화가 일어나기 이전에 ARC를 통한 코드변환 작업이 먼저 발생하기 때문에 return do(x-1) 대신에 return autorelease(do(x-1)) 이런식으로 변경이 일어나며, 이는 꼬리재귀의 모양이 아니게 된다. 따라서 이 문제를 해결하기 위해서는 트램폴린이라는 다른 기법을 쓰는 것이 추천된다.


  1. 대부분의 프로그래밍 언어에서 함수를 호출하면 호출시의 인자값 및 함수 내부에서 쓰이는 지역 변수를 할당하고 초기화하는 것은 가용 메모리의 끝 부분의 스택 영역에서 이루어진다. 스택을 이용할 때의 장점은 함수가 리턴할 때 스택에서 추가로 할당한 컨텍스트를 pop 해서 파괴해버리면 자동으로 스택의 최상위 컨텍스트가 해당 함수를 호출했던 지점으로 복귀한다는 것이다. 물론 이러한 스택 구조는 그 크기를 한정해야 하므로 많은 언어에서 재귀 호출의 깊이가 제한된다. (대신 스택을 힙 영역 내에 생성하고 직접 관리하는 일부 언어들 (stackless python 등)의 경우에는 이런 제한이 없지만, 컨텍스트 관리를 위해서 스택을 쓴다는 점은 공통적이다. 
  2. 일반적인 프로그래밍 언어에서 반복문은 반복문을 탈출하기 위한 조건이 있고, 그 조건을 저장하는 상태변수가 있어야 한다. (전통적인 C의 for 문을 생각해보라) 그런데 함수형 언어에서는 이런 변수를 사용할 수가 없으니 리스트와 같은 자료 구조를 이용해서 재귀를 통해 반복하는 패턴을 이용한다. 
  • 사소한 문제지만 “head, tail과 재귀” 항목의 C코드가 잘못됐네요. return 1 이 아니라 return sum + 1 이겠습니다. 평소에 소중히 잘보고 있습니다. 🙂

    • 아, 틀린 부분이 있었군요. 지적 감사합니다. 평소에도 자주 들러주신다니 더 감사드리구요 🙂