종료 조건. 스택 오버플로 오류

종료 조건이 없는 재귀 코드의 예

재귀 문제를 다시 살펴보겠습니다. 예를 들어 피보나치 수를 계산하는 것을 고려하십시오. 피보나치 수열은 처음 두 숫자가 0과 1이고 다음 각 숫자는 이전 두 숫자의 합과 같은 숫자 시퀀스라는 것을 누구나 기억할 것입니다.

다음 숫자를 계산하고 표시하는 코드를 작성해 보겠습니다.

public class Fibonacci {
    public static void main(String[] args) {
        System.out.println(0);
        System.out.println(1);
        printFibonacci(0, 1);
    }

    private static void printFibonacci(long penultimate, long previous) {
        long current = penultimate + previous;
        System.out.println(current);
        printFibonacci(previous, current);
    }
}

재귀적인 printFibonacci 메서드를 처음 호출하기 전에 시퀀스의 처음 두 숫자인 0과 1을 인쇄합니다. 재귀 메서드는 매개 변수 자체가 아니라 입력 매개 변수의 합계만 표시하기 때문에 이렇게 해야 합니다.

코드는 괜찮아 보입니다. 우리는 두 개의 숫자를 얻고, 합계를 계산하고, 콘솔에 인쇄하고, 재귀적으로 printFibonacci 메서드를 다시 호출합니다. 이전 번호(previous)와 현재 번호(current)를 인수로 전달합니다.

실제로 코드에는 두 가지 오류가 있습니다. 코드를 실행하면 볼 수 있습니다.

첫 번째 오류는 long 형식을 오버플로하는 것입니다. 시퀀스의 104번째 숫자는 음수이며 long 형식이 오버플로되었음을 나타냅니다.

두 번째 오류는 다릅니다. 대략 12,000개의 숫자를 계산한 후 다음을 얻습니다.

지금은 Java에서 메서드 호출 스택이 무엇인지 기억할 적절한 시기입니다. Java 머신은 모든 함수 호출을 기록합니다. 이를 위해 스택이라는 특별한 종류의 컬렉션을 사용합니다. 한 함수가 다른 함수를 호출하면 Java 시스템이 새 StackTraceElement를 스택에 푸시합니다. 함수가 종료되면 이 요소는 스택에서 제거됩니다. 따라서 스택은 함수 호출 스택의 현재 상태에 대한 최신 정보를 항상 저장합니다. StackTraceElement에 대한 설명서에는 "응용 프로그램이 너무 깊게 반복되어 스택 오버플로가 발생하면 발생합니다."라고 나와 있습니다. 실행 중인 JVM에는 메서드 호출 스택을 저장하기 위한 특수 메모리 영역이 있습니다. 이 메모리 영역의 크기는 OS 및 JVM 설정에 따라 다릅니다. 메서드 호출 스택 자체 외에도 기본 변수(메서드 매개 변수의 특정 값) 및 참조 변수의 주소("힙"이라는 메모리 영역에 있음)는 이 특수 메모리 영역에 저장됩니다. 호출 스택에 대한 액세스는 LIFO 원칙을 따릅니다.

종료 조건이 있는 수정된 예

코드의 두 번째 문제를 수정하여 시작하겠습니다.

문제를 정면으로 해결해 봅시다. 스택이 너무 작으면 더 크게 만들어 봅시다. 이렇게 하려면 "-Xss" 플래그로 JVM을 시작하고 스택에 할당할 메모리 양을 지정합니다. 5MB를 할당해 보겠습니다. IDEA에서는 다음과 같이 표시됩니다.

출력 길이를 늘릴 수 있었습니다. 이제 약 12,000개의 숫자로 제한되지 않고 시퀀스의 49,000개 이상의 숫자를 계산할 수 있습니다. 그러나 어느 시점에서 우리는 여전히 StackOverflowError 를 얻습니다 .

스택 크기를 늘릴 수는 있지만 근본적인 문제는 해결되지 않습니다. 자, 논리에서 문제를 찾아봅시다. 재귀가 멈추는 지점이 있어야 합니다. 즉, 호출 스택이 풀릴 수 있도록 재귀 메서드가 더 이상 호출되지 않는 시기를 결정하는 조건이 있어야 합니다. 이러한 조건을 정의하기 위해 우리의 목표를 명시적으로 만들어 보겠습니다. 숫자가 Integer.MAX_VALUE 미만인 한 피보나치 수열을 표시합니다 .

