재귀 관계식

재귀 관계식은 큰 경우의 값을 더 작은 경우의 값으로 정해 줍니다. 수학에서 수열을 정의하는 점화식이 이 식입니다. 알고리즘 분석에서는 자기 자신을 부르는 코드의 비용을 이 식으로 나타냅니다. 그 식을 풀어 코드의 시간 복잡도를 얻습니다.

상세

영화관 줄 맨 뒤에서 내 순번이 궁금해 앞사람에게 묻습니다. 앞사람도 모르기에 질문은 맨 앞까지 거슬러 갑니다. 맨 앞 사람이 「1번」이라고 답한 뒤로는 저마다 들은 번호에 1을 더해 뒷사람에게 넘깁니다.

줄에 셋만 서 있다면 질문과 답이 이렇게 오갑니다. 질문은 앞으로 내려갑니다. 답은 1씩 커지며 뒤로 돌아옵니다.

sequenceDiagram
    participant 나
    participant 앞사람
    participant 맨앞 as 맨 앞 사람
    나->>앞사람: 몇 번이에요?
    앞사람->>맨앞: 몇 번이에요?
    Note over 맨앞: 더 물을 사람이 없다
    맨앞-->>앞사람: 1번
    Note over 앞사람: 1 + 1 = 2
    앞사람-->>나: 2번
    Note over 나: 2 + 1 = 3

이 줄에서 순번을 정한 것은 규칙 하나와 출발점 하나입니다. 규칙은 「내 순번은 앞사람 순번에 1을 더한 값」입니다. 출발점은 「맨 앞은 1번」입니다. 앞의 규칙처럼 큰 경우의 값을 작은 경우의 값으로 나타내는 식을 재귀 관계식이라고 합니다.

이런 식이 필요한 까닭은 값을 바로 적기 어려운 것이 많아서입니다. 100번째 값은 몰라도 「99번째에서 어떻게 넘어오나」는 쉽게 말할 수 있는 경우가 흔합니다. 재귀 관계식은 그 넘어오는 규칙만으로 모든 값을 정합니다.

식을 이루는 두 부분

재귀 관계식은 규칙과 초기 조건, 두 부분으로 이루어집니다. 규칙은 큰 경우의 값을 작은 경우의 값으로 나타냅니다. 규칙을 따라 내려가면 더 작게 갈 수 없는 맨 아래 경우에 닿습니다. 이 맨 아래 경우의 값을 초기 조건이라고 부릅니다.

줄 비유에서는 「앞사람 순번에 1을 더한다」가 규칙입니다. 「맨 앞은 1번」이 초기 조건입니다.

1, 4, 7, 10 처럼 3씩 커지는 수열을 예로 봅시다. n 번째 항을 a(n) 이라고 두면 규칙은 a(n) = a(n-1) + 3 입니다. 초기 조건은 a(1) = 1 입니다.

규칙만 있고 초기 조건이 없으면 값이 하나로 안 정해집니다. a(n) = a(n-1) + 3 은 2, 5, 8 에도 맞고 0, 3, 6 에도 맞습니다. 초기 조건이 그중 어느 수열인지를 고릅니다.

재귀 코드에서는 더 부르지 않고 바로 답을 돌려주는 경우가 초기 조건에 해당합니다. 이 경우를 기저 사례라고 부릅니다. 기저 사례가 없는 재귀 코드는 끝없이 자기 자신을 부르다 호출 스택이 넘칩니다.

수열을 정하는 점화식

수학에서는 재귀 관계식을 점화식이라고 부릅니다. 수열의 항을 앞 항 몇 개로 정하는 식입니다.

가장 잘 알려진 예가 피보나치 수열입니다. 규칙은 F(n) = F(n-1) + F(n-2) 입니다. 초기 조건은 F(0) = 0, F(1) = 1 입니다. 그래서 수열은 0, 1, 1, 2, 3, 5, 8, 13 으로 이어집니다.

