파이썬 강좌 번외편. 재귀 함수

우리는 함수 내에서 또 다른 함수를 호출할 수 있습니다. 그리고 물론 자기 자신을 호출할 수도 있습니다. 여기서 함수 내에서 자기 자신을 호출하는 함수를 재귀 함수라고 부릅니다. 이 재귀 함수는 팩토리얼이나 피보나치 수열을 만드는 등과 같은 다양한 수학 문제를 해결하는 데 매우 유용합니다. 예제를 보며 직접 한번 살펴보도록 하겠습니다.

>>> def recursive(num):
         	print(num)
         	num += 1
         	recursive(num) # 자기 자신을 호출한다!
 
>>> recursive(10)
10
11
12
13
…

위의 예제를 직접 실행시켜보면 함수 recursive()가 자기 자신을 호출하고, 호출된 함수가 다시 자기 자신을 호출하며 끊임없이 변수 num의 값을 출력하고 있는 것을 볼 수 있습니다. IDLE에서 위의 예제를 실행시키셨다면 Ctrl+C를 통해 KeyboardInterrupt를 발생시켜 무한 재귀에서 빠져나올 수 있습니다. 재귀 함수 역시도 우리가 제어문에서 보았던 무한 루프와 같이 조건문을 통해서 제어가 가능합니다. 아래 예제를 보도록 합시다.

>>> def factorial(n):
         	if n == 1:
                       	return 1
         	else:
                       	return n * factorial(n - 1)
 
>>> factorial(5)
120

ll위는 재귀 호출을 통한 팩토리얼 계산을 하는 예제입니다. 함수를 계속해서 호출하다가, 매개변수 n으로 넘어간 값이 1이라면 함수를 더이상 호출하지 않고 1을 그대로 돌려주게 됩니다. 재귀 호출의 과정을 천천히 살펴보면 아래와 같은 과정을 거칠 것입니다. 우리가 직접 결과를 계산해 보아도 위와 동일한 결과값을 얻을 수 있습니다.

factorial(5)
5 * factorial(4)
5 * 4 * factorial(3)
5 * 4 * 3 * factorial(2)
5 * 4 * 3 * 2 * factorial(1)
5 * 4 * 3 * 2 * 1
5 * 4 * 3 * 2
5 * 4 * 6
5 * 24
120

아래에서 예외가 발생한 이유는 파이썬이 끝없이 자신을 호출함으로써 스택 오버플로를 발생시키는 것을 막기 위해 재귀 깊이(recursion depth)를 두었기 때문입니다. 파이썬에서 함수를 호출할 때마다 스택이라고 불리는 곳에 일정량의 공간을 필요로 합니다.

>>> factorial(2000)
Traceback (most recent call last):
  File "<pyshell#35>", line 1, in <module>
    factorial(3000)
…
RecursionError: maximum recursion depth exceeded in comparison

물론, 파이썬에서 걸어둔 이 제한을 아래와 같은 방법으로 풀 수 있습니다. 그러나, 아래와 같이 한계를 수정해 버리는 것은 적절치 못한 방법이며 재귀 호출을 사용하는 대신에 반복문으로 대체하는 것을 권장합니다.

>>> import sys
>>> sys.getrecursionlimit()
1000
>>> sys.setrecursionlimit(1500)

아래는 재귀 함수로 구현된 팩토리얼 함수를 반복문으로 대체한 것입니다.

>>> def factorial(n):
            	result = 1
            	for i in range(2, n + 1):
                            	result *= i
            	return result
 
>>> factorial(1000)
4023872600770937735437024339230039857193748642107146325437999104299385123986290205920442084869694048004799886101971960586316668729948085589…

재귀 함수는 코드를 간결하게 만들어 주는 장점이 있습니다. 그러나, 재귀 함수는 디버그 하기가 어렵고 메모리를 상당히 잡아먹으며 시간도 소비하므로 그에 따른 비용이 많이 듭니다.