그림 1. 재귀 버전
요약: 어떤 종류의 문제들은 재귀 프로시저로 아주 효과적으로 기술이 가능하다. 그러나 재귀 프로시저에 대하여 엄격하게 통제할 필요가 있을 경우가 있다. 엄청난 양의 데이터를 양산하며, 코딩하기에도 어렵기 때문이다. 파이썬 발생자는 파이썬 2.2 이상에서 도입되었는데, 이런 프로시저들을 쉽게 통제하면서 간결하게 프로그램을 유지할 수 있다.
이 문서에서 언급된 소스 코드는 여기에 있다. 일반 텍스트 버전은 여기에 있다.
아무도 재귀의 힘을 의심하는 사람은 없다. 비록 가끔 약간 복잡해 보이지만, 보통은 문제를 기술하는 아주 바른 방법이다. 프로시저가 처리하는 데이터의 크기가 지수적으로 증가할 경우 특히 그렇다. 트리를 순화는 것은 좋은 예이다. 트리에서 각 노드는 하나 이상의 노드들이 있기 때문에, 프로시저가 트리 아래로 내려갈 수록, 노드의 수는 지수승씩 늘어난다. 그러나 모든 노드가 동질적이라면, 같은 프로시저는 노드마다 계속해서 적용할 수 있다.
트리 순회는 재귀의 사소한 예이다. 왜냐하면 거의 모든 컴퓨터 공학 교과서에서 이것을 설명하기 때문에 아마도 누구나 깊은 생각없이 트리 순회에 대해서 즐겁게 재귀를 선택할 것이다. 그렇지만, 물론 재귀가 제대로 잘 작동하려면 많은 작업이 필요하다. 그래서 또다른 예를 보기로 하자.
다음 함수 f를 생각해 보자. 이 함수는 벡터 집합을 취해 (V1, V2, V3, ... , Vn) Vi의 각 요소의 가능한 모든 조합의 집합을 돌려준다. 각 조합은 n-요소 벡터로 구성된다 (xi1, xi2, ... , xim) 여기에서 xij는 Vi의 요소이다. 이 함수가 돌려주는 벡터의 총 개수는 |V1| x |V2| x |V3| x ... x |Vn|이다.
이 함수를 파이썬으로 구현해 보자. 간단하게 하기 위하여, String 객체를 사용하여 각 벡터 Vi를 표현한다. 함수는 벡터 집합을 리스트로 돌려준다. 예상된 결과는 다음과 같다:
f([]) --> [''] # 1
f(['abc']) --> ['a', 'b', 'c'] # 3
f(['abc', 'xyz']) --> ['ax', 'ay', 'az', 'bx', 'by', 'bz', 'cx', 'cy', 'cz'] # 9
f(['abc', 'xyz', '123']) --> ['ax1', 'ax2', 'ax3', 'ay1', 'ay2', 'ay3', 'az1', 'az2', 'az3',
'bx1', 'bx2', 'bx3', 'by1', 'by2', 'by3', 'bz1', 'bz2', 'bz3',
'cx1', 'cx2', 'cx3', 'cy1', 'cy2', 'cy3', 'cz1', 'cz2', 'cz3'] # 27
언듯 보면, 구현하기 쉬워 보인다. 재귀를 사용하지 않아도 이 함수를 쉽게 작성할 수 있다고 생각하실지도 모르겠다. 시도해보자.
먼저, 재귀를 전혀 쓰고 싶지 않다면, 프로그램은 아마도 다음과 같이 될 것이다:
def f0(args): counter = [ 0 for i in args ] r = [] while 1: r.append("".join([ arg1[i] for arg1,i in zip(args, counter) ])) carry = 1 x = range(len(args)) x.reverse() # x == [len(args)-1, len(args)-2, ..., 1, 0] for i in x: counter[i] += 1 if counter[i] < len(args[i]): carry = 0 break # leave "for" counter[i] = 0 else: break # leave "while" return r
재귀를 사용하지 않는다면, 중간 상태를 기억해야만 가능한 모든 답을 산출할 수 있다. 이 프로그램에서, 나는 전-가산기 같은 것을 흉내내려고 했다. 먼저 프로그램은 정수 리스트를 준비한다. 다음 반복적으로 가장 낮은 자리수에 1을 추가하려고 시도한다. 반복마다, 인자의 각 요소들을 결합해서 변수 r에 보관한다. 그러나 이 프로그램의 행위는 "carry" 같은 변수들은 힌트를 주는 듯 보이지만, 전체적으로 이해하기가 어렵다.
이제 재귀 버전이다. 함수 f는 다음과 같이 재귀적으로 정의가 가능하다:
| f(Vi, Vi+1, ... , Vn) = | ({xi1} + f(Vi+1, ... , Vn)) + |
| ({xi2} + f(Vi+1, ... , Vn)) + | |
| ... | |
| ({xim} + f(Vi+1, ... , Vn)) . |
이 정의로 자기 자신을 호출하면 프로그램을 더욱 더 쉽게 만들 수 있다:
def fr(args): if not args: return [""] r = [] for i in args[0]: for tmp in fr(args[1:]): r.append(i + tmp) return r
위의 구현은 아주 이해하기 쉽다. 재귀의 힘은 프로그램을 여러 하부문제로 나누어서 각 하부문제에 정확하게 똑 같은 작동방식을 적용할 수 있다는 것이다. 이 프로그램은 각 인자에서 첫 요소를 취해 하나 더 적은수의 인자를 가진 이 함수의 해답에다 그것을 결합할 뿐이다(그림 1).
지금까지 한 번에 결과를 모두 돌려주는 함수들을 보아왔다. 그러나 탐색 또는 열거와 같이 어떤 어플리케이션에서는 아마도 모든 조합을 기억하고 싶지는 않을 것이다. 단지 한 번에 한 조합을 조사하고, 그리고 사용한 다음에는 버리고 싶을 것이다.
출력의 개수가 적으면, 이것은 큰 문제가 안된다. 그러나 재귀 프로시저에서 기대하는 것은 그의 결과가 지수적으로 증가하는 함수에 대하여 신속한 해결책을 제공하는 것이다. 그렇지만, 묘하게도 그런 함수들은 엄청난 양의 데이터를 양산하는 경향이 있어서 프로그램에 문제를 야기한다. 많은 언어 구현에서, 모든 결과를 기억할 수는 없다. 조만간 메모리 용량의 최대 한계에 이를 것이기 때문이다:
$ ulimit -v 5000 $ python ... >>> for x in fr(["abcdefghij","abcdefghij","abcdefghij","abcdefghij","abcdefghij"]): ... print x ... Traceback (most recent call last): File "<stdin>", line 1, in ? File "<stdin>", line 7, in fr MemoryError
이에 대한 전형적인 해결책은 각 조합을 서로다른 상태로 분리하는 것이다. 파이썬에서는 전형적으로 반복자를 구축한다.
파이썬에서 __iter__ 메쏘드가 있는 클래스는 반복자로 사용이 가능하다. 반복자가 기능적으로 리스트와 똑 같지는 않지만, 어떤 서술문 또는 함수에서는 리스트 대신 취해도 된다 (for, map, filter, 등등).
class fi: def __init__(self, args): self.args = args self.counter = [ 0 for i in args ] self.carry = 0 return def __iter__(self): return self def next(self): if self.carry: raise StopIteration r = "".join([ arg1[i] for arg1,i in zip(self.args, self.counter) ]) self.carry = 1 x = range(len(self.args)) x.reverse() # x == [len(args)-1, len(args)-2, ..., 1, 0] for i in x: self.counter[i] += 1 if self.counter[i] < len(self.args[i]): self.carry = 0 break self.counter[i] = 0 return r # display def display(x): for i in x: print i, print return
이 문제에서, 클래스 fi의 구성자를 다음 형태로 재귀 버전 fr과 똑 같이 사용할 수 있다:
>>> display(fi(["abc","def"]))
이 실체가 for 서술문에 건네지면, __iter__ 메쏘드가 호출되고 반환된 객체 (이 경우에는 그 객체 자체)가 회돌이의 반복자로 사용된다. 각 반복마다, next 메쏘드가 인자 없이 호출된다. 반환 값은 회돌이 변수에 저장된다.
그렇지만, 이 프로그램은 이해하기가 쉽지 않다. 알고리즘적으로, 앞서 설명한 비-재귀 버전과 비슷하다. next 메쏘드가 호출될 때마다, counter 변수에 저장된 현재 상태가 갱신되고, 현재 상태에 따라 결과 하나를 돌려준다. 그러나 더 복잡해 보이는데, 그 이유는 메쏘드가 회돌이 사이에서 호출되도록 디자인 되어있기 때문이다. 이는 여기에서 명시적으로 보이지 않는다. next 프로시저의 꼭대기에서 carry 변수를 점검하는 것을 보면 혼란스러울 수 있다. 이것을 이해하려면 이 메쏘드의 바깥에 (보이지 않는) 회돌이가 있다고 상상해야 한다.
이것은 반복자 버전보다 단순할 뿐만 아니라, 원래 재귀 버전보다 훨씬 더 단순하다는 것에 주목하자. 발생자로는 그냥 결과를 한 번에 하나씩 던져주고(또는 "양보(yield)") 그 다음은 잊어 버리면 된다. 마치 스트림 장치에서 결과를 인쇄하는 것과 비슷하다. 상태를 보관하는데 실제로 신경쓸 필요가 없다. 단지 모든 결과를 무식하게 생산만 하면 된다. 그러고도 여전히 그 프로시저를 엄격하게 통제할 수 있다. 비슷한 함수가def fg(args): if not args: yield "" return for i in args[0]: for tmp in fg(args[1:]): yield i + tmp return
게으른 평가(lazy evaluation)로 실현될 수 있다는 것을 눈치채셨을 것이다. 이것은 어떤 기능적 언어에서 지원된다. 게으른 평가와 발생자가 정확하게 똑 같은 개념은 아니지만, 둘 모두 서로 다른 종류의 헝태로 같은 상황을 처리하는데 도움을 준다.
기능형 프로그래머라면 객체보다 람다 캡슐화를 더 선호하실지도 모르겠다. 파이썬으로 역시 이렇게 할 수 있다. 그렇지만, 사실 이것은 정말 나에게 골치거리였다. 반복자 버전에서와 똑 같은 방식으로 일을 할 수 있었다. 그러나 뭔가 다른 것을 원했다. 몇 시간의 사투 끝에, 마침내 다음과 같은 결과에 도달하였다:
def fl(args, i=0, tmp="", parent_sibling=None): if not args: # at a leaf return (tmp, parent_sibling) if i < len(args[0]): # prepare my sibling sibling = fl(args, i+1, tmp, parent_sibling) return lambda: fl(args[1:], 0, tmp+args[0][i], sibling) else: # go up and visit the parent's sibling return parent_sibling # traverse function for lambda version def traverse(n): while n: if callable(n): # node n = n() else: # leaf (result, n) = n print result, print
실제로 아이디어는 트리 순회로 생각하는 것이다. 함수 f는 부분적 결과를 각 노드에 담고 있는 트리로 간주될 수 있다(그림 2). fl이 생산한 함수에는 트리에서 그의 위치와 다음 형제 노드 그리고 부모 노드의 다음 형제 노드를 유지한다. 트리를 타고 내려오면서, 벡트 요소들은 축적된다. 잎에 도달하면, 완전한 해답을 가지게 된다 (요소들의 조합). 같은 수준에서 더 이상 노드가 없다면, 부모 노드로 다시 돌아가 부모 노드의 다음 형제 노드를 시도한다. 트리를 순회하려면 특별한 구동 루틴이 필요하다.
물론 발생자 버전도 트리 순회로 간주할 수 있다. 이 경우 트리를 방문해서 각 노드에 결과를 떨어트린다.
CHANGES:
Jun 1, 2003: Released.
Jun 7, 2003: A small update based on the comments by Eli Collins.
Last Modified: Sat Jun 7 19:51:47 EDT 2003 (06/08, 08:51 JST)
Yusuke Shinyama