점화식으로 정한 수열은 앞에서부터 차례로 계산해 나가면 됩니다. 대신 100번째 항을 한 번에 알려면 n 만 넣어 값을 내는 식이 따로 필요합니다. 이런 식을 닫힌 꼴이라고 합니다. 3씩 커지는 수열의 닫힌 꼴은 a(n) = 3n - 2 입니다.

「재귀 관계식을 푼다」는 말은 이 닫힌 꼴을 찾는다는 뜻입니다. 알고리즘 분석에서는 정확한 닫힌 꼴 대신 자라는 꼴만 찾는 경우가 많습니다.

재귀 코드의 비용을 나타내는 식

알고리즘 분석에서 재귀 관계식은 코드의 비용을 나타냅니다. 반복문은 몇 번 도는지 세면 비용이 나옵니다. 자기 자신을 부르는 재귀 코드는 그렇게 세기 어렵습니다. 호출 하나가 다른 호출을 낳고, 그 호출이 또 호출을 낳기 때문입니다.

그래서 비용을 더 작은 입력의 비용으로 나타냅니다. 입력 크기가 n 일 때 드는 시간을 T(n) 이라고 둡니다. T(n) 은 「더 작은 입력에 드는 시간」과 「이번 호출이 직접 하는 일」의 합입니다.

목록 n 개를 더하는 재귀 함수를 봅시다. 이 함수는 맨 앞 값 하나를 꺼내 나머지 n-1 개의 합에 더합니다. 꺼내고 더하는 일은 목록 길이와 상관없이 정해진 만큼 걸립니다. 그 시간을 c 라고 두면 T(n) = T(n-1) + c 입니다.

이 식은 「한 번 부를 때마다 c 만큼 일하고 크기가 하나 줄어든다」는 뜻입니다. 크기가 0 이 될 때까지 n 번 부르므로 전체는 c 를 n 번 더한 값입니다. 이렇게 비용이 n 에 비례해 자라는 것을 Θ(n) 이라고 씁니다. Θ 는 「이 꼴로 자란다」를 뜻하는 빅세타 표기법입니다.

답의 식과 비용의 식

같은 코드에 재귀 관계식이 둘 붙기도 합니다. 코드가 내는 답의 식과 코드에 드는 비용의 식입니다. 피보나치 수를 정의대로 재귀로 짠 코드가 대표적인 예입니다.

아래 코드는 fib 가 몇 번 불렸는지를 calls 에 셉니다.

calls = 0

def fib(n):
    global calls
    calls += 1
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

fib(10)   # 55
calls     # 177

답 55 는 점화식 F(n) = F(n-1) + F(n-2) 를 따릅니다. 불린 횟수 177 은 다른 식을 따릅니다. fib(n) 하나를 부르면 일어나는 호출의 총수를 C(n) 이라고 두면 C(n) = C(n-1) + C(n-2) + 1 입니다.

식의 앞 두 항은 fib(n) 이 부른 fib(n-1) 과 fib(n-2) 가 저마다 일으키는 호출 수입니다. 끝의 + 1 은 fib(n) 자기 자신을 센 몫입니다.

fib(4) 하나를 부르면 호출이 아래처럼 갈라집니다. 칸 하나가 호출 하나입니다.

flowchart TD
    A["fib(4)"] --> B["fib(3)"]
    A --> C["fib(2)"]
    B --> D["fib(2)"]
    B --> E["fib(1)"]
    D --> F["fib(1)"]
    D --> G["fib(0)"]
    C --> H["fib(1)"]
    C --> I["fib(0)"]

칸이 아홉 개이니 C(4) = 9 입니다. fib(2) 가 두 번 나오는 데서 보듯 같은 값을 여러 번 다시 계산합니다.

C(n) 은 F(n) 처럼 앞 두 항을 더하므로 비슷한 속도로 불어납니다. n 이 하나 늘 때마다 호출이 1.6배쯤 늡니다. fib(30) 하나에 호출이 약 269만 번 일어납니다.

