자료구조 핵심 원리 - 재귀 함수

 

1.  재귀함수

재귀(recursion) 함수란 호출된 함수가 자기 자신을 다시 호출하는 풀이 방식입니다.실제 개발할 때 재귀 함수를 보기란 쉽지 않습니다. 하지만 커다란 문제를 쪼개 부분 문제로 만들어 해결함으로써 전체 문제를 풀어 나가는 구조를 설계할 때는 반드시 필요하기에 자료 구조나 알고리즘에서는 알아야 하는 필수 개념입니다. 스택 프레임과 지역 변수의 역할을 알고 나면 쉽게 이해할 수 있습니다.

 

1.1  재귀 함수로 팩토리얼 구현하기

n의 팩토리얼은 1부터 n까지 곱을 의미하고 n!라고 표기합니다. 4!은 1×2×3×4을 의미합니다. 4! = 3!×4과 같이 풀어 쓸 수도 있습니다. 일반화하면 n! = (n-1)!×n

 

def factorial(n):
    return factorial(n-1) * n # 1

if __name__ == "__main__":
    for i in range(1, 6):
        print(factorial(i)) # 2

 

# 2에서 factorial 함수를 호출하고 있습니다. 호출된 함수는 # 1 라인을 만나고, 다시 factorial 함수를 호출합니다. 이와 같이 실행 도중에 자기 스스로를 다시 호출하는 함수가 재귀 함수입니다. 하지만 실행하면 RecursionError가 발생합니다. 최대 재귀 깊이를 초과했습니다. 다음과 같이 수정합니다.

 

def factorial(n):
    # base case
    if n <= 0: # 1
        return 1
    return n*factorial(n-1)

if __name__ == "__main__":
    for i in range(1, 6): 
        print(factorial(i))

 

# 1을 보면 매개변수 n이 0일 때, 즉 0!일 때 1을 반환하도록 되어 있습니다. 음수는 조건에서 제외합니다. 더 이상 재귀함수가 호출되지 않도록 하는 '특정 조건'을 base case(기저 사례)라고 합니다.

 

재귀 함수를 구현하려면 1) 언제 어떤 매개변수를 가지고 호출할지 정해야 하고, 2) 호출을 정지시켜 줄 기저 사례가 필요합니다. 

 

 

1.2  스택 프레임으로 재귀 함수 이해하기

함수가 호출되면 메모리에서는 스택 프레임이라는 공간이 생깁니다. 이 스택 프레임에는 함수 실행에 필요한 지역 변수들이 할당됩니다.

 

def add_two(a, b):
    c = a + b # 4
    return c

a = 10 # 1
b = 20 # 2
result = add_two(a, b) # 3
print(result)

 

# 1과 # 2는 프로그램이 시작되면서부터 끝날 때까지 메모리에 유지되는 전역 변수입니다. # 3에서 a와 b를 인수로 전달하고 add_two 함수를 호출하면 내부적으로 ‘스택 프레임’이라는 내부 공간이 생기고, 그 공간에 add_two 함수 내부에 있는 매개변수 a, b와 그 결괏값을 담을 지역 변수 c가 저장됩니다.

 

 # 3에서 매개변수로 전달된 a와 b는 # 1과 # 2에 있는 a와 b가 아닙니다. # 3에서 함수가 호출된 순간 매개변수를 비롯한 지역 변수를 저장할 공간을 따로 만들고, 전달된 10과 20이라는 a와 b 값만 복사하여 전달하게 됩니다. 최종적으로 a와 b의 연산이 끝나고 c에 값이 잘 저장된 후에는 return을 만나면 함수가 종료되는데, 이때 만들어졌던 add_two 함수의 스택 프레임 역시 사라집니다. 스택 프레임의 생성 시기는 함수를 호출했을 때고, 소멸 시기는 함수 실행이 종료되었을 때입니다.

 

스택 프레임은 메모리에 생성되는데 생성될 수 있는 크기에 한계가 있습니다. 그러므로 계속 쌓인다면 언젠가는 최대 한계치에 도달할 수밖에 없지요. 이때 발생하는 에러가 Recursion Depth 에러입니다. 이를 방지하려면 함수 호출을 막아 줄 기저 사례가 필요합니다. 기저 사례는 전달받은 매개변수 값이 특정 값에 도달하면 함수가 호출되는 것을 막아 줍니다. 함수 구조를 살펴보면, 보통은 호출 코드가 있는 부분으로 가지 않고 계산된 값을 반환하며 함수를 종료합니다. 팩토리얼에서 이 특정 조건은 0!=1이므로 이 조건을 기저 사례로 사용할 수 있습니다.

 

종합해 볼까요?

