10. 스택과 재귀(recursive), 파이썬

프로그래밍 언어를 구현할 때도 스택을 사용합니다.
좀 더 자세히 말씀드리면 함수의 호출은 스택으로 구현됩니다만, 이 부분을 자세히 설명드리는 것은 이 글의 범위를 벗어난 것 같습니다. 
혹시 이 부분에 대해 궁금하신 분은 다음 사이트를 참고하시기 바랍니다. 
https://dojang.io/mod/page/view.php?id=1376

 

스택으로 재귀 구현 흉내 내기를 해보겠습니다. 

 

먼저 재귀의 가장 흔한 예인 팩토리얼을 만들어 봅시다. 

 

5 팩토리얼은 다음과 같죠.. 

5! = 5*4*3*2*1 = 120

 

코딩을 합니다. 

# 팩토리얼 2019-06-01

def factorial(n):
    if n == 1:
        return n
    return n*factorial(n-1)


print(factorial(5))  # 120

 

리스트로 스택과 재귀를 흉내내는 게 무슨 의미가 있나 자괴감이 살짝 들수도 있겠지만 ....

의미가 있습니다. ^^

 

실제 프로그래밍을 할 때 재귀는 잘 쓰지 않고 반복문, 스택 등을 사용합니다. 

함수의 재귀에 사용되는 스택은 숫자의 제한이 있기 때문입니다. 

생각난 김에 파이썬 스택의 한계를 측정하는 코드를 작성해 보는 것도 좋을 것 같네요. 

스택 오버 플로우(https://stackoverflow.com/)라는 사이트도 있죠?

혹시 모르시는 분들을 위해서 간단히 설명하자면...
코딩하다가 모르는 것 있으면 구글에 검색해보세요. 
스택 오버 플로우가 연결되는 경우가 많습니다. 

python recursion limit increase 라고 검색해 보았습니다. 

 

 

본론으로 돌아가서 팩토리얼을 스택으로 코딩합니다...

def fact(n):
    stack = []
    while n > 0:
        stack.append(n)
        n -= 1
    result = 1
    while stack:
        result *= stack.pop()
    return result


print(fact(5))

 

팩토리얼을 코딩하는 가장 쉬운 방법: for 문을 이용.

def fact(n):
    result = 1
    for i in range(1, n+1):
        result *= i
    return result


print(fact(5))

 

함수형 프로그래밍으로.. 

from functools import reduce
print(reduce(lambda x, y: x*y, range(1, 6)))

 

생각난 김에 재귀의 한계도 보고 갑시다. 

def recur(n):
    print(n)
    return recur(n+1)

recur(1)

996까지 출력 후 다음 에러가 출력되네요. 

RecursionError: maximum recursion depth exceeded while calling a Python object
재귀에러: 파이썬 객체를 호출하는 중에 최대 재귀 깊이를 초과했습니다. 

재귀의 한계를 늘릴 수 있습니다. 

import sys
sys.setrecursionlimit(10**6)

위 recur함수를 다시 돌려봅니다. 
6436까지 출력 후 스택 오버플로우 에러가 출력되네요. 

MemoryError: stack overflow