[자료구조][스택] - 재귀 스택

재귀 함수란?

자신을 다시 호출하는 함수

재귀 함수 예시

    int factorial(int n) {
        if (n == 1) { // 종료 조건
            return 1; 
        }
        return n * factorial(n - 1); // 재귀 호출
    }
    
    
    System.out.println(factorial(5)); // 5 * 4 * 3 * 2 * 1 = 120

 

재귀 함수는 매번 자기 자신을 호출할 때마다

현재 함수의 상태가 스택에 저장됨

 

하지만 재귀 호출이 너무 깊어지면

Stack Overflow 가 발생할 수도 있음

 

 

해당 문제를 해결하기 위해

재귀를 명시적 스택을 사용하여

반복문으로 대체할 수 있다

명시적 재귀 스택 예시

    int factorial(int n) {
        Stack<Integer> stack = new Stack<>();
        int result = 1;
        while (n > 1) {
            stack.push(n);
            n--;
        }
        while (!stack.isEmpty()) {
            result *= stack.pop();
        }
        return result;
    }

    System.out.println(factorial(5)); // 120