[파이썬/Python] 재귀함수(Recursive function)와 메모이제이션(Memoization)

재귀함수(recursive function)란 함수 내부에서 자기 자신(함수)을 다시 호출하는 함수이다. 잘만 활용하면 참 좋다고 생각하는데, 가장 중요한 탈출 조건을 생각해내는 것이 상당히 까다로운 편이라 권장되지는 않고 있다. 또한, 재귀함수만 이용할 경우 과도하게 스택메모리를 이용하게 되고 탈출 조건을 잘못 세울 경우 스택오버플로우 에러가 발생할 위험도 존재한다. 그래서 동적 프로그래밍(Dynamic Progrmming)처럼 재귀함수의 각 단계 결과값을 저장하여 성능을 높여주는 방법도 존재한다. 우선 재귀함수의 예시를 두 개 들어보자.

 

1. 팩토리얼 구하기

일반적인 for문을 이용하여 팩토리얼을 구하면 다음과 같은 코드를 짤 수 있다.

def factorial_for(n):
    if n == 0 or n == 1:
        return 1

    answer = 1
    for i in range(1, n+1):
        answer = answer * i
    return answer
    

print(factorial_for(5)) # 120

반면, 재귀함수로 팩토리얼 구하는 기능을 구현하면 다음과 같다.

def factorial_recursion(n):
    if n == 1 or n == 0:
        return 1
    else:
        return n * factorial_recursion(n-1)
        
        
print(factorial_recursion(5)) # 120

결과값은 당연히 첫 번째 함수와 같아야 한다. 재귀함수는 어떤 식으로 계산하는 것인가 자세한 과정을 살펴보자. 자세한 과정을 살펴볼 때 factorial_recursion이라는 함수 이름은 너무 길기 때문에 factorial이라고 간단히 부르겠다.

 

1. 구하고자 하는 수가 5! 이라고 할 때, 사용자는 factorial(5)를 호출한다.
2. factorial 함수에 5라는 파라미터가 들어간 후 호출되면, n != 1 이므로 else에 걸려 5 * factorial(4) 를 return한다.
3. 다시 factorial(4)를 계산해야 하므로 factorial 함수에는 4라는 파라미터가 들어가게 되고, 이 또한 마찬가지로 n != 1 이므로 else에 걸려 4 * factorial(3) 을 return한다.
4. 그 과정을 한번 더 반복한 후 factorial(2) 를 계산해야 한다고 해보자. factorial(2)의 return값은 2 * factorial(1) 이며, factorial(1) 은 n == 1 이므로 if에 걸려서 return 1을 하게 된다. 여기가 바로 반복을 탈출할 수 있는 조건이 되겠다.
5. factorial(2) = 2 * factorial(1)은 이제 factorial(2) = 2 * 1 = 2 라는 것을 알게 되었으며, 자연스럽게 factorial(3)과 factorial(4)의 값을 알 수 있게 되어 factorial(5)의 값까지 알게 된다.

그림으로 확인해보면 이해가 더욱 잘 될 것 같다. 우선 탈출 조건인 n == 1 이 될 때까지 factorial 함수가 어떻게 진행되는지 확인해보자.

factorial(2) 내부에서 else에 걸려 2 * factorial(1)이 되고 factorial(1)은 탈출 조건인 n == 1에 걸려 return 1을 하게 된다. 이후 탈출에 성공한 재귀함수는 아래 그림과 같이 가장 아랫단부터 역으로 올라가며 더 윗 단계의 함수들의 결과값을 리턴할 수 있게끔 한다.

최종적으로 factorial(5)까지 거슬러 올라온 재귀함수는 찾고자 하는 값에 도달했으므로 5*4*3*2*1의 값을 리턴하며 함수를 종료하게 된다.

 

2. 피보나치 수열

재귀함수의 또 다른 대표적인 예시는 피보나치 수열을 구하는 함수이다. 피보나치 수열은 다음과 같은 특성을 갖고 있다.

• if (n = 0) : 0
• if (n = 1) : 1
• if (n > 1) : f(n-1) + f(n-2)

특성 그대로 코드를 구현해주면 되기 때문에 너무나도 쉬운, 말할 가치도 없는 코드이다. 바로 재귀함수로 구현해보겠다.

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)
        
        
print(fibonacci(10)) # 55

 

※ 재귀함수의 문제점 및 해결책

재귀함수의 가장 큰 문제점은 효율성이 좋지 못하다는 점인데, 이미 계산되었던 값일지라도 의미 없이 다시 계산을 반복하기 때문이다. 실제로 팩토리얼을 구하는 기능의 두 함수를 비교하기 위해 100! 을 구하는 두 함수를 천 번 반복할 경우 다음과 같이 2.4배 가량의 시간 차이가 발생한다. 

# 1. factorial function using the 'for'
def factorial_for(n):
    if n == 0 or n == 1:
        return 1

    answer = 1
    for i in range(1, n+1):
        answer = answer * i
    return answer

# 2. factorial function using the 'recursion'
def factorial_recursion(n):
    if n == 1 or n == 0:
        return 1
    else:
        return n * factorial_recursion(n-1)

# factorial_for vs. factorial_recursion
from timeit import *
t1 = Timer("factorial_for(100)", "from __main__ import factorial_for")
t2 = Timer("factorial_recursion(100)", "from __main__ import factorial_recursion")
print("factorial_for(100) * 1,000 times : ", t1.timeit(number = 1000), "seconds")
print("factorial_recursion(100) * 1,000 times  ", t2.timeit(number = 1000), "seconds")