이 조건을 고려할 새 printFibonacciWithCondition 메서드를 작성해 보겠습니다 . 그리고 수정된 새로운 메소드를 메인 메소드에서 호출하도록 하겠습니다.

public class Fibonacci {
    public static void main(String[] args) {
        System.out.println(0);
        System.out.println(1);
//        printFibonacci(0, 1);
        printFibonacciWithCondition(0, 1);
    }

    private static void printFibonacci(long penultimate, long previous) {
        long current = penultimate + previous;
        System.out.println(current);
        printFibonacci(previous, current);
    }

    private static void printFibonacciWithCondition(long penultimate, long previous) {
        long current = penultimate + previous;
        if (current > Integer.MAX_VALUE) {
            return;
        }
        System.out.println(current);
        printFibonacciWithCondition(previous, current);
    }
}

코드를 실행한 후 출력이 숫자 1836311903으로 끝나는 것을 볼 수 있습니다. 이 숫자 앞의 숫자는 1134903170입니다. 이 숫자의 합은 2_971_215_073이며 실제로 Integer.MAX_VALUE(2_147_483_647)보다 큽니다 .

이 변경으로 긴 오버플로 버그가 자동으로 수정되었습니다. 시리즈를 더 많이 계산해야 하는 경우 BigInteger 와 같은 다른 데이터 유형을 사용해야 합니다 .

재귀 하강 및 풀기

코드가 어떻게 실행되는지 단계별로 분석해 봅시다. 이를 위해 echo 메서드를 추가하고 printFibonacciWithCondition 메서드 의 재귀 호출 전후에 호출합니다 .

public class Fibonacci {
    public static void main(String[] args) {
        System.out.println(0);
        System.out.println(1);
        printFibonacciWithCondition(0, 1);
    }

    private static void printFibonacciWithCondition(long penultimate, long previous) {
        long current = penultimate + previous;
        if (current > Integer.MAX_VALUE) {
            return;
        }
        echo(true, penultimate, previous);
        System.out.println(current);
        printFibonacciWithCondition(previous, current);
        echo(false, penultimate, previous);
    }

    private static void echo(boolean isBeforeRecursiveCall, long penultimate, long previous) {
        if (isBeforeRecursiveCall) {
            System.out.printf("Before method call with args: %d, %d. Current number = ", penultimate, previous);
        } else {
            System.out.printf("After method call with args: %d, %d\n", penultimate, previous);
        }
    }
}

이 프로그램은 다음과 같은 결과를 제공합니다.

다음은 무슨 일이 일어나고 있는지 시각화한 것입니다.

다시 말해봅시다: printFibonacciWithCondition 메소드가 호출됩니다. 현재 숫자를 계산합니다. 적합하다면 이를 표시하고 새 인수를 사용하여 printFibonacciWithCondition 메서드를 다시 호출합니다.

재귀 메서드가 호출되는 한 이를 "재귀 하강"이라고 합니다. 재귀가 종료되고 메서드 호출이 반환되면 호출 스택이 "풀림" 상태라고 합니다.

재귀는 프로그래밍에서 흥미로운 주제입니다. 재료를 더 잘 다루기 위해 작업을 약간 변경해 보겠습니다. 새로운 작업은 Integer.MAX_VALUE 를 초과하지 않는 피보나치 수열의 모든 숫자를 내림차순으로 출력하는 것입니다 . 우리는 이미 이 작업에 필요한 모든 코드를 작성했습니다. 남은 것은 현재 숫자를 표시하고 재귀 메서드를 호출하는 순서를 바꾸는 것입니다. 즉, 첫 번째 예에서 "하강" 중에 계산된 숫자가 표시되었지만 이제 "맨 아래로 내려간" 다음 "다시 올라가는 중"에 숫자를 표시해야 합니다. 그리고 물론, 메인 메소드에서는 재귀 메소드를 호출한 후 시퀀스의 두 초기 숫자(0과 1)를 표시한 후 교체합니다. 가독성을 위해방법.

public class Fibonacci {
    public static void main(String[] args) {
        printFibonacciWithCondition(0, 1);
        System.out.println(1);
        System.out.println(0);
    }

    private static void printFibonacciWithCondition(long penultimate, long previous) {
        long current = penultimate + previous;
        if (current > Integer.MAX_VALUE) {
            return;
        }
        printFibonacciWithCondition(previous, current);
        System.out.println(current);
    }
}

출력은 다음과 같습니다.