비용 식을 보면 고칠 곳도 보입니다. 같은 n 의 답을 한 번만 계산해 두고 다시 쓰면, 새로 계산하는 횟수가 n 번 남짓으로 줄어 Θ(n) 이 됩니다. 계산한 답을 저장해 다시 쓰는 이 기법이 메모이제이션입니다.

같은 fib(4) 를 메모이제이션으로 부르면 호출이 아래처럼 줄어듭니다. 이미 계산한 값을 다시 만나면 저장해 둔 값을 꺼내고 더 내려가지 않습니다.

flowchart TD
    A["fib(4)"] --> B["fib(3)"]
    A --> C["fib(2) · 저장해 둔 값을 꺼냄"]
    B --> D["fib(2)"]
    B --> E["fib(1)"]
    D --> F["fib(1)"]
    D --> G["fib(0)"]

오른쪽 fib(2) 아래의 두 칸이 잘려 나가 칸이 아홉에서 일곱으로 줄었습니다. n 이 커질수록 잘려 나가는 가지가 많아져 칸 수가 n 에 비례해서만 늡니다.

답의 점화식을 먼저 세우고 작은 답부터 채워 가는 설계 방법이 동적 계획법입니다. 코딩 테스트에서 「점화식을 세운다」고 할 때 가리키는 것이 이 답의 식입니다. 시간 복잡도를 따질 때 세우는 식은 비용의 식입니다.

줄어드는 방식에 따른 두 식

재귀 관계식은 입력이 어떻게 줄어드는지로 크게 갈립니다. 하나씩 빼 가며 줄어드는 빼는 식과 반씩 나눠 가며 줄어드는 나누는 식입니다. 호출마다 하는 일이 같아도 두 식은 결과가 크게 다릅니다.

빼는 식은 T(n) = T(n-1) + c 처럼 생깁니다. 크기가 하나씩 줄므로 바닥까지 n 번 내려갑니다. 앞의 목록 합이 이 식입니다. 답은 Θ(n) 입니다.

나누는 식은 T(n) = T(n/2) + c 처럼 생깁니다. 바닥까지 내려가는 횟수는 n 을 반으로 몇 번 접어야 1 이 되느냐입니다. 그 횟수가 log₂ n 입니다. 1,024 개면 10 번입니다.

정렬된 배열에서 가운데를 보고 한쪽을 버리는 이진 탐색이 이 나누는 식입니다. 답은 Θ(log n) 입니다.

크기 1,024 에서 출발하면 두 식이 바닥까지 가는 길이가 이만큼 다릅니다.

flowchart TD
    subgraph S1["빼는 식 · 1,024 번"]
        a1["1024"] --> a2["1023"] --> a3["1022"] --> a4["…"] --> a5["0"]
    end
    subgraph S2["나누는 식 · 10 번"]
        b1["1024"] --> b2["512"] --> b3["256"] --> b4["…"] --> b5["1"]
    end
    a5 ~~~ b1

나눈 조각을 여럿 부르는 식도 있습니다. 병합 정렬은 반쪽 둘을 각각 정렬한 뒤 합칩니다. 합치는 데 n 에 비례하는 시간이 들므로 T(n) = 2T(n/2) + n 입니다. 문제를 쪼개 푸는 분할 정복 알고리즘이 대개 이런 식을 남깁니다.

자주 만나는 식과 답을 아래 표에 모았습니다. 왼쪽 식으로 어떤 코드인지 알아봅니다. 얼마나 걸리는지는 오른쪽에서 읽습니다.

표에서 눈여겨볼 것은 호출이 둘로 갈라지는 두 줄입니다. 빼는 식인 2T(n-1) + c 는 지수 꼴로 불어납니다. 나누는 식인 2T(n/2) + n 은 n log n 에 머뭅니다. 두 식을 층마다 그려 보면 까닭이 보입니다.

