재귀 에서

재귀 소개

재귀는 함수가 자기 자신을 호출하면서 함수 안의 코드를 반복 실행하는 방법이에요. 자기 자신을 호출하는 함수를 재귀 함수라고 해요. 재귀는 반복하는 또 다른 방법으로 볼 수 있어요. 그리고 반복과 마찬가지로, 불리언 표현식이나 True/False 검사로 재귀 실행을 언제 멈출지 결정해요.

반복과는 달리, 파이썬에서 종료 조건이 없는 재귀는 무한히 실행될 수 없어요. 각 함수 호출에서 쓰이는 값은 파이썬 인터프리터 스택에서 자기만의 프레임에 놓여요. 함수 호출의 총 개수가 스택이 감당할 수 있는 공간보다 많아지면 오류가 발생해요.

반복 구현과 재귀 구현

반복과 재귀는 둘 다 되풀이한다는 점에서 비슷하게 느껴질 수 있어요. 하지만 코드 수준에서도, 구현 수준에서도 _보이는 모습_은 달라요. 반복은 호출 스택의 같은 프레임 안에서 일어날 수 있어요. 보통 하나 이상의 변수 값을 갱신하면서 각 반복의 상태를 조금씩 유지하는 식으로 관리해요. 효율적인 구현이지만, 코드를 들여다볼 때는 다소 복잡해 보일 수 있어요.

재귀는 _변수 상태_를 갱신하는 대신, _갱신된 값_을 같은 함수의 다음 호출(반복)에 인자로 바로 넘길 수 있어요. 이렇게 하면 함수 본문이 깔끔해지고 각 갱신이 어떻게 일어나는지도 분명해져요. 하지만 같은 함수를 호출할 때마다 스택에 프레임이 하나씩 쌓이기 때문에, 구현 효율은 오히려 더 떨어져요.

재귀: 언제 쓰고, 언제 쓰지 않을까요?

스택 오류나 오버플로가 생길 위험이 있다면, 왜 재귀로 문제를 풀려고 할까요? 가독성, 추적 가능성, 그리고 의도 때문이에요. 어떤 해법은 반복으로 표현할 때보다 재귀로 표현할 때 더 읽기 쉽거나 더 쉽게 따져볼 수 있는 상황도 있어요. 데이터를 사용하거나 변경하는 방식, 복잡성 관리, 책임 분배, 작업량 구성 등과 관련된 프로그램 차원의 제약이 있을 수도 있어요.

재귀에 잘 맞는 문제로는 시간이 지날수록 작아지는, 복잡하지만 반복적인 문제, 특히 분할 정복 알고리즘과 누적 알고리즘이 있어요. 하지만 파이썬은 스택에 올릴 수 있는 프레임 수에 제한이 있어서, 모든 문제가 완전한 재귀 전략의 이점을 누리는 것은 아니에요. 재귀가 덜 어울리는 문제로는 일정한 상태를 유지하면서 정해진 횟수만큼 반복해야 하는 문제, 비동기로 실행해야 하는 문제, 아주 많은 반복이 필요한 상황이 있어요.

반복 전략과 재귀 전략: 인디라의 걱정

인디라는 매달 받는 사회 보장 연금이 **둘째 수요일**마다 은행 계좌에 자동으로 입금되게 해 두었어요. 인디라는 수표 잔고를 맞추는 일이 걱정돼요. 입금되기 전에 수표를 써 버릴까 봐 걱정스러워요. 그래서 손녀 아디야에게 돈이 계좌에 들어오는 날짜 목록을 만들어 달라고 부탁해요.

막 파이썬 프로그래밍을 배우기 시작한 아디야는 처음 떠오른 대로 프로그램을 짜 봐요. 입금 날짜들을 출력할 수 있도록 그 목록을 list로 반환하고 싶어요. 또 _어떤 연도_에도 쓸 수 있는 함수를 만들고 싶어 해요. 일정이 바뀔 수도 있고 (다른 친척들이 아디야에게 자기 입금 일정도 계산해 달라고 할 수도 있고), 그래서 _요일_을 받는 매개변수를 하나 더 두기로 해요. 마지막으로 그 달의 몇 번째 요일인지, 예를 들어 첫째, 둘째 등을 받는 매개변수도 필요하다고 판단해요. 이런 요구 사항을 모두 만족시키기 위해, datetime에서 가져온 date 클래스를 쓰기로 해요. 이걸 모두 합쳐서 아디야가 만든 코드는 이래요:

from datetime import date


def paydates_for_year(year, weekday, ordinal):
    """Returns a list of the matching weekday dates.
    
    Arguments:
        year (int): The year (e.g. 2022).
        weekday (int): The weekday number (e.g. 3 for Wednesday).
        ordinal (int): Which weekday of the month (e.g. 2 for the second day).
    
    Returns:
        output (list): Matching weekday dates.
    """
    
    output = []

    for month in range(1, 13):
        for day_num in range(1, 8):
            if date(year, month, day_num).isoweekday() == weekday:
                output.append(date(year, month, day_num + (ordinal - 1) * 7))
                break
    return output

# find the second Wednesday of the month for all the months in 2022
print(paydates_for_year(2022, 3, 2))

이 첫 번째 버전도 잘 동작하지만, 아디야는 더 적은 줄과 덜 중첩된 반복으로 코드를 리팩터링할 수 있을지 궁금해져요. 상태 변경을 최소화하는 게 좋다는 글도 읽은 터라, output, month, day_num 같은 변수를 변경하지 않도록 할 수 있을지도 알아보고 싶어요.

