재귀와 점화식 - 반복 구조를 식으로

이 장에서 배우는 것

반복되는 작업을 설명할 때 “작은 작업을 먼저 끝낸 뒤 그 결과를 합친다”라는 말이 자주 등장한다. 폴더 안의 폴더를 처리하거나, 긴 자료를 나누어 계산하거나, 앞서 계산한 값으로 다음 값을 만드는 상황이 그렇다. 이번에는 이런 설명을 식과 코드로 옮긴다. 앞 장에서 다룬 나머지 계산이 수의 반복 패턴을 드러냈다면, 여기서는 작업 자체의 반복 구조를 살펴본다.

핵심은 함수가 자기 자신을 부른다는 문법보다 무엇이 작아지고 어디서 멈추는지를 찾는 데 있다. 같은 값을 계산하는 코드라도 실제 호출 횟수는 크게 달라질 수 있다. 작은 입력에 대해 값과 호출 횟수를 함께 출력하면 그 차이를 직접 확인할 수 있다.

• 문장의 반복 구조에서 처음 값과 다음 값을 정하는 점화식을 만든다.
• 피보나치와 하노이에서 결과값과 재귀 호출 횟수를 구별한다.
• 문제를 반으로 나누었을 때 전체 작업량이 어떻게 쌓이는지 확인한다.
• 이미 구한 값을 보관하는 메모이제이션을 구현하고 호출 수를 비교한다.
• 점화식 값과 호출 수를 출력하는 하나의 프로그램을 완성한다.

문제 상황

여러 자료 묶음의 처리 비용을 미리 계산하는 도구를 만든다고 하자. 묶음의 크기가 n일 때 처리 규칙은 다음과 같다. 크기가 1이면 추가 작업이 없다. 크기가 2 이상이면 두 묶음으로 나누어 각각 처리한 뒤, 전체 원소 수만큼 확인 작업을 한다. 크기가 8인 묶음은 크기 4 두 개로, 크기 4는 크기 2 두 개로 나뉜다.

처음에는 “반으로 나누니까 금방 끝난다”라고 생각할 수 있다. 그러나 반으로 나눈 두 묶음을 모두 처리해야 한다. 한쪽 작업이 작아져도 처리할 묶음의 개수는 늘어난다. 따라서 한 번에 다루는 크기만 보고 전체 비용을 판단하면 잘못된 예측을 한다.

또 다른 동료는 같은 크기에 대한 예상값을 여러 곳에서 반복 계산한다. 이 경우에는 계산을 나누는 방식뿐 아니라 이미 얻은 값을 다시 계산하는지도 살펴야 한다. 이번 장의 완성 프로그램은 이런 판단을 위한 작은 실험 도구다. 실행 시간 대신 호출 횟수를 세므로 실행하는 기기의 성능에 영향을 덜 받고 결과가 일정하다.

작은 문제와 처음 값으로 점화식 세우기

점화식(recurrence relation)은 어떤 항의 값을 다른 항의 값으로 정하는 식이다. 여기서 항은 번호가 붙은 값 하나를 뜻한다. 번호 n에 해당하는 값을 A(n)처럼 적는다. 전공 수업에서는 번호 순서대로 놓인 값들을 수열이라 부른다. 점화식은 그 수열을 만드는 규칙을 표현한다.

예를 들어 빈 작업 목록을 만드는 비용이 2이고, 작업 하나를 추가할 때마다 비용이 3씩 늘어난다고 하자. 처음 값은 A(0) = 2이고, 나머지는 A(n) = A(n - 1) + 3이다. A(1)은 5, A(2)는 8이다. 다음 코드는 이 규칙을 그대로 실행한다.

def cost(n):
    if n == 0:
        return 2
    return cost(n - 1) + 3

assert [cost(n) for n in range(4)] == [2, 5, 8, 11]

