Unit 33. 함수에서 재귀호출 사용하기

함수 안에서 함수 자기자신을 호출하는 방식을 재귀호출(recursive call)이라고 합니다. 재귀호출은 일반적인 상황에서는 잘 사용하지 않지만 알고리즘을 구현할 때 매우 유용합니다(구현은 만들다와 같은 뜻입니다). 보통 알고리즘에 따라서 반복문으로 구현한 코드보다 재귀호출로 구현한 코드가 좀 더 직관적이고 이해하기 쉬운 경우가 많습니다.

이번에는 재귀호출을 사용하는 방법과 주의점을 알아보겠습니다. 참고로 재귀호출은 코드가 간단한 편이지만 머릿속으로 생각을 많이 해야 됩니다. 그래서 초보자들은 한 번에 이해가 되지 않을 수 있습니다.

33.1 재귀호출 사용하기

먼저 간단한 재귀호출 함수를 만들어보겠습니다. 다음 내용을 IDLE의 소스 코드 편집 창에 입력한 뒤 실행해보세요.

recursive_function_error.py

def hello():
    print('Hello, world!')
    hello()
 
hello()

실행 결과

Hello, world!
Hello, world!
Hello, world!
...(생략)
Traceback (most recent call last):
  File "C:₩project₩recursive_function_error.py", line 5, in <module>
    hello()
  File "C:₩project₩recursive_function_error.py", line 3, in hello
    hello()
  File "C:₩project₩recursive_function_error.py", line 3, in hello
    hello()
  File "C:₩project₩recursive_function_error.py", line 3, in hello
    hello()
  [Previous line repeated 974 more times]
  File "C:₩project₩recursive_function_error.py", line 2, in hello
    print('Hello, world!')
RecursionError: maximum recursion depth exceeded while pickling an object

hello 함수 안에서 다시 hello 함수를 호출하고 있습니다. 소스 코드를 실행해보면 'Hello, world!' 문자열이 계속 출력되다가 에러가 발생합니다. 왜냐하면 파이썬에서는 함수 호출 스택의 깊이 제한이 1,000으로 정해져 있어서 그렇습니다. 즉, hello 함수가 자기자신을 계속 호출하다가 스택이 넘쳐서 스택 오버플로우(stack overflow)가 발생합니다.

재귀호출을 그림으로 나타내면 다음과 같은 모양이 됩니다.

그림 33-1 재귀호출과 스택 넘침 현상
그림 33 1 재귀호출과 스택 넘침 현상

재귀호출을 사용하려면 반드시 다음과 같이 종료 조건을 만들어주어야 합니다.

recursive_function_exit_condition.py

def hello(count):
    if count == 0:    # 종료 조건을 만듦. count가 0이면 다시 hello 함수를 호출하지 않고 끝냄
        return
    
    print('Hello, world!', count)
    
    count -= 1      # count를 1 감소시킨 뒤
    hello(count)    # 다시 hello에 넣음
 
hello(5)    # hello 함수 호출

실행 결과

Hello, world! 5
Hello, world! 4
Hello, world! 3
Hello, world! 2
Hello, world! 1

먼저 hello 함수의 반복 횟수를 계산하기 위해 매개변수 count를 지정합니다. 그리고 count가 0이면 hello 함수를 호출하지 않고 끝냅니다. 만약 0이 아니면 'Hello, world!'를 출력하고, count의 값을 1씩 감소시킨 뒤 hello 함수를 호출할 때 넣어줍니다.

def hello(count):
    if count == 0:    # 종료 조건을 만듦. count가 0이면 다시 hello 함수를 호출하지 않고 끝냄
        return
    
    print('Hello, world!', count)
    
    count -= 1      # count를 1 감소시킨 뒤
    hello(count)    # 다시 hello에 넣음

이제 hello 함수를 호출할 때 반복할 횟수를 넣어줍니다. 이렇게 하면 hello 함수가 재귀호출을 할 때마다 count에 들어있는 값이 1씩 감소하고, 0이 되면 재귀호출을 끝냅니다.

hello(5)    # hello 함수 호출
그림 33-2 재귀호출에서 종료 조건을 지정
그림 33 2 재귀호출에서 종료 조건을 지정