재귀함수(스택프레임)

스택 프레임이란

함수가 호출될 때, 그 함수만의 스택 영역을 구분하기 위해 생성되는 공간입니다.

지역변수, 매개변수가 저장되며, 함수 호출 시 할당되고 함수가 종료되면 소멸합니다.

 

구성요소

• 지역변수
• 매개변수
• 복귀 주소

메서드가 호출될 때마다 스택 프레임이 만들어지며, 메서드의 호출이 끝나면 자동으로 스택 프레임은 제거된다.

 

---

실습 예제

public class Main {

    public void DFS(int N) {
        if (N == 0) return;
        else {
            DFS(N - 1);
            System.out.print(N + " ");
        }
    }

    public static void main(String[] args) {
        Main T = new Main();
        T.DFS(3);
    }
}

1, 2, 3

 

sout 위치만 바꿔주었을 뿐인데 순서가 완전 정반대로 나오게 됩니다. Stack 개념을 이해해야 합니다.

DFS(N-1)이 호출들이 대기상태로 쌓이게 되는데, 마지막 DFS가 실행되면 Stack의 가장 상단의 값이 작동된다고 생각하면 편합니다.

DFS

1. DFS(0)은 더 이상 실행할 내용이 없으므로 pop
2. DFS(1)은 1 출력 후 pop
3. DFS(2)은 2 출력 후 pop
4. DFS(3)은 3 출력 후 pop

항상 스택의 상단이 실행된다고 생각하면 백트래킹 문제를 풀 때도 유용하게 사용할 수 있습니다.