재귀(recursion)는 함수가 자기 자신을 다시 호출하여 문제를 푸는 방식이다. 전공 수업에서는 더 작은 문제의 결과를 이용해 현재 문제를 해결하는 재귀적 정의와 함께 다룬다. 위 코드는 cost(3)을 구하려고 cost(2)를 부르고, 다시 cost(1), cost(0)을 부른다. cost(0)이 2를 돌려주면 기다리던 계산이 거꾸로 마무리된다.

여기서 n은 0 이상의 정수로 제한한다. n이 음수이면 n - 1은 0에서 더 멀어진다. 함수 안에 멈추는 조건을 적었다는 사실만으로 종료가 보장되지는 않는다. 허용하는 입력과, 호출할 때 작아지는 양과, 실제로 도달할 멈춤 조건을 함께 정해야 한다. 멈춤 조건에 해당하는 경우를 기저 사례(base case)라고 부른다.

점화식을 코드로 옮기기 전에 결정할 세 가지

결정할 것	비용 예제	코드에서 확인할 곳
입력 범위	n은 0 이상의 정수	함수에 전달하는 값
처음 값	A(0) = 2	if n == 0
작아지는 관계	A(n) = A(n - 1) + 3	cost(n - 1)

처음 값이 빠지면 같은 점화식으로 서로 다른 수열을 만들 수 있다. A(0)을 20으로 바꾸면 A(1)은 23이다. “이전 값에 3을 더한다”라는 규칙만으로는 원하는 결과를 정할 수 없다는 작은 반례다.

피보나치: 값 하나에 호출은 몇 번 필요한가

피보나치 수열은 두 앞선 값을 더해 다음 값을 만든다. 이 장에서는 F(0) = 0, F(1) = 1로 정하고, n이 2 이상이면 F(n) = F(n - 1) + F(n - 2)로 정한다. 처음 몇 값은 0, 1, 1, 2, 3, 5, 8이다. 이 규칙은 재귀 코드로 바로 옮길 수 있지만, 코드를 짧게 쓸 수 있다는 사실과 계산량이 적다는 사실은 별개다.

그림에서 F(4)는 F(3)과 F(2)를 요구한다. F(3)도 F(2)를 요구하므로 F(2)를 두 번 계산한다. F(2)가 필요로 하는 F(1)과 F(0)도 그때마다 다시 호출한다. 같은 입력이 여러 경로로 나타나는 것이다.

함수에 들어온 횟수를 C(n)으로 두자. 처음 실행한 호출도 세고, 기저 사례에 들어간 호출도 센다. 그러면 C(0) = C(1) = 1이다. n이 2 이상일 때는 C(n) = 1 + C(n - 1) + C(n - 2)다. 맨 앞의 1은 현재 호출 자신의 몫이다. F(n)은 결과값이고 C(n)은 그 값을 구하는 과정의 호출 수다. 둘은 서로 다른 질문에 답한다.

예를 들어 F(4)는 3이지만 C(4)는 9다. 재귀식에 등장하는 덧셈이 비슷하다고 결과값과 호출 수를 같은 수열로 취급하면 이 작은 입력부터 맞지 않는다. 완성 코드에서는 호출할 때마다 목록에 표시를 하나 추가하고 그 길이를 세어 C(n)을 확인한다.

하노이: 두 번의 작은 작업 사이에 한 번의 이동

하노이는 크기가 다른 원판을 세 기둥 사이에서 옮기는 문제다. 한 번에 맨 위 원판 하나만 옮기고, 큰 원판을 작은 원판 위에 놓지 않는다. 한 기둥에 쌓인 n개 원판을 다른 기둥으로 옮기려면 위의 n - 1개를 보조 기둥에 옮기고, 가장 큰 원판을 목적지로 옮긴 뒤, 보조 기둥의 n - 1개를 목적지로 옮기는 절차를 쓸 수 있다.

