설명

3을 입력하여 재귀 함수를 통해 3,2,1을 출력하세요.

코드

public class StackFrame {
    public static void main(String[] args) {
        DFS(3);
    }
    public static void DFS(int n){
        if(n == 0) return;
        DFS(n-1);
        System.out.println(n);
    }
}

코드는 엄청 간단하다. DFS 메서드를 통해 n 값을 받고 DFS 내부에 자신을 다시 호출하여(=재귀) n값이 0일때까지 반복하여 실행되는 함수를 선언한 것이다. 이 동작을 이해하기 위해서는 Stack Frame이라는 개념을 알고 있으면 이해하기 좋은데. 예전에 내가 쓴 글 중에 JVM의 메서드를 실행하는 방법에도 설명했던 내용이였다.

재귀 호출과 jvm의 구조

위에 글도 한번 봐주면 jvm의 구조도 이해하고 아래 설명할 내용도 이해가 빠를 것이다.

Stack Frame이란 재귀에서 메서드를 실행했을 때 구조를 이해하기 위한 개념인데. 먼저 우리가 지금 실행한 DFS(3)이 실행되었을 때 실제로 실행되어지는 메서드들을 살펴보아야한다. 순서대로 나열하면
DFS(3), DFS(2), DFS(1), DFS(0) 순서로 실행되는 것을 코드로 확인할 수 있을 것이다. 하지만 실제 출력 결과는

메서드의 실행 순서와 달리 1 2 3으로 실행되는 것을 알수있는데 이것은 Stack Frame을 이해하면 이해가 될것이다. Stack Frame이란 위 코드와 같이 재귀로 실행했을 경우 Stack의 자료구조에 메서드들이

그림과 같이 쌓여 있다는 것을 이해해야한다. Stack 자료구조와 동일하게 FILO로 출력된다. 또한 저 메서드들을 하나의 프레임이라 부르며 프레임에는 매개변수 지역변수 반환 주소 들의 정보가 포함되어 있다. 그리고 쌓여있는 Stack의 데이터가 pop() 되듯이 가장 늦게 들어온 메서드 부터 차례대로 실행되어 지는데

DFS(0) : n==0 이므로 return
DFS(1) : n!=0 이므로 1 출력
DFS(2) : n!=0 이므로 2 출력
DFS(3) : n!=0 이므로 3 출력

의 순서로 실행이 되므로 우리는 1,2,3의 출력결과를 확인 할 수 있었던 것이다.

Stack Frame의 개념과 재귀함수의 메서드 실행의 개념을 정확히 알고 넘어가기 위한 정리글