스택 오버플로우(Stack Overflow)

1. Stack Overflow의 뜻

2. Stack Overflow의 대표적 원인과 해결 방법

2.1 원인: 무한 재귀 호출 (Infinite Recursion)

public class StackOverflowExample {

    public static void recursiveMethod() {
        recursiveMethod();  // 종료 조건 없이 자기 자신을 계속 호출
    }

    public static void main(String[] args) {
        recursiveMethod();  // StackOverflowError 발생
    }
}

해결 방법: 종료 조건 추가 (Base Case)

public class StackOverflowSolution {

    public static void recursiveMethod(int n) {
        if (n == 0) {  // 종료 조건 설정
            return;   // 재귀 호출 종료
        }
        recursiveMethod(n - 1);  // 재귀 호출
    }

    public static void main(String[] args) {
        recursiveMethod(5);  // 안전한 재귀 호출
    }
}

2.2 원인: 과도한 재귀 깊이 (Excessive Recursion Depth)

public class ExcessiveRecursionExample {

    public static void deepRecursion(int n) {
        if (n == 0) {
            return;
        }
        deepRecursion(n - 1);  // 재귀 호출
    }

    public static void main(String[] args) {
        deepRecursion(100000);  // 큰 깊이의 재귀 호출 -> StackOverflowError 발생 가능
    }
}

해결 방법: 반복문으로 리팩토링 (Refactoring to Iteration)

public class IterativeSolution {

    public static void iterativeMethod(int n) {
        while (n > 0) {
            n--;
        }
    }

    public static void main(String[] args) {
        iterativeMethod(100000);  // StackOverflowError 발생하지 않음
    }
}

2.3 꼬리 재귀 최적화 (Tail Recursion Optimization)

• Tail Recursion은 재귀 호출이 함수의 마지막 동작으로 이루어지는 경우입니다. 일부 컴파일러나 런타임에서는 이러한 꼬리 재귀를 최적화하여 스택 프레임을 재사용함으로써 스택 오버플로우를 방지할 수 있습니다.

• Java에서는 기본적으로 꼬리 재귀 최적화(Tail Call Optimization, TCO)가 지원되지 않지만, 이 패턴을 활용할 수 있는 경우, 알고리즘을 다른 언어로 구현하거나, 꼬리 재귀 최적화가 가능한 런타임 환경에서 실행할 수도 있습니다.

public class TailRecursionExample {

    public static int tailRecursiveMethod(int n, int result) {
        if (n == 0) {
            return result;  // 종료 조건
        }
        return tailRecursiveMethod(n - 1, result * n);  // 마지막 호출로 꼬리 재귀
    }

    public static void main(String[] args) {
        System.out.println(tailRecursiveMethod(5, 1));  // 결과: 120
    }
}

2.4 스택 크기 조정

• JVM(Java Virtual Machine) 스택 크기 조정: Java에서는 JVM의 스택 크기를 조정하여 스택 오버플로우를 방지할 수 있습니다. 그러나 이것은 임시적인 해결책에 불과하며, 근본적인 문제를 해결하지는 않습니다.

• 커맨드 라인에서 Xss 옵션을 사용하여 스택 크기를 늘릴 수 있습니다.

java -Xss2m YourClassName

• 이 옵션은 기본 스택 크기를 초과하는 큰 재귀나 깊은 함수 호출을 처리할 때 유용할 수 있습니다. 하지만 스택 크기를 무작정 늘리는 것은 메모리 낭비로 이어질 수 있으며, 근본적인 문제를 해결하는 방법은 아닙니다.

2.5 재귀 대신 데이터 구조 사용

• 재귀 호출을 데이터 구조(예: 스택 자료구조)를 사용하여 구현할 수 있습니다. 이렇게 하면 스택 오버플로우를 피하면서 재귀 알고리즘의 논리를 유지할 수 있습니다.

import java.util.Stack;

public class StackBasedSolution {

    public static void iterativeFactorial(int n) {
        Stack<Integer> stack = new Stack<>();
        int result = 1;

        while (n > 0) {
            stack.push(n--);
        }

        while (!stack.isEmpty()) {
            result *= stack.pop();
        }

        System.out.println(result);  // 결과 출력
    }

    public static void main(String[] args) {
        iterativeFactorial(5);  // 결과: 120
    }
}