이 절차의 이동 수를 H(n)이라고 하자. 원판이 없으면 H(0) = 0이다. 원판이 있으면 H(n) = 2 × H(n - 1) + 1이다. 실제 이동 명령을 만들지 않고도 이 식으로 이동 수를 계산할 수 있다. H(1), H(2), H(3)은 각각 1, 3, 7이다.

다음 코드는 원판 3개를 실제로 옮긴다. 목록의 마지막 원소를 기둥의 맨 위로 정한다. pop은 마지막 원소를 꺼내면서 목록에서 제거하는 연산이다. 각 이동 전에 목적지의 맨 위 원판과 크기를 비교하므로 규칙을 어긴 이동도 확인할 수 있다.

def move(n, source, target, spare, moves):
    if n == 0:
        return
    move(n - 1, source, spare, target, moves)
    disk = source.pop()
    assert not target or target[-1] > disk
    target.append(disk)
    moves.append(disk)
    move(n - 1, spare, target, source, moves)

source = [3, 2, 1]
target = []
moves = []
move(3, source, target, [], moves)
assert source == []
assert target == [3, 2, 1]
assert len(moves) == 7

이 코드가 실행한 이동 수는 H(3)과 같다. 그러나 n = 0인 호출에서는 이동하지 않고 돌아간다. 따라서 이동 수가 곧 호출 수는 아니다. 같은 절차의 호출 수를 D(n)으로 쓰면 D(0) = 1, D(n) = 1 + 2 × D(n - 1)이다. H(3)은 7이지만 D(3)은 15다. 완성 코드에서는 두 작은 호출을 실제로 실행하면서 이동 수만 반환하여 이 차이를 표로 확인한다.

문제를 나누면 전체 일은 얼마나 늘어나는가

분할 정복(divide and conquer)은 문제를 더 작은 문제로 나누어 각각 해결하고 결과를 합치는 방식이다. 전공 수업에서는 이때 드는 작업량도 점화식으로 나타낸다. 처음 문제 상황의 비용을 T(n)으로 쓰자. n이 1이면 T(1) = 0이다. n이 2 이상이면 왼쪽 크기를 a = n // 2, 오른쪽 크기를 b = n - a로 정하여 T(n) = T(a) + T(b) + n으로 쓸 수 있다.

//는 정수 나눗셈의 몫을 구하는 연산이다. n이 5이면 a는 2, b는 3이 된다. 두 크기를 모두 n // 2로 쓰면 합이 4가 되어 원소 하나를 빠뜨린다. 나눠진 크기의 합이 원래 크기와 같은지 확인하는 습관이 필요하다.

n이 8이면 첫 단계에서 8, 다음 단계에서 4 + 4, 그다음 단계에서 2 + 2 + 2 + 2만큼 일한다. 크기 1에서는 비용을 더하지 않는다. 비용을 더하는 단계는 세 개이며 각 단계의 합은 8이므로 T(8) = 24다. 이 예제의 비용은 실제 초 단위 시간이 아니라 우리가 정한 작업 단위의 개수다.

수를 몇 번 2로 나누어 1에 도달하는지 나타내는 값을 밑이 2인 로그(logarithm)라고 한다. 8은 세 번 나누면 1이므로 log₂ 8 = 3이다. 16은 네 번이므로 log₂ 16 = 4다. n이 2의 거듭제곱이면 이 비용 모형에서 T(n) = n × log₂ n이다. 완성 코드의 1, 2, 4, 8, 16 행으로 이 관계를 확인한다.

입력이 커질 때 작업량이 어떤 속도로 늘어나는지 표현하는 방법을 전공 수업에서는 시간 복잡도라고 부른다. 그중 빅오 표기법(big O notation)은 커지는 정도의 상한을 나타낸다. 이 예제는 O(n log n)으로 표현할 수 있다. 이는 실행 시간이 n log n초라는 뜻이 아니다. 입력이 늘어날 때 작업량을 비교하기 위한 표현이다.

