재귀·기저 사례·호출 스택

컴퓨터의 폴더 안에는 파일과 함께 다른 폴더가 들어 있고, 그 폴더 안에 또 폴더가 들어 있을 수 있습니다. 폴더 하나의 전체 크기를 구하려면 그 안의 파일 크기를 더하고, 안에 든 폴더마다 "그 폴더의 전체 크기"를 구해 더해야 합니다. 큰 문제를 풀기 위해 같은 모양의 작은 문제를 푸는 셈입니다. 이렇게 함수가 자기 자신을 다시 부르는 방식을 재귀(recursion)라고 합니다. 이 글에서는 재귀 함수를 만들 때 꼭 필요한 두 부분을 익히고, 컴퓨터가 재귀 호출을 어떻게 기억했다가 되돌아오는지 호출 스택으로 추적합니다. 이어지는 병합 정렬과 퀵 정렬은 모두 이 재귀 위에 만들어집니다.

같은 모양의 작은 문제로 나누기

팩토리얼(factorial) n!은 1부터 n까지의 정수를 모두 곱한 값입니다. 4! = 4 × 3 × 2 × 1 = 24이고, 0!은 1로 정합니다. 4!을 잘 보면 4 × (3 × 2 × 1), 곧 4 × 3!입니다. 일반적으로 n이 1 이상이면 n! = n × (n - 1)!이 성립하므로, n!을 구하는 문제는 (n - 1)!을 구하는 작은 문제로 바뀝니다.

이 관계를 그대로 코드로 옮기면 다음과 같습니다. factorial(n)은 factorial(n - 1)의 답에 n을 곱해 돌려줍니다.

def factorial(n):
    if n < 0:
        raise ValueError("n은 0 이상이어야 합니다")
    if n <= 1:
        return 1
    return n * factorial(n - 1)


print(factorial(3))
print(factorial(0))
try:
    factorial(-1)
except ValueError as error:
    print("오류:", error)

6
1
오류: n은 0 이상이어야 합니다

재귀 함수는 두 부분으로 이루어집니다. n <= 1일 때처럼 더 나누지 않고 바로 답을 돌려주는 입력을 기저 사례(base case)라 하고, n * factorial(n - 1)처럼 더 작은 입력으로 자기 자신을 부르는 부분을 재귀 단계(recursive case)라고 합니다. 음수 입력은 팩토리얼이 정의되지 않으므로 ValueError로 거절합니다. raise는 오류를 일으키는 문장이고, try와 except는 그 오류를 받아 처리하는 문장입니다.

기저 사례가 없으면

기저 사례를 빼먹으면 어떻게 될까요? 아래 코드는 n이 얼마든 무조건 factorial(n - 1)을 부릅니다.

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


print(factorial(3))

Traceback (most recent call last):
  File "C:\algo\lesson.py", line 5, in <module>
    print(factorial(3))
          ~~~~~~~~~^^^
  File "C:\algo\lesson.py", line 2, in factorial
    return n * factorial(n - 1)
               ~~~~~~~~~^^^^^^^
  File "C:\algo\lesson.py", line 2, in factorial
    return n * factorial(n - 1)
               ~~~~~~~~~^^^^^^^
  File "C:\algo\lesson.py", line 2, in factorial
    return n * factorial(n - 1)
               ~~~~~~~~~^^^^^^^
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

factorial(3)이 factorial(2)를, 그것이 factorial(1), factorial(0), factorial(-1)을 부르며 멈추지 않고 내려갑니다. Python은 아직 끝나지 않은 호출이 너무 많이 쌓이면 RecursionError를 내고 프로그램을 멈춥니다. 오류 메시지의 [Previous line repeated 996 more times]는 같은 줄의 호출이 996번 더 반복되었다는 뜻입니다. 기저 사례는 재귀가 언젠가 멈추게 하는 장치이므로, 재귀 함수를 만들 때는 이것부터 정하는 것이 좋습니다.

호출 스택이 기다리는 계산을 기억한다

factorial(3)은 3 * factorial(2)를 계산하려는 도중에 factorial(2)를 부릅니다. 곱셈을 끝내려면 factorial(2)의 답이 필요하므로, factorial(3)은 그 답이 돌아올 때까지 기다려야 합니다. 이때 컴퓨터는 factorial(3)의 상태, 곧 n이 3이라는 것과 돌아와서 곱셈을 이어서 해야 한다는 것을 기억해 둡니다. 함수 호출 하나의 이런 상태를 프레임(frame)이라 하고, 프레임들을 쌓아 두는 곳을 호출 스택(call stack)이라고 합니다.