아래 두 그림에서 칸 하나가 호출 하나입니다. 칸 안의 값은 그 호출이 맡은 크기입니다. 먼저 병합 정렬의 T(n) = 2T(n/2) + n 입니다. 크기 m 짜리 호출은 합치는 데 m 만큼 일하므로 칸의 값이 곧 그 칸의 일입니다.

flowchart TD
    subgraph L1["층 1 · 일의 합 n"]
        A["n"]
    end
    subgraph L2["층 2 · 일의 합 n"]
        B1["n/2"]
        B2["n/2"]
    end
    subgraph L3["층 3 · 일의 합 n"]
        C1["n/4"]
        C2["n/4"]
        C3["n/4"]
        C4["n/4"]
    end
    A --> B1
    A --> B2
    B1 --> C1
    B1 --> C2
    B2 --> C3
    B2 --> C4
    C1 & C2 & C3 & C4 --> D["…"]
    D --> E["맨 아래 층 · 크기 1 칸이 n 개<br/>일의 합 n"]
    E --> F["층이 log₂ n 개 남짓<br/>전체 n log n"]

층마다 칸이 두 배로 늘지만 칸의 크기는 반으로 줍니다. 그래서 층마다 일의 합이 n 으로 같습니다. 층이 log₂ n 개 남짓이니 전체는 n log n 입니다.

다음은 하노이의 탑의 T(n) = 2T(n-1) + c 입니다. 이 식에서 칸마다 하는 일은 크기와 상관없이 c 입니다.

flowchart TD
    subgraph L1["층 1 · 일의 합 c"]
        A["n"]
    end
    subgraph L2["층 2 · 일의 합 2c"]
        B1["n-1"]
        B2["n-1"]
    end
    subgraph L3["층 3 · 일의 합 4c"]
        C1["n-2"]
        C2["n-2"]
        C3["n-2"]
        C4["n-2"]
    end
    A --> B1
    A --> B2
    B1 --> C1
    B1 --> C2
    B2 --> C3
    B2 --> C4
    C1 & C2 & C3 & C4 --> D["…"]
    D --> E["맨 아래 층 · 크기 1 칸이 2ⁿ⁻¹ 개<br/>일의 합 2ⁿ⁻¹c"]
    E --> F["층이 n 개<br/>전체 약 2ⁿ c"]

여기서도 층마다 칸이 두 배로 늡니다. 그런데 크기가 하나씩만 줄어서 층이 n 개나 쌓입니다. 맨 아래 층 하나에만 칸이 2ⁿ⁻¹ 개라 전체가 2ⁿ 꼴로 불어납니다.

식을 푸는 방법

식을 세웠으면 풀어야 답이 나옵니다. 이 소절은 표의 T(n) = T(n-1) + n 을 손으로 펼쳐 풉니다. 이어서 손으로 풀기 번거로울 때 쓰는 도구 셋을 짚습니다.

가장 손쉬운 방법은 식을 자기 자신에 거듭 넣어 펼치는 것입니다. T(n-1) 대신 T(n-2) + (n-1) 을 넣습니다. 같은 일을 바닥까지 되풀이합니다.

T(n) = T(n-1) + n
     = T(n-2) + (n-1) + n
     = T(n-3) + (n-2) + (n-1) + n
     …
     = T(1) + 2 + 3 + … + n

맨 아래 줄의 합 2 + 3 + … + n 은 n(n+1)/2 - 1 입니다. T(1) 은 정해진 값입니다. 가장 크게 자라는 항이 n²/2 이므로 답은 Θ(n²) 입니다.

펼치기가 길어지는 식에는 그림이 낫습니다. 호출 하나를 칸 하나로 그리고 칸마다 직접 하는 일을 써 넣은 뒤, 층마다 합을 더합니다. 이 그림이 재귀 트리입니다. 앞의 fib(4) 그림과 두 식을 층마다 그린 그림이 모두 재귀 트리입니다.

T(n) = aT(n/b) + f(n) 모양의 식에는 공식이 있습니다. 호출 하나가 크기 n/b 짜리 조각 a 개를 부릅니다. 그 호출이 직접 하는 일은 f(n) 입니다.