반으로 나눈다는 말만으로 O(log n)이라고 결론 내릴 수는 없다. 한쪽만 처리하는 코드와 양쪽을 모두 처리하는 코드는 다르다. 여기에 합치는 비용까지 더해야 한다. 우리의 함수는 크기 8에서 호출을 15번 하지만 작업량은 24다. 호출 횟수만으로도 함수 안에서 한 일을 전부 설명할 수 없다는 예다.

구한 값을 보관해 중복 계산 줄이기

메모이제이션(memoization)은 같은 입력에 대한 계산 결과를 보관했다가 다시 사용하는 방법이다. 전공 수업에서는 문제가 같은 작은 문제를 반복해서 요구할 때 계산을 줄이는 기법으로 다룬다. 피보나치에서 F(2)를 한 번 구했다면 다음에는 그 값을 꺼내면 된다.

완성 코드에서는 사전으로 값을 보관한다. 사전은 이름 그대로 열쇠에 해당하는 키와 값을 짝지어 저장하는 자료형이다. {0: 0, 1: 1}은 입력 0의 결과가 0이고 입력 1의 결과가 1임을 뜻한다. n in cache로 보관 여부를 확인하고, cache[n]으로 값을 읽거나 저장한다. 호출에 앞서 사전이 모두 완성되어 있을 필요는 없다. 필요한 값을 계산한 직후 추가한다.

단, 보관된 값을 꺼내는 호출도 함수에 들어온 호출이다. 우리의 계수 방식에서는 그 호출도 센다. 처음 값 두 개만 보관한 빈 실험에서 F(6)을 구하면 일반 재귀는 25번, 메모이제이션 재귀는 11번 호출된다. 두 방식 모두 반환값은 8이다. 호출 수 비교를 위해 각 입력마다 새 사전을 만든다. 앞선 행의 결과를 다음 행에 물려주면 다른 실험이 된다.

메모이제이션을 사용하면 F(n)을 구할 때 2부터 n까지의 각 값을 한 번씩 새로 계산한다. 사전 조회와 덧셈을 일정한 비용으로 보는 단순 모형에서는 작업량이 n에 비례한다. 다만 큰 정수는 자릿수가 늘수록 덧셈과 보관 비용도 늘어난다. 작은 예제의 호출 수 표와 큰 정수를 다루는 실제 처리 비용은 구별해야 한다.

실무에서 만나는 곳

같은 규칙으로 반복해서 비용을 추정하거나, 같은 설정을 여러 계산에서 참조하거나, 같은 자료 묶음의 요약값을 여러 번 요구할 때 결과 보관이 도움이 된다. 이때 입력 번호 하나만 같다고 항상 같은 문제는 아니다. 요금표나 설정이 바뀐다면 같은 번호에도 결과가 달라질 수 있다. 결과를 결정하는 조건까지 보관 키에 포함하거나, 조건이 바뀔 때 보관값을 지워야 한다.

결과 보관은 계산 시간을 줄이는 대신 저장 공간을 사용한다. 또한 자기 자신을 부르는 깊이까지 줄여 주지는 않는다. 피보나치에서 가장 먼저 F(n - 1)을 따라 내려가는 길은 여전히 길다. 앞선 두 값만 있으면 되는 계산이라면 반복문으로 바꾸어 보관 공간과 호출 깊이를 함께 줄일 수도 있다.

완성 코드

다음 내용을 main.py로 저장한다. 모든 호출 수에는 맨 처음 호출과 기저 사례 호출을 포함한다. 메모이제이션에서는 보관값을 읽는 호출도 포함한다. marks는 호출마다 None을 하나씩 담는 목록이며, None은 여기서 별도의 데이터를 담지 않는 표시로만 사용한다. 작은 입력을 관찰하기 위한 방식이므로 실제 큰 작업의 계수기와는 구별한다.

def fib_plain(n, marks):
    marks.append(None)
    if n < 2:
        return n
    return fib_plain(n - 1, marks) + fib_plain(n - 2, marks)


