자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(Recursive_재귀함수(스택프레임))

 

 

1. 재귀함수(스택프레임)

 

예시 입력 1 

3

예시 출력 1

1 2 3

 

public class Main {

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

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

 

위의 코드에서 보는 것 처럼 출력을 몇번째 줄에서 하느냐에 따라 반환값이 다르게 나타난다.

1번의 경우 3 2 1로 출력되고, 2번은 1 2 3으로 출력된다.

재귀함수 위에 놓는지 아래에 놓는지에 따라 출력이 다르기 때문에 굉장히 중요합니다.

 

재귀 함수는 stack이라는 자료구조인 스택 프레임을 사용한다.

물론 모든 함수가 호출되면 스택 프레임이라고 해서 스택을 사용해서 스택 프레임이 생긴다.

 

 

매개 변수 정보 지역 변수 정보, 복귀 주소 정보

함수를 호출하면 해당하는 3개의 정보를 갖고 있는 프레임이 생깁니다.

스택프레임을 사용함으로써 백트래킹을 할 수 있다.

 

 

Main메소드에서 DFS를 호출하면 DFS라는 메소드의 스택 프레임이 생성됩니다.

그러면 조건문은 참이 아니라서 넘어가고 6라인에서 다시 DFS가 호출이 일어납니다. 호출이 되는 순간 stack에 기록을 합니다.

그러면 D(3)은 대기상태로 들어가고, 스택의 상단에 있는게 동작됩니다.

 

그러면 DFS(2)가 동작하고, 다시 6라인에서 DFS(1)이 호출됩니다. 그렇게 DFS(0)까지 동작하는데, 안에 있는 if문에서 참이라서 

return하는 순간 9라인으로 와서 종료됩니다.

그러면 DFS(0)은 자기 할일이 다 끝난 상태라 스택에서 pop됩니다. 그러고 나서 스택의 상단에 있는게 작동하므로 DFS(0)에서 DFS(1)로 복귀합니다. 그러면 백해서 DFS(1)이 작동하게 됩니다. 그러면 디버깅해봤을때 DFS(1)의 6라인으로 돌아오게 됩니다. 이제 7라인 부터 시작하게 되니까 출력을 하고  DFS(1)는 자기할일 끝내면서 pop되고 사라집니다.

이제 DFS(2)로 복귀하는 순간 다시 6라인으로 복귀합니다. 위와 같은 방식으로 DFS(3)까지 복귀하게 되면 아래가 출력되고 끝납니다.

1 2 3