스택(stack)은 접시를 쌓듯 마지막에 넣은 것을 가장 먼저 꺼내는 구조입니다. 새 호출이 시작되면 그 프레임이 맨 위에 쌓이고, 호출이 끝나면 맨 위의 프레임이 빠지면서 바로 아래에서 기다리던 호출이 계산을 이어 갑니다. 아래 그림은 factorial(3)의 프레임이 쌓였다가 빠지는 과정입니다.

호출 순서와 반환 순서를 눈으로 보려면 호출할 때와 돌아올 때 각각 출력하게 하면 됩니다. 아래 코드의 depth는 호출의 깊이로, 깊을수록 출력을 오른쪽으로 들여 씁니다.

def factorial(n, depth=0):
    print("  " * depth + f"factorial({n}) 호출")
    if n <= 1:
        result = 1
    else:
        result = n * factorial(n - 1, depth + 1)
    print("  " * depth + f"factorial({n}) = {result} 반환")
    return result


factorial(3)

factorial(3) 호출
  factorial(2) 호출
    factorial(1) 호출
    factorial(1) = 1 반환
  factorial(2) = 2 반환
factorial(3) = 6 반환

호출은 3, 2, 1 순서로 내려가고, 반환은 1, 2, 6 순서로 올라옵니다. factorial(3)의 "반환" 줄이 가장 마지막에 나오는 것은, 이 호출이 가장 먼저 시작했지만 아래의 모든 호출이 끝날 때까지 기다렸기 때문입니다. 각 프레임은 자기만의 n을 가지고 있어서, factorial(1)이 실행되는 동안에도 아래 프레임들의 n인 2와 3은 그대로 남아 있습니다. 재귀 호출 뒤에 있는 문장은 호출한 작은 문제가 답을 돌려준 뒤에야 실행된다는 점이 재귀를 읽을 때 가장 중요합니다.

왜 맞고 왜 끝나는가

재귀 함수가 맞는다는 것은 이산수학의 수학적 귀납법과 불변식에서 다루는 수학적 귀납법(mathematical induction)과 같은 방식으로 보입니다. 먼저 기저 사례인 n = 0과 n = 1에서 1을 돌려주는 것은 정의대로입니다. 다음으로 n이 2 이상일 때, factorial(n - 1)이 (n - 1)!을 바르게 돌려준다고 가정하면 n * factorial(n - 1)은 n × (n - 1)! = n!이므로 factorial(n)도 맞습니다. 이 두 가지가 성립하면 0, 1에서 맞고, 그래서 2에서 맞고, 그래서 3에서 맞는 식으로 모든 음이 아닌 정수에서 맞습니다.

이 논리 덕분에 재귀 함수를 만들 때는 작은 문제의 호출이 어떻게 실행되는지 끝까지 따라가지 않아도 됩니다. 작은 입력에 대한 호출이 맞는 답을 돌려준다고 믿고, 그 답으로 현재 문제를 푸는 방법만 바르게 만들면 됩니다. 단, 그 믿음이 정당하려면 호출할 때마다 입력이 기저 사례 쪽으로 줄어들어야 합니다. factorial은 호출마다 n이 1씩 줄어 늦어도 n = 1에서 멈추고, 음수는 처음부터 거절하므로 언제나 끝납니다.

재귀가 자연스러운 문제

팩토리얼은 반복문으로도 쉽게 계산할 수 있어서, 재귀를 꼭 써야 하는 예는 아닙니다. 재귀가 진가를 보이는 것은 처음에 든 폴더처럼 구조 안에 같은 구조가 몇 겹으로 들어 있는지 미리 알 수 없을 때입니다. 아래 함수는 리스트 안에 리스트가 들어 있을 수 있는 중첩 리스트에서 모든 수의 합을 구합니다.

def total(items):
    result = 0
    for item in items:
        if isinstance(item, list):
            result += total(item)
        else:
            result += item
    return result


print(total([1, [2, 3], [4, [5, 6]], 7]))

28

isinstance(item, list)는 item이 리스트인지 확인합니다. 원소가 수이면 그대로 더하고, 리스트이면 그 리스트의 합을 같은 함수로 구해 더합니다. 리스트가 몇 겹이든 각 호출은 자기 리스트 한 겹만 처리하면 되므로 코드가 짧습니다. 여기서 기저 사례는 안에 리스트가 없는 리스트로, 이때는 재귀 호출 없이 반복문만으로 합을 돌려줍니다. 같은 일을 반복문만으로 하려면 아직 처리하지 않은 리스트들을 직접 쌓아 두고 관리해야 하는데, 재귀는 그 일을 호출 스택에 맡깁니다. 스택과 깊이 우선 탐색 DFS에서 이 관계를 다시 봅니다.