def fib_memo(n, cache, marks):
    marks.append(None)
    if n in cache:
        return cache[n]
    cache[n] = (
        fib_memo(n - 1, cache, marks)
        + fib_memo(n - 2, cache, marks)
    )
    return cache[n]


def hanoi_count(n, marks):
    marks.append(None)
    if n == 0:
        return 0
    left = hanoi_count(n - 1, marks)
    right = hanoi_count(n - 1, marks)
    return left + 1 + right


def split_work(n, marks):
    marks.append(None)
    if n == 1:
        return 0
    left_size = n // 2
    right_size = n - left_size
    left = split_work(left_size, marks)
    right = split_work(right_size, marks)
    return left + right + n


def main():
    print("피보나치: 값과 호출 수")
    print("n | F(n) | 일반 호출 | 메모 호출")
    for n in range(7):
        plain_marks = []
        memo_marks = []
        plain_value = fib_plain(n, plain_marks)
        memo_value = fib_memo(n, {0: 0, 1: 1}, memo_marks)
        assert plain_value == memo_value
        print(
            f"{n} | {plain_value} | "
            f"{len(plain_marks)} | {len(memo_marks)}"
        )

    print()
    print("하노이: 이동 수와 호출 수")
    print("n | H(n) | 호출 수")
    for n in range(7):
        marks = []
        moves = hanoi_count(n, marks)
        assert moves == 2 ** n - 1
        assert len(marks) == 2 * moves + 1
        print(f"{n} | {moves} | {len(marks)}")

    print()
    print("분할 처리: 작업량과 호출 수")
    print("n | T(n) | 호출 수")
    for n in [1, 2, 4, 8, 16]:
        marks = []
        work = split_work(n, marks)
        assert len(marks) == 2 * n - 1
        print(f"{n} | {work} | {len(marks)}")


if __name__ == "__main__":
    main()

완성 코드의 함수는 정해진 입력 범위를 전제로 한다. 피보나치와 하노이는 0 이상의 정수, 분할 처리는 1 이상의 정수를 받는다. main은 그 범위의 작은 값만 전달한다. 입력을 직접 받는 프로그램으로 확장한다면 함수 호출 전에 범위를 확인해야 한다.

줄별 해설

fib_plain의 첫 줄은 계산에 들어온 사실을 기록한다. 기저 사례 검사보다 먼저 기록하므로 n이 0이나 1이어도 호출 수는 1이다. return n은 F(0) = 0과 F(1) = 1을 한꺼번에 표현한다. 마지막 줄의 두 호출에는 같은 marks를 전달하므로 양쪽 호출이 하나의 목록에 기록된다.

fib_memo도 먼저 호출을 기록한다. 이어서 if n in cache가 입력에 대한 결과가 있는지 확인한다. 보관값이 0인지 1인지가 아니라 키가 존재하는지를 검사한다는 점이 중요하다. 보관값이 없으면 두 작은 결과를 더하여 cache[n]에 넣는다. 이후 같은 n이 나타나면 그 아래의 재귀 호출을 실행하지 않고 반환한다.

hanoi_count는 원판이 0개일 때 이동 수 0을 반환한다. left와 right는 각각 n - 1개를 옮기는 이동 수다. 두 값이 같더라도 두 호출을 모두 실행한다. 실제로 두 하위 절차를 수행했을 때의 호출 수를 관찰하려는 목적 때문이다. 그 사이에 가장 큰 원판을 옮기는 한 번을 더한다. 이 함수는 실제 원판 배치를 바꾸지 않고 이동 수를 계산한다.

split_work는 크기 1에서 멈춘다. left_size와 right_size의 합은 항상 n이다. 두 작은 묶음의 작업량을 각각 계산한 뒤 현재 묶음에서 필요한 n을 더한다. n이 홀수여도 두 묶음 모두 1 이상이고 원래 크기보다 작으므로 종료 조건을 향해 진행한다.