# factorial_for(100) * 1,000 times :  0.017826356 seconds
# factorial_recursion(100) * 1,000 times   0.043898705999999996 seconds

심지어, 피보나치 수열은 더욱 심각하다. 위처럼 timeit 모듈을 활용하여 피보나치의 30번째 수를 구하는 과정을 10번만 반복해도 빠를 때는 3.6초에서 느릴 때는 4.9초까지 걸렸다. 프로그래머스 코딩테스트 Level 2 문제 중 '피보나치 수'라는 문제에서는 n번째 피보나치 수를 구한 후 1234567로 나눈 나머지를 리턴해야 하는데 제한 사항이 1 이상 100,000만 이하의 자연수 n이다. 분명 효율성 테스트에서 10만이라는 n도 주어질 것이라 생각되는데, 이럴 때는 분명 시간 초과가 떠서 통과할 수 없을 것이다.

 

그래서 위와 같은 문제점을 해결하기 위해 동적계획법(Dynamic Programming, DP)에서 활용되는 메모이제이션(Memoization)을 사용해야 한다. DP는 코딩테스트에서 너무나도 다양한 모습으로 등장하기 때문에 나중에 알고리즘을 정리할 때 DP에 대해 자세히 다루도록 하겠다. 핵심적인 내용만 얘기하자면, DP에서는 큰 문제를 해결하기 위해 작은 문제들을 해결해나가야 하는데, 그 작은 문제들의 결과값은 변하지 않아야 한다. 그리고 그 결과값이 변하지 않는 작은 문제들이 자꾸 반복해서 일어나게 된다.

 

메모이제이션은 자꾸만 반복되지만 그 결과값은 변하지 않는 작은 문제들의 결과값을 저장하는 것을 의미한다. 메모이제이션을 통해 이미 결과값이 기록되는 특정 문제가 반복할 때, 불필요한 계산은 패스하고 기록되어 있는 값만 불러오면 아주 빠르게 해결할 수 있다. 재귀함수 또한 큰 문제를 해결하기 위해 탈출 조건을 만날 때까지 작은 문제들을 풀어나가야 하고, 그 과정 중에 반복되는 작은 문제들이 있을 수 있다.

 

거창할 건 없고, 피보나치의 n번째 수를 구하는 함수에 메모이제이션 개념을 도입하면 다음과 같이 코드를 짤 수 있다.

dic = {} # memoization을 위한 dictionary를 함수 외부에 선언

def fibonacci_2(n):
    if n in dic: # 기록되어 있는 값을 바로 return함으로써 효율성 증대
        return dic[n]

    if n == 0:
        dic[0] = 0
        return 0
    elif n == 1:
        dic[1] = 1
        return 1
    else:
        dic[n] = fibonacci_2(n-1) + fibonacci_2(n-2)
        return dic[n]

위 코드가 지저분하면 다음과 같이 n이 0일 때와 1일 때를 dictionary에 미리 넣어둘 수도 있다.

dic = {0:0, 1:1} # memoization을 위한 dictionary를 함수 외부에 선언

def fibonacci_2(n):
    if n in dic: # 기록되어 있는 값을 바로 return함으로써 효율성 증대
        return dic[n]

    dic[n] = fibonacci_2(n-1) + fibonacci_2(n-2)
    return dic[n]

그렇다면 이러한 memoization을 통해 효율성이 얼마나 증대될까? 또 한 번 비교를 해보자!

# 1. fibonacci function using the 'recursion'
def fibonacci_1(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci_1(n-1) + fibonacci_1(n-2)

# 2. fibonacci function using the 'recursion' and 'memoization'
dic = {0:0, 1:1}
def fibonacci_2(n):
    if n in dic:
        return dic[n]

    dic[n] = fibonacci_2(n-1) + fibonacci_2(n-2)
    return dic[n]

# fibonacci_1 vs. fibonacci_2
from timeit import *
t3 = Timer("fibonacci_1(30)", "from __main__ import fibonacci_1")
t4 = Timer("fibonacci_2(30)", "from __main__ import fibonacci_2")
print("fibonacci_1(30) * 20 times : ", t3.timeit(number = 20), "seconds")
print("fibonacci_2(30) * 20 times  ", t4.timeit(number = 20), "seconds")

# fibonacci_1(30) * 20 times :  8.453629271 seconds
# fibonacci_2(30) * 20 times   3.624800000068262e-05 seconds

30번째 피보나치 수열을 찾는 과정을 20번 반복한 결과, 단순히 재귀함수를 이용했을 때는 8.45초 가량이 소요되었으며, memoization을 활용한 결과 0.000036초 가량이 소요되었다. 계산기에 두 결과값을 넣어 나누어 보니 233,216배 가량이 차이났다. 단순한 비교를 위해 30번째 피보나치 수를 찾아봤지만, 재귀함수만을 이용한 함수에서 50번째 수를 찾으려고 하면 컴퓨터가 몇 분째 답하지 않게 된다. 그렇듯, 조금만 숫자가 올라가도 그 시간복잡도가 매우 증대되기 때문에 효율성을 증진시키기 위해 memoization이 더더욱 필요하다고 볼 수 있다.

 

정리

1. 재귀함수를 구현하고 싶을 때, 탈출 조건을 잘 정해야 한다.

2. 재귀함수의 효율성이 많이 떨어지게 될 경우, 재귀함수가 한 번 호출될 때마다의 결과값을 저장하여 효율성을 증대시키자.

 

 

 

source :

1. 윤인성님의 유튜브, "Hello Coding 파이썬 44강 - 재귀함수와 메모화"