비용과 재귀 깊이의 한계

factorial(n)은 호출을 n번 하고 곱셈을 n - 1번 하므로 O(n)번의 연산을 하며, 호출 스택에도 프레임이 많을 때 n개까지 쌓여 O(n)의 공간을 씁니다. 다만 n!은 매우 빨리 커져서 1000!은 2568자리 수입니다. 이런 큰 정수의 곱셈은 한 번에 끝나는 기본 연산이 아니라 자릿수가 많을수록 오래 걸리므로, 곱셈 횟수와 실제 시간은 구분해서 생각해야 합니다.

Python은 호출 스택이 한없이 커지지 않도록 쌓을 수 있는 호출의 개수를 제한합니다. 기본 한도는 1000이며 sys.getrecursionlimit()으로 확인할 수 있습니다. 그래서 위의 factorial로 factorial(5000)을 계산하면, 기저 사례가 있어도 도착하기 전에 RecursionError가 납니다. 깊이가 입력 크기에 비례해 커지는 재귀라면 큰 입력에서는 반복문으로 바꾸는 편이 안전합니다. 팩토리얼은 반복문으로 바로 바꿀 수 있고, 표준 라이브러리의 math.factorial을 써도 됩니다.

더 깊이: 꼬리 재귀와 Python

factorial의 마지막 문장 n * factorial(n - 1)은 재귀 호출이 끝난 뒤에 곱셈이 남아 있어서 프레임을 지울 수 없습니다. 반면 재귀 호출의 결과를 아무 계산 없이 그대로 돌려주는 형태를 꼬리 재귀(tail recursion)라고 합니다. 예를 들어 지금까지의 곱을 acc라는 매개변수로 넘기면 return factorial_acc(n - 1, acc * n)처럼 쓸 수 있습니다. 일부 언어는 꼬리 재귀를 반복문처럼 실행해 프레임을 쌓지 않는데, 이것을 꼬리 호출 최적화(tail call optimization)라고 합니다.

CPython은 이 최적화를 하지 않습니다. 프레임을 지우면 오류가 났을 때 Traceback에 호출 과정이 남지 않아 디버깅이 어려워진다는 것이 Python을 만든 Guido van Rossum이 밝힌 이유 가운데 하나입니다. 그래서 Python에서는 꼬리 재귀로 고쳐 써도 깊이 한도가 그대로이고, 깊은 재귀가 필요하면 반복문으로 바꾸는 것이 일반적입니다.

정리

• 재귀는 함수가 같은 모양의 더 작은 문제로 자기 자신을 부르는 방식이며, 바로 답을 내는 기저 사례와 작은 입력으로 자신을 부르는 재귀 단계로 이루어집니다.
• 기저 사례가 없거나 입력이 기저 사례 쪽으로 줄지 않으면 호출이 끝없이 쌓여 RecursionError가 납니다.
• 호출이 시작될 때마다 그 호출의 상태를 담은 프레임이 호출 스택에 쌓이고, 호출이 끝나면 빠집니다. 호출은 큰 문제부터 내려가고 반환은 작은 문제부터 올라옵니다.
• 재귀 함수의 정확성은 수학적 귀납법처럼 기저 사례가 맞고, 작은 문제의 답이 맞으면 큰 문제의 답도 맞음을 보여서 설명합니다.
• Python의 재귀 깊이 기본 한도는 1000이고 꼬리 호출 최적화가 없으므로, 깊이가 입력에 비례하는 재귀는 큰 입력에서 반복문으로 바꿉니다.

연습 문제

1. factorial(4) 추적하기

factorial(4)를 실행할 때 각 호출이 기다리는 계산과 돌려주는 값을 호출 순서대로 쓰세요.

2. 기저 사례를 n == 1로만 두면

본문의 factorial에서 if n <= 1:을 if n == 1:로 바꾸면 factorial(0)은 어떻게 될까요? 음수 검사가 없는 경우도 생각해 보세요.

3. 자릿수의 합을 재귀로 구하기

음이 아닌 정수 n의 각 자릿수를 더한 값을 돌려주는 재귀 함수 digit_sum(n)을 만드세요. 예를 들어 digit_sum(1234)는 1 + 2 + 3 + 4 = 10입니다. 기저 사례와 재귀 단계를 무엇으로 정하면 될까요?

def digit_sum(n):
    if n < 10:
        return n
    return n % 10 + digit_sum(n // 10)


print(digit_sum(1234), digit_sum(7), digit_sum(0))

10 7 0

다음 글 병합 정렬의 분할과 합치기에서는 리스트를 반으로 나누어 각각을 재귀로 정렬한 뒤 하나로 합치는 정렬을 만듭니다.