main의 첫 반복문은 입력마다 두 marks 목록과 새 사전을 준비한다. 같은 목록을 다음 입력에 재사용하면 앞선 실험의 호출 기록까지 더해진다. assert는 뒤의 조건이 참인지 확인하고, 거짓이면 실행을 멈추는 문장이다. 여기서는 두 구현의 결과가 같은지 확인하는 작은 검사용 장치로 쓴다.

print 안의 f로 시작하는 문자열은 중괄호 속 값을 문자열에 넣는 표기다. 괄호 안에 이어 적은 두 문자열은 하나로 연결된다. 따라서 피보나치의 한 행이 한 줄로 출력된다. len은 목록에 담긴 원소 수를 반환하므로 호출 수가 된다.

하노이의 2 ** n - 1에서 **는 거듭제곱 연산이다. 이동 수는 n이 하나 증가할 때 두 배가 되고 1이 더해지므로 이 식과 맞는다. 실제로 2 × (2 ** (n - 1) - 1) + 1을 정리하면 2 ** n - 1이다. 코드의 검사는 선택한 작은 입력에서 이 관계를 확인한다. 유한한 입력을 검사했다는 사실만으로 모든 입력에 대한 주장이 입증되는 것은 아니다.

마지막 조건문은 이 파일을 직접 실행할 때 main을 호출한다. 완성 코드에는 입력 대기, 외부 파일, 난수, 네트워크 작업이 없다. 표시한 세 표를 출력한 뒤 실행을 마친다.

실행 결과

터미널에서 main.py가 있는 디렉터리로 이동하여 다음 명령을 실행한다.

python3 main.py

예상 출력은 다음과 같다.

피보나치: 값과 호출 수
n | F(n) | 일반 호출 | 메모 호출
0 | 0 | 1 | 1
1 | 1 | 1 | 1
2 | 1 | 3 | 3
3 | 2 | 5 | 5
4 | 3 | 9 | 7
5 | 5 | 15 | 9
6 | 8 | 25 | 11

하노이: 이동 수와 호출 수
n | H(n) | 호출 수
0 | 0 | 1
1 | 1 | 3
2 | 3 | 7
3 | 7 | 15
4 | 15 | 31
5 | 31 | 63
6 | 63 | 127

분할 처리: 작업량과 호출 수
n | T(n) | 호출 수
1 | 0 | 1
2 | 2 | 3
4 | 8 | 7
8 | 24 | 15
16 | 64 | 31

피보나치의 n = 2와 n = 3에서는 두 호출 수가 같다. 보관 기능을 추가했다고 모든 작은 입력에서 호출 수가 줄어드는 것은 아니다. n = 4부터 이미 계산한 값을 다시 요구하는 부분이 줄어든다. 한편 하노이는 입력이 1 늘 때 이동 수가 거의 두 배가 된다. 반으로 나누는 분할 처리와는 크기가 줄어드는 방식이 다르다.

실무에서 자주 틀리는 것

멈춤 조건만 적고 입력 범위를 놓친다

다음 함수는 n이 음수이면 멈춤 조건에 도달하지 못한다. 재귀가 계속되면 Python의 호출 깊이 제한에 걸린다. 재귀 호출 깊이는 동시에 끝나지 않고 기다리는 호출이 얼마나 쌓였는지를 뜻하며, 전체 호출 횟수와 다르다.

def countdown(n):
    if n == 0:
        return 0
    return 1 + countdown(n - 1)

이 함수가 정수 입력을 받는다고 정했다면 음수를 먼저 거절한다. ValueError는 값이 허용 범위에 맞지 않음을 알리는 예외다. raise는 그 예외를 발생시킨다.

def countdown(n):
    if n < 0:
        raise ValueError("n은 0 이상의 정수여야 한다")
    if n == 0:
        return 0
    return 1 + countdown(n - 1)

assert countdown(3) == 3

범위 검사는 잘못된 입력을 막지만 큰 입력의 호출 깊이까지 해결하지는 않는다. 반복문으로 표현할 수 있는 긴 계산이라면 호출 깊이를 늘리는 설정부터 바꾸기보다 반복문을 검토하는 편이 낫다.