병합 정렬에 대어 보면 반쪽 둘을 부르므로 a = 2, b = 2 입니다. f(n) 은 반쪽 둘을 합치는 일 n 입니다.

마스터 정리는 재귀 트리의 맨 위 층과 맨 아래 층을 견줍니다. 맨 위는 첫 호출이 직접 하는 일 f(n) 입니다. 맨 아래는 크기 1 까지 내려간 조각들이 하는 일의 합입니다. 둘 중 어느 쪽이 더 빨리 자라나로 답이 정해집니다.

맨 위가 뚜렷하게 더 빨리 자라면 답은 f(n) 꼴입니다. 맨 아래가 뚜렷하게 더 빨리 자라면 맨 아래 일의 합이 답입니다. 둘이 같은 꼴로 자라면 그 꼴에 log n 을 곱합니다. 앞의 그림에서 병합 정렬은 맨 위도 n, 맨 아래도 n 이라 답이 n log n 입니다.

답을 미리 짐작할 수 있으면 짐작이 맞는지 증명하는 길도 있습니다. 「T(n) 은 n² 꼴을 넘지 않는다」고 짐작한 뒤 수학적 귀납법으로 확인합니다. 이 방법을 치환법이라고 부릅니다.

쓰는 경우와 한계

이 식은 코드가 자기 자신을 부를 때 꺼냅니다. 반복문만 있는 코드는 몇 번 도는지 세면 끝나므로 식이 필요 없습니다. 병합 정렬 같은 분할 정복 알고리즘과 이진 탐색이 이 식으로 비용을 따지는 대표적인 코드입니다.

모든 식이 공식 하나로 풀리지는 않습니다. 마스터 정리는 크기가 n/b 처럼 나눠서 줄 때만 쓸 수 있습니다. 하노이의 탑처럼 n-1 로 빼서 주는 식에는 맞지 않습니다. 조각 크기가 n/3 과 2n/3 처럼 고르지 않은 식도 재귀 트리로 따로 풉니다.

식은 비용의 꼴을 줄 뿐 실제 시간을 주지는 않습니다. 상수 c 와 초기 조건의 값은 대개 꼴을 바꾸지 않아서 풀이 중에 버립니다. 그래서 같은 Θ(n log n) 끼리는 이 식만으로 어느 쪽이 덜 걸리는지 가릴 수 없습니다.

수학의 점화식과는 이 점이 다릅니다. 수열에서는 초기 조건이 바뀌면 모든 항이 바뀝니다. 비용 분석에서는 맨 아래 호출이 1 이 걸리든 5 가 걸리든 자라는 꼴은 대개 같습니다.

관련 항목

재귀 관계식을 푸는 방법

재귀 트리 · 마스터 정리 · 치환법 · 반복 대입법 · 수학적 귀납법 · 생성 함수 · 특성 방정식

재귀 관계식으로 비용을 적는 코드 구조

재귀 · 기저 사례 · 호출 스택 · 꼬리 재귀 · 분할 정복 · 재귀 백트래킹

재귀 관계식으로 비용을 분석하는 알고리즘

병합 정렬 · 퀵 정렬 · 이진 탐색 · 하노이의 탑 · 카라츠바 알고리즘 · 스트라센 알고리즘 · 선택 정렬

재귀 관계식을 풀어 얻는 비용 지표와 표기법

점근 분석 · 시간 복잡도 · 공간 복잡도 · 점근 표기법 · 빅오 표기법 · 빅세타 표기법 · 빅오메가 표기법

재귀 관계식으로 정의하는 수열

수열 · 피보나치 수열 · 등차수열 · 등비수열 · 카탈랑 수 · 황금비 · 닫힌 꼴

재귀 관계식의 중복 계산을 줄이는 기법

메모이제이션 · 동적 계획법 · 타뷸레이션 · 부분 문제 · 최적 부분 구조