모든 것의 시작은 아주 단순한 것이었습니다. 저는 그저 바둑판에서 나타날 수 있는 모든 경우의 수라는 361!(19*19의 계승)을 계산하고 싶었을 뿐이었습니다. 그래서 Python에서 재귀를 이용한 아주 단순한 코드를 입력했지요.

>>> def factorial(n):
...     if n <= 1:
...         return 1
...     else:
...         return n * factorial(n-1)
...
>>> factorial(19*19)
1437923258884890654832362511499863354754907538644755876127282765299227795534389618856841908003141196071413794434890585968383968233304321607713808837056557879669192486182709780035899021100579450107333050792627771722750412268086775281368850575265418120435021506234663026434426736326270927646433025577722695595343233942204301825548143785112222186834487969871267194205609533306413935710635197200721473378733826980308535104317420365367377988721756551345004129106165050615449626558110282424142840662705458556231015637528928999248573883166476871652120015362189137337137682618614562954409007743375894907714439917299937133680728459000034496420337066440853337001284286412654394495050773954560000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
>>> len(str(factorial(19*19)))
769

…여기에서 끝내면 좋았을 것을, 어째서인지는 기억나지 않지만 하여튼 이 재귀식이 어디까지 돌아가는지 한번 보고 싶었습니다. 어쩌면 그냥 스택이 터지는 것을 보고 싶었던 건지도 모르겠네요. 마침 정보처리기사 필기 교재에서 스택 오버플로우에 대해 읽은 후이기도 하고.

몇 번의 실험 결과, 이게 환경에 따라서 RecursionError가 뜨는 숫자가 다르다는 것이 드러났습니다. iPython 노트북에서는 저 함수에 숫자 488만 집어넣어도 에러가 뜨는 반면, 그냥 Python 콘솔에서는 998까지도 문제 없이 실행이 되는 걸 발견한 거지요. 하여튼, 여기에서 끝내어도 좋았을 것입니다만…

문득 재귀식의 한계를 극복해 보고 싶어졌습니다. 저걸 넘어서는 숫자를 재귀식으로 처리하는 모습을 보고 싶어진 것이죠.

발상은 이랬습니다. 재귀식이 한번에 일정 숫자 이상 재귀를 하지 못한다면, 일정 숫자만큼만 재귀하고 그 결과를 기억한 다음 다시 재귀를 반복하면 된다는 것이지요. 마침 저는 메모이제이션(Memoization)이라는 기법에 대해 알고 있었습니다. 이건 프로그램에서 이전에 실행했던 작업의 결과물을 캐싱하고 있다가, 다음 번에 똑같은 입력이 오면 기억하고 있던 내용을 바로 출력해 주는 것입니다. 이걸 응용하면 어떻게 될지도 모른다는 생각이 든 것이지요. 말하자면 메모이제이션 기법과 분할정복(Divide-and-conquer) 기법을 함께 사용한 거라고 할 수 있겠습니다.

그리하여 다음과 같은 코드가 나왔습니다.

※주의! 아래의 코드는 실행시 10GB 이상의 메모리를 소비합니다! 이 코드를 실행한 결과는 절대 책임지지 않습니다.

def processDivide(f):
    a = 0
    def wrapper(x):
        if x > 100:
            nonlocal a
            while a < x:
                a += 100
                f(a)
        return f(x)
    return wrapper

def memoize(f):
    memo = {}
    def wrapper(x):
        if x not in memo:
            memo[x] = f(x)
        return memo[x]
    return wrapper

@processDivide
@memoize
def factorial(n):
    if n <= 1:
        return 1
    else:
        return n * factorial(n-1)

def main():
    print(factorial(100000))

main()

으헤헤헤헤헤헤헤… 메모리가 가득차버렷!!

제 컴퓨터에서 위 코드를 실행하면 10여 초의 시간과 10GB 이상의 메모리를 소비하여 45만 6574자리에 달하는 기다란 숫자를 내뱉습니다. 덤으로, 저기서 10만이란 숫자 뒤에 0 하나만 더 붙이면 메모리 부족으로 시스템이 다운되더군요. 네. 직접 해봤습니다. (…)

이렇게 컴퓨터를 쓸데없이 혹사시킨 건 그렇다 치고, 곧 다가오는 정보처리기사 필기 시험은 어찌 치나 걱정되는 1人의 오늘의 잉여짓이었습니다.

p.s.
이걸 재귀가 아니라 반복문으로 바꾸면 어찌 되느냐고요?

def factorial_iter(n):
    a, b = 0, 1
    while a < n:
        a += 1
        b = b * a
    return b

네. 훨씬 심플하고, 메모리도 별로 먹지 않는 코드가 나옵니다.
그러니까 결론은 위의 코드는 모두 잉여짓이라는 거