두 배로 쓰고 두 번 실행했다고 센다

다음 코드는 하노이의 이동 수를 올바르게 반환하지만 하위 호출은 한 번만 실행한다.

def hanoi_short(n, marks):
    marks.append(None)
    if n == 0:
        return 0
    return 2 * hanoi_short(n - 1, marks) + 1

n이 3이면 반환값은 7이지만 호출은 4번이다. 곱셈의 2가 함수 실행까지 복제하지는 않는다. 두 하위 절차의 호출 수를 관찰하려면 다음처럼 작성한다.

def hanoi_expanded(n, marks):
    marks.append(None)
    if n == 0:
        return 0
    left = hanoi_expanded(n - 1, marks)
    right = hanoi_expanded(n - 1, marks)
    return left + 1 + right

marks = []
assert hanoi_expanded(3, marks) == 7
assert len(marks) == 15

값만 필요하면 첫 코드가 더 적게 계산한다. 틀린 부분은 첫 코드로 두 하위 절차를 실행한 호출 수를 측정했다고 해석하는 데 있다. 점화식의 값과 그 값을 계산하는 구현의 비용을 따로 보아야 한다.

결과를 저장하는 줄을 빠뜨린다

사전을 확인하기만 하고 새 결과를 넣지 않으면 중복 계산은 줄어들지 않는다. 다음 함수는 처음 두 값만 계속 재사용한다.

def fib_missing_store(n, cache):
    if n in cache:
        return cache[n]
    return (
        fib_missing_store(n - 1, cache)
        + fib_missing_store(n - 2, cache)
    )

계산한 값을 해당 입력의 키로 저장한 뒤 반환해야 한다. 실행 후 사전에 2부터 6까지도 들어 있는지 확인할 수 있다.

def fib_saved(n, cache):
    if n in cache:
        return cache[n]
    cache[n] = fib_saved(n - 1, cache) + fib_saved(n - 2, cache)
    return cache[n]

cache = {0: 0, 1: 1}
assert fib_saved(6, cache) == 8
assert set(cache) == set(range(7))

홀수 크기를 나누며 하나를 빠뜨린다

양쪽 크기를 모두 몫으로 정하면 홀수 입력에서 원래 크기를 보존하지 못한다.

n = 5
left_size = n // 2
right_size = n // 2
assert left_size + right_size == 4

한쪽 크기를 정한 뒤 나머지를 다른 쪽에 배정한다. 완성 코드의 split_work에 크기 5를 넣으면 작업량은 12다.

n = 5
left_size = n // 2
right_size = n - left_size
assert left_size + right_size == n

marks = []
assert split_work(5, marks) == 12
assert len(marks) == 9

짝수 입력만 검사하면 이 실수를 발견하기 어렵다. 크기가 다른 두 부분이 생기는 가장 작은 입력 3도 유용한 확인 대상이다.

한눈에 보기

반복 구조마다 값과 계산 비용을 구별하는 기준

대상	처음 값	반복 규칙	확인할 차이
피보나치 값	F(0) = 0, F(1) = 1	F(n) = F(n - 1) + F(n - 2)	결과값과 호출 수는 다르다
일반 피보나치 호출 수	C(0) = C(1) = 1	C(n) = 1 + C(n - 1) + C(n - 2)	현재 호출도 1번 센다
하노이 이동 수	H(0) = 0	H(n) = 2 × H(n - 1) + 1	이동 없는 호출도 있다
양쪽 분할 작업량	T(1) = 0	T(n) = T(a) + T(b) + n	a + b = n을 지킨다
메모이제이션	알려진 결과를 보관한다	없는 값만 계산해 저장한다	보관값 조회도 호출에 포함한다