재귀에 대해서도 알고 있는 아디야는, 프로그램을 재귀 방식으로 바꿀 수 있을지 생각해 봐요. 반복 함수에서 만들고 변경하던 변수들을 대신 인자로 넘길 수 있겠다는 거예요. 함수 안에서 변수를 변경하는 대신, 갱신된 값을 인자로 다음 함수 호출에 넘길 수 있어요. 그런 생각으로 만든 재귀 방식은 이래요:

from datetime import date


def paydates_for_year_rec(year, weekday, ordinal, month, day_num, output):
    """Returns a list of the matching weekday dates
    
    Arguments:
        year (int): The year (e.g. 2022).
        weekday (int): The weekday number (e.g. 3 for Wednesday).
        ordinal (int): Which weekday of the month (e.g. 2 for the second day).
        month (int): The month number currently being processed.
        day_num (int): The day number of the month currently being processed.
    
    Returns:
        output (list): Matching weekday dates.
    """
    
    if month == 13:
        return output
        
    if date(year, month, day_num).isoweekday() == weekday:
        return paydates_for_year_rec(
                 year, weekday, ordinal, month + 1, 1, output
                 + [date(year, month, day_num + (ordinal - 1) * 7)]
                 )
    
    return paydates_for_year_rec(year, weekday, ordinal, month, day_num + 1, output)

# find the second Wednesday of the month for all the months in 2022
print(paydates_for_year_rec(2022, 3, 2, 1, 1, []))

아디야는 중첩 루프도 없고, 변경되는 상태도 없고, 코드 줄도 2줄이나 줄었다는 사실이 기뻐요!

다만 재귀 방식이 반복 방식보다 단계를 더 많이 거쳐서 성능이 더 떨어진다는 점은 조금 걸려요. 그래도 문제를 재귀로 다시 써 보면서 지저분한 중첩 반복(성능을 해치는 요소)과 과도한 상태 변경, 복잡한 조건문에서 오는 혼란을 확실히 정리할 수 있었어요. 코드가 더 "읽기 쉬운" 느낌도 들어요. 한동안 손을 놓았다가 다시 이 코드를 봐도, 더 수월하게 읽으면서 무슨 일을 하는지 기억해 낼 수 있을 거라고 확신해요.

앞으로 아디야는 문제를 먼저 재귀로 풀어 볼지도 몰라요. 중첩과 변경, 복잡함을 최소화하면 문제를 처음부터 또렷한 단계로 따라가기가 더 쉬울 수 있거든요. 기본 로직을 정리한 다음에는, 처음에 만든 재귀 단계를 성능이 더 좋은 반복 방식으로 최적화하는 데 집중할 수 있어요.

더 나중에 tuples를 배우면, Calendar.itermonthdates와 함께 list comprehension을 쓰거나 특정 값을 메모이제이션하는 식으로 더 "최적화"하는 방법도 고려해 볼 수 있어요.

재귀의 변형: 꼬리 호출

꼬리 호출은 함수의 마지막 문이 자기 자신만 호출하고 그 외에는 아무것도 하지 않는 경우를 말해요. 다음 예시는 자기 자신을 호출한 결과에 1을 더하기 때문에 꼬리 호출이 아니에요:

def print_increment(step, max_value):
    if step > max_value:
        return 1
    print(f'The step is {step}')
    return 1 + print_increment(step + 1, max_value)


def main():
    retval = print_increment(1, 2)
    print(f'retval is {retval} after recursion')

if __name__ == "__main__":
    main()

실행하면 이렇게 출력돼요:

The step is 1
The step is 2
retval is 3 after recursion

꼬리 호출로 리팩터링하려면 retval을 print_increment의 매개변수로 만들면 돼요.

def print_increment(step, max_value, retval):
    if step > max_value:
        return retval
    print(f'The step is {step}')
    return print_increment(step + 1, max_value, retval + 1)


def main():
    retval = print_increment(1, 2, 1)
    print(f'retval is {retval} after recursion')

if __name__ == "__main__":
    main()

꼬리 호출이 꼬리 호출이 아닌 재귀 호출보다 따져 보기가 훨씬 쉬울 수도 있어요. 그래도 재귀를 쓸 때는 스택이 넘칠 만큼 반복이 많아지지 않는다는 점을 늘 확인하는 게 중요해요.

파이썬의 재귀 한도

어떤 언어는 꼬리 호출을 최적화해서, 스택에 프레임을 새로 추가하는 대신 함수를 처음 호출할 때의 스택 프레임을 각 재귀 호출이 재사용할 수 있어요 (반복이 프레임을 재사용하는 방식과 비슷해요). 파이썬은 그런 언어가 아니에요. 스택 오버플로를 막기 위해, 파이썬에는 기본값이 1,000 프레임인 재귀 한도가 있어요. 인터프리터가 재귀 한도를 넘었다고 판단하면 RecursionError 예외가 발생해요. sys.setrecursionlimit 메서드로 재귀 한도를 늘릴 수도 있지만, 그러면 런타임 세그멘테이션 오류가 나서 프로그램이, 어쩌면 운영체제까지 멈출 위험이 있어요.

참고 자료

파이썬에서 재귀를 더 알아보고 싶다면 다음부터 시작해 봐요

• python-programming: recursion
• Real Python: python-recursion
• Real Python: python-thinking-recursively