재귀 호출과 종료 조건

재귀 메서드는 문제를 더 작은 같은 형태로 바꾸어 자기 자신을 호출합니다.

트리 순회나 분할 정복처럼 구조가 재귀적일 때 코드가 자연스럽지만 모든 반복을 재귀로 바꿀 필요는 없습니다.

각 호출은 별도의 스택 프레임을 사용하므로 깊이가 지나치면 StackOverflowError가 납니다.

Java는 꼬리 재귀를 일반적으로 반복문으로 최적화한다고 보장하지 않습니다.

이 절에서는 종료 조건과 문제 크기 감소를 먼저 증명합니다.

기저 조건이 더 이상 호출하지 않는 경계다

입력이 가장 작은 문제에 도달했을 때 즉시 결과를 반환해야 합니다.

기저 조건이 빠지거나 도달할 수 없으면 호출이 끝나지 않습니다.

각 호출에서 문제 크기가 줄어야 한다

숫자는 0 쪽으로, 배열 구간은 더 짧게, 트리는 자식 노드로 이동해야 합니다.

감소 규칙을 말로 설명할 수 있어야 종료를 믿을 수 있습니다.

아래 재귀 예제에는 더 작은 입력으로 내려가는 호출과 즉시 값을 돌려주는 기저 조건이 함께 있습니다. 코드를 실행하기 전에 호출 인자를 손으로 나열해 종료를 먼저 증명해 봅니다.

public class RecursiveSum {
    static int sumTo(int value) {
        if (value < 0) throw new IllegalArgumentException("negative");
        if (value == 0) return 0;
        return value + sumTo(value - 1);
    }

    public static void main(String[] args) {
        System.out.println(sumTo(5));
        // System.out.println(sumTo(-1)); // 실행 시 IllegalArgumentException
        // endless(1); // StackOverflowError: 기저 조건에 도달하지 않음
    }

    static int endless(int value) {
        return endless(value + 1);
    }
}

호출할 때마다 입력이 기저 조건에 한 단계 가까워지는지 추적합니다. sumTo에서 value가 1씩 줄지 않거나 음수 입력을 막지 않으면 0에 도달하지 못하고 스택이 소진될 수 있습니다.

15

5에서 0까지 입력이 줄고 0이 기저 조건이므로 호출은 반드시 끝납니다.

반환 과정에서 부분 결과를 합친다

호출이 내려가는 단계와 결과가 올라오는 단계는 다릅니다.

sumTo는 현재 값과 더 작은 문제의 결과를 더해 돌아옵니다.

재귀 호출은 내려가면서 문제를 쪼개고, 반환하면서 부분 결과를 합칩니다. sumTo(4)의 호출 전에 enter, 반환 직전에 leave 로그를 넣으면 출력 순서가 서로 반대라는 사실을 확인할 수 있습니다.

static int iterativeSumTo(int value) {
    int total = 0;
    for (int current = 1; current <= value; current++) {
        total += current;
    }
    return total;
}

// 깊이가 입력 크기와 함께 커지면 반복 구현과 비교한다.

깊이가 입력 크기에 비례하면 반복을 검토한다

연결 리스트나 큰 숫자처럼 깊이가 쉽게 커지는 문제는 명시적 스택이나 반복문이 안전합니다.

읽기 쉬움과 스택 한도를 함께 비교합니다.

호출 트리의 중복 계산을 찾는다

피보나치처럼 같은 입력을 여러 번 다시 계산하면 재귀 구조가 명료해도 비용이 급격히 커집니다.

메모이제이션이나 반복 계산으로 중복을 제거합니다.

스택 추적으로 현재 입력을 확인한다

오류가 나면 스택 트레이스에 반복된 메서드 호출과 각 프레임의 위치가 나타납니다.

종료 조건에 도달하지 못한 입력 변화부터 조사합니다.

스택 추적의 같은 메서드가 반복되는 프레임에서 인자 값을 확인하면 줄지 않는 입력을 찾을 수 있습니다. 0, 1, 작은 정상값, 잘못된 음수를 각각 넣어 기저 조건과 입력 검증이 서로 다른 역할을 하는지도 점검하세요.

재귀는 자기 호출이라는 문법보다 기저 조건, 문제 감소, 결과 결합이라는 세 증명이 갖춰졌을 때 사용합니다.