재귀함수를 쓸 때 주의해야하는 이유
주의
프로그래밍을 처음 배우면 그것이 어떤 언어든지 ‘재귀함수는 조심해서 써야한다’는 경고가 함께한다. 사실 재귀함수라는 게 그렇게 빈번하게 사용되는 테크닉이 아니기 때문에 그 이유는 설명하지 않는 경우가 많은데, 배우는 입장에선 이 좋은 걸 왜 꺼리는지 이해가 잘 되지 않을 수 있다. 예시를 통해 알아보자.
예시
def fibo1(n) :
if n==1 or n==2 :
return 1
else :
return fibo1(n-1) + fibo1(n-2)
for i in range(1,11) :
print(fibo1(i))
함수의 재귀호출은 프로그래밍을 하면서 만나는 여러가지 문제들에 대해 간단하면서도 우아한 해법이 된다. 코드를 쓰기도 쉽고, 읽기도 쉽다는 것은 어마어마한 장점이며 보통 복잡해질 수 있는 코드를 간단하게 줄여준다. 가령 피보나치 수열을 반환하는 프로그램을 짜야한다면, 재귀함수를 통해 간단하게 구현하는 것이 가능하다. 가령 위와 같은 파이썬 코드를 실행시키면 다음과 같이 피보나치 수열의 제$10$항까지를 계산해준다:
문제는 이러한 방법이 우리 인간에겐 편할 뿐, 컴퓨터가 받아들이기에는 상당히 불합리하다는 것이다. 컴퓨터는 매번 호출될 때마다 return fibo1(n-1) + fibo1(n-2)이라는 계산을 수행한 것이지, 점화식 $$ a_{n} : = \begin{cases} 1 &, n \le 2 \\ a_{n-2} + a_{n-1} &, n \ge 3 \end{cases} $$ 을 이해한 것이 아니다. 메모리 어딘가에 이전에 구한 항들이 저장되어있더라도, 재귀함수를 작성할 때 프로그래머가 요구한 것은 ‘이전의 항을 참조하는 것’이 아니라 ‘이전의 항을 계산하는 것’이었다. 다음은 위에서와 같은 함수를 호출 될때마다 그것을 알리도록 수정하고, $a_{10}$ 를 계산하는 과정을 움짤로 나타낸 것이다:
$a_{10}$ 가 계산되기 위해서는 $a_{8}$ 과 $a_{9}$ 가 계산되어야한다. 그런데 $a_{9}$ 가 계산되기 위해서는 $a_{7}$ 과 $a_{8}$ 이 계산되어야한다. 이러한 사실만 보아도 $a_{10}$ 이 호출되기 위해 $a_{8}$ 도 최소한 두 번은 호출되어야함을 알 수 있다. 다음은 실제로 fibo(10)을 계산하기 위해서 각각의 fibo(n)들이 몇 번이나 호출되는지를 나타낸다:
| fibo(n) | 횟수 |
|---|---|
| fibo(9) | 1 |
| fibo(8) | 2 |
| fibo(7) | 3 |
| fibo(6) | 5 |
| fibo(5) | 8 |
| fibo(4) | 13 |
| fibo(3) | 21 |
재미있게도, 피보나치 수열을 계산할 때의 중복호출은 피보나치 수열을 따르며 증가하다. 이러한 중복호출은 메모리에서든 시간에서든 엄청난 낭비를 야기한다. 또한 재귀함수의 본질이 ‘반복’인 이상, 이러한 문제점들이 항상 따라붙는다는 것을 명심해야한다.
이러한 문제들을 회피하는 방법으로써 동적 프로그래밍이라는 것이 있긴한데, 사실 이 방법은 재귀함수 자체를 쓰지 않는 것이나 마찬가지다. 동적 프로그래밍이 재귀호출의 문제를 해결해주는 것이 아니라, 재귀호출을 쓰지 말아야하는 문제를 정확하게 이해했을 때 재귀함수의 대안으로써 쓰이는 것이다.
코드
import time
def fibo1(n) :
if n==1 or n==2 :
return 1
else :
return fibo1(n-1) + fibo1(n-2)
for i in range(1,11) :
print(fibo1(i))
def fibo(n) :
if n==1 or n==2 :
return 1
else :
print("fibo(",n,") 호출됨!")
return fibo(n-1) + fibo(n-2)
for i in range(1,11) :
print(fibo1(i))
print(fibo(10))