재귀 함수를 스택 프레임 관점에서 바라보면 상태 정보를 가지고 있는 지역 변수는 서로 다른 스택 프레임에 저장됩니다. 그렇기에 함수 내에서 자기 자신을 호출한다고 해도 같은 기능의 코드를 실행하는 것일 뿐 그 실행 결과는 서로 다른 스택 프레임에 있는 지역 변수에 저장됩니다. 이때 기저 사례를 두지 않으면 계속 호출이 일어나고 스택 프레임이 저장되는 메모리가 한정적이기 때문에 언젠가는 오류가 발생합니다.

 

재귀 함수를 설계할 때는 두 가지를 고려해야 합니다. 1) 언제 어떤 인수를 전달하여 호출할 것인지와 2) 재귀 호출을 멈추는 조건인 기저 사례를 정하는 것입니다. 재귀 함수가 스스로를 호출할 때 매개변수를 그 크기가 줄어드는 형태로 전달하여 언젠가는 반드시 기저 사례와 만나게 해야만 에러를 일으키지 않습니다.

 

 

1.3  순열을 재귀 함수로 구현하기 : 재귀 트리 사용하기

재귀 함수를 사용하는 두 번째 예로, 어떤 집합이 주어졌을 때 그 집합의 모든 순열을 구하는 프로그램을 만들어 보겠습니다. 순열(permutation)이란 순서가 있는 집합을 다른 순서로 섞는 것입니다. 예를 들어 집합 S={1, 2, 3}이 주어질 때 순서를 섞어 얻은 {2, 1, 3}은 집합 S의 한 순열입니다. 집합 S의 모든 순열로는 {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1} 가 있습니다. 집합 원소 개수가 n일 때 순열 개수는 n!입니다. 즉, S의 집합원소는 3개이기 때문에 6개의 순열이 나옵니다.

 

먼저 문제를 정의해야만 합니다. 이 절에서 해결하려고 하는 문제는 개수가 n인 집합의 모든 순열입니다. 일단 작은 크기의 문제로 나눈 후 답을 구하고 그 답을 합치면 될 것입니다.

 

permutation() 함수가 순열을 출력하는 프로그램이라고 하면 다음과 같이 표현할 수 있습니다.

 

<문제: permutation({1, 2, 3})>

- 부분 문제 1:  1을 출력 후 permutation({2, 3})

- 부분 문제 2:  2를 출력 후 permutation({1, 3})

- 부분 문제 3:  3을 출력 후 permutation({1, 2})

 

이 표현은 문제(problem)를 여러 개의 부분 문제(subproblem)로 쪼갠 후 그 해답을 구하는 과정입니다. 그림으로 나타내면 아래와 같습니다. 이를 재귀트리(recursive tree)라고 합니다.

 

 

 

재귀 트리에서 각 사각형은 스택 프레임을 의미합니다. 사각형 내부의 {}은 함수에 전달할 argument(매개변수)를 의미합니다. {} 안에 있는 원소 개수가 아래로 내려 갈수록 집합 개수가 적어지고 있습니다. 집합 크기가 계속 작아지면 결국 공집합에 도달하게 되는데, 그때가 기저 사례가 됩니다.

 

각 스택 프레임마다 집합 순서가 모두 다릅니다. 매개변수로 {1, 2, 3}을 전달받아 가장 먼저 호출되는 스택 프레임에서 그다음으로 호출되는 스택 프레임들을 살펴보면, 집합에 포함되지 않는 가장 첫 번째 숫자가 차례대로 1, 2, 3인 것을 알 수 있습니다. 순서는 상관없지만, 모든 요소가 한 번씩 꼭 포함되어야 한다는 것이 중요합니다.

 

 

집합의 원소를 차례로 첫 번째 원소와 바꾼 후 다음 스택 프레임에 전달하고, 그다음 집합의 첫 번째 요소를 집합에서 제외시킵니다. 스택 프레임이 자신이 호출한 재귀 함수를 모두 종료하고 호출한 스택 프레임으로 다시 돌아왔다면 그때는 바꾸었던 원소들을 다시 원래대로 돌려놓아야 합니다. 그래야 원소 순서가 겹치지 않고 집합을 매개변수로 한 번만 전달할 수 있습니다.

 

def permutation(arr, start):
    if len(arr) - 1 == start: #start가 마지막 원소에 도달했을 때 섞을 다른 원소가 없으므로 완성된 순열 출력
        print(arr)
        return
    
    for idx in range(start, len(arr)):
        arr[start], arr[idx] = arr[idx], arr[start]
        permutation(arr, start+1)
        arr[start], arr[idx] = arr[idx], arr[start]

if __name__ == "__main__":
    arr = [1,2,3]
    permutation(arr, 0)

 

idx로 집합의 모든 원소를 순회하면서 start와 idx의 원소를 바꾼 후 집합 크기를 줄여서(start를 한 칸 움직여서) 다시 재귀 함수를 호출합니다. 다시 자신의 스택 프레임으로 돌아왔다면 이전에 바꾸어 놓았던 원소를 다시 원래대로 돌려놓습니다.

 

 

(출처 : 파이썬으로 배우는 자료구조 핵심 원리)