재귀 코드를 읽을 때는 입력 범위, 멈추는 경우, 작아지는 양을 먼저 찾는다. 그다음 결과값을 구하는 식과 작업량을 세는 식을 따로 적는다. 마지막으로 보관된 값의 재사용 여부를 살피면 코드가 짧다는 인상에 기대지 않고 계산 구조를 설명할 수 있다.

연습 문제

1. 작업이 없는 상태의 비용은 4이고 작업 하나를 추가할 때 비용이 2씩 늘어난다. A(n)의 처음 값과 점화식을 적고, 재귀 함수로 A(5)를 확인하라.
2. 완성 코드의 fib_memo로 F(6)을 한 번 구한 뒤 같은 사전으로 F(6)을 다시 구한다. 두 번째 측정에는 새 marks 목록을 사용한다. 반환값과 호출 수를 예상하고 코드로 확인하라.
3. 하노이 이동 수를 H(n) = 2 × H(n - 1) + 1로 계산하되 하위 함수를 한 번만 호출하라. n = 4에서 이동 수와 호출 수를 확인하고, 완성 코드의 같은 입력과 비교하라.
4. split_work에 입력 3, 5, 6을 넣어 작업량과 호출 수를 확인하라. 이어서 크기 1에서는 0을 반환하고 나머지는 작은 두 작업량만 더하는 함수로 바꾸면 모든 결과가 0이 되는 이유를 설명하라.

정답과 해설

1. 처음 비용과 증가량을 분리한다

A(0) = 4이고, n이 1 이상이면 A(n) = A(n - 1) + 2다. A(5)는 14다. 처음 비용 4를 기저 사례에서 한 번 반환하고, 돌아오는 다섯 호출에서 각각 2를 더한다.

def added_cost(n):
    if n == 0:
        return 4
    return added_cost(n - 1) + 2

assert added_cost(5) == 14

2. 보관값이 있는 실험은 호출 한 번으로 끝난다

반환값은 다시 8이며 두 번째 호출 수는 1이다. 이미 키 6이 있으므로 작은 입력으로 내려가지 않는다. 완성 코드의 각 행은 새 사전으로 시작했기 때문에 n = 6의 호출 수가 11이었다.

cache = {0: 0, 1: 1}
first_marks = []
assert fib_memo(6, cache, first_marks) == 8
second_marks = []
assert fib_memo(6, cache, second_marks) == 8
assert len(first_marks) == 11
assert len(second_marks) == 1

3. 같은 이동 수를 더 적은 호출로 계산한다

이동 수는 15이고 호출 수는 5다. 완성 코드의 호출 수는 31이다. 아래 함수는 실제 두 하위 절차를 펼치지 않고 한쪽의 이동 수를 구해 두 배로 사용한다.

def hanoi_value(n, marks):
    marks.append(None)
    if n == 0:
        return 0
    smaller = hanoi_value(n - 1, marks)
    return 2 * smaller + 1

marks = []
assert hanoi_value(4, marks) == 15
assert len(marks) == 5

4. 나누는 비용과 합치는 비용을 구분한다

입력 3, 5, 6의 작업량은 각각 5, 12, 16이며 호출 수는 5, 9, 11이다. n이 2의 거듭제곱이 아니어도 완성 코드의 분할 규칙으로 계산할 수 있다.

for n, expected_work, expected_calls in [
    (3, 5, 5),
    (5, 12, 9),
    (6, 16, 11),
]:
    marks = []
    assert split_work(n, marks) == expected_work
    assert len(marks) == expected_calls

현재 묶음의 비용 n을 더하지 않으면 끝에서 받은 0끼리만 계속 더한다. 재귀 호출은 여러 번 발생하지만 반환값은 모든 입력에서 0이 된다. 계산 결과가 0이라는 사실은 계산 작업이 없었다는 뜻이 아니다.

def split_zero(n):
    if n == 1:
        return 0
    a = n // 2
    b = n - a
    return split_zero(a) + split_zero(b)

assert [split_zero(n) for n in range(1, 7)] == [0, 0, 0, 0, 0, 0]