섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 1. 재귀함수(스택프레임)

문제

• 자연수 N이 입력되면 재귀함수를 이용하여 1부터 N까지를 출력하는 프로그램을 작성하세요.

입력

• 첫 번째 줄은 정수 N(3<=N<=10)이 입력된다.

출력

• 첫째 줄에 출력한다.

입출력 예제

---

풀이방식

이번 문제는 재귀함수를(을) 사용하여 푸는 문제이다.

재귀함수란 자기가 자기 자신을 호출하는 함수이며, 스택 프레임을 사용한다.

---

스택 프레임이란 스택 영역에 함수를 구분하기 위해 생성되는 공간이다.

스택 영역은 함수의 호출과 함께 할당되며, 함수의 호출이 완료되면 소멸한다.

이 스택 프레임에는 호출된 함수의 매개변수 정보, 지역변수 정보, 복귀 주소 등이 저장되어 있다.

아래 예시를 보며 확인해보자.

코드는 아래와 같다.

public class RecursiveFunction {
	public void DFS(int N) {
		if(N == 0) {
			return;
		} else {
			DFS(N-1);
			System.out.print(N + " ");
		}
	}
	
	public static void main(String[] args) {
		RecursiveFunction R = new RecursiveFunction();
		R.DFS(3);
	}
}

---

1. R.DFS(3)을 통해 DFS 함수에 3이라는 값이 들어가서 DFS(3)이 스택 영역에 할당된다. 

2. 항상 최상단에 있는 스택 프레임이 작동되므로 할당된 DFS(3)이 수행된다.

3. 그러면 ' if(N == 0) { ' 이 있는 4 라인부터 한줄씩 넘어가며 6라인까지 도달한다.

4. 6 라인에 도달하는 순간, 그 뒤는 수행하지 않고 바로 함수를 수행하며 DFS(2) 를 호출한다.

5. DFS(2)를 호출하는 순간에 DFS(3)에는 ' line 6 ' 이라는 정보가 들어간다.

6. DFS(3)은 대기 상태가 되고, DFS(2)가 스택 영역에 들어가서 작동한다.

7. 동일하게 4 라인부터 수행되고, 6 라인에 도달하는 순간  ' line 6 ' 이라는 정보가 들어간다.

8. DFS(2)는 대기 상태가 되고, DSF(1)이 스택 영역에 들어가서 작동한다.

9. 동일하게 4 라인부터 수행되고, 6 라인에 도달하는 순간  ' line 6 ' 이라는 정보가 들어간다.

8. DFS(1)는 대기 상태가 되고, DSF(0)이 스택 영역에 들어가서 작동한다.

9. DSF(0)은 4 라인에서 바로 리턴된다. 이 순간에 9 라인으로 이동하며 종료한다.

10. 종료가 되었으면 DSF(0)은 스택에서 pop() 된다.

11. DFS(0)이 종료되고, DFS(1)로 복귀한다. 

12. DFS(1)에는 복귀주소인 ' line 6 ' 이 저장되어있기에 출력문인 7 라인이 수행되고, ' 1 ' 를 출력한다. 

13. 출력을 완료했으면 pop() 한 후에 DFS(2)로 복귀한다.

14. 위 과정을 반복하면서 '1, 2, 3' 이라는 결과를 출력한다.

---

답안소스

public class RecursiveFunction {
	public void DFS(int N) {
		if(N == 0) {
			return;
		} else {
			DFS(N-1);
			System.out.print(N + " ");
		}
	}
	
	public static void main(String[] args) {
		RecursiveFunction R = new RecursiveFunction();
		R.DFS(3);
	}
}

---

해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.