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

이번에는 재귀호출을 사용하는 방법과 주의할점에 대해서 알아보자. 재귀호출은 코드는 간단하지만 머리속으로 생각을 많이 해야한다. 그래서 초보자는 처음에 이해하기가 좀 어려울 수 있다.

1. 재귀호출 사용하기

먼저 간단한 재귀호출 함수를 만들어보자

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, world!' 를 출력하고 다시 hello 함수를 호출한다. 호출된 함수는 다시 문자열을 출력하고 계속 반복이 된다. 그러다가 오류가 발생하고 종료가 되는데 그 이유는 파이썬에서 최대 재귀 깊이(maximum recursion depth)가 1,000으로 정해져 있기 때문이다. 즉, hello 함수가 자기자신을 계속 호출하다가 최대 재귀 깊이를 초과하면 RecursionError 가 발생한다.

재귀호출 종료 조건 만들기

재귀호출을 사용하기 위해선 종료 조건을 만들어야 한다 그렇지 않으면 앞서 위에서 보았듯이 무한반복 되다가 오류를 내뿜으면서 종료가 된다.

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

2. 재귀로 팩토리얼 구하기

재귀로 팩토리얼을 구해보자. 팩토리얼은 1부터 n 까지의 곱을 구한 것이다. 예를 들어서 5! 는 5 x 4 x 3 x 2 x 1

이며 결과는 120이다. 그러면 실제로 만들업자

def factorial(n):
    if n == 1:      # n이 1일 때
        return 1    # 1을 반환하고 재귀호출을 끝냄
    return n * factorial(n - 1)    # n과 factorial 함수에 n - 1을 넣어서 반환된 값을 곱함
 
print(factorial(5))

실행 결과

120

계속 재귀가 진행되다가 다섯 번째 호출에서 1을 리턴한다. 그 뒤에 1과 2를 곱해서 2를 반환하고 3과 2를 곱해서 6을 반환하고 6과 4를 곱해서 24를 반환하고,, 이런식으로 진행되다가 24 와 5를 곱해 120을 리턴하게 된다.