자바 알고리즘 문제 풀이 입문. ch07. Recursive, Tree, Graph(DFS, BFS 기초) : 재귀 함수

 

 

https://hyejin.tistory.com/1251

자바 알고리즘 문제 풀이 입문. ch06. Sorting and Searching(정렬, 이분검색과 결정알고리즘) : 마구간

-> 이전 문제 풀이 

 

 

1. 재귀 함수 

설명

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

 

입력

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

 

출력

첫째 줄에 출력한다.

 

예시 입력 1 

3

 

예시 출력 1

1 2 3

 

 

문제 풀이  1

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

👾 : 섹션7은 문제 채점을 제공하지 않는 섹션이다. 우선 기본적으로 재귀 함수에 대한 설명을 위한 코드이기 때문에 굳이 정답을 채점할 필요는 없기 때문이라고 한다. 따라서 그냥 문제만 제공해준다. 

(사실 정답을 얻고 싶으면 재귀 함수 사용 안하고 for문을 통해서 그냥 1 2 3 출력해주면 되기 때문 !) 

 

우선 재귀 함수란 자기 자신을 계속 호출하는 함수이다.

자기 자신을 계속 호출하기 때문에 무한 반복에 빠질 수 있어 if-else 문을 거의 항상 사용한다. 

그리고 재귀 함수 문제를 풀 때 잘 모르겠다면 스택 프레임을 직접 그려가면서 푸는 것도 추천한다.

( 재귀 함수 관련 문제만 나오면 못풀고 쩔쩔 매는 나이기 때문에 나는 그럴 예정..ㅎ) 

 

아무튼 이 문제는 n 숫자가 주어지면 1 부터 n까지 출력하는 문제이다. 

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

-> 처음에 나는 이렇게 풀었었는데 이렇게 풀면 3 2 1 출력된다. 

왜냐하면 DFS(3) -> DFS(2) -> DSF(1) 로 이렇게 차례대로 호출될 때 3 출력하고 DFS(2) 호출하고, 2 출력하고 DFS(1) 호출하기 때문이다. 

 

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

따라서 이렇게 자신을 호출하는 함수 밑에 출력문을 넣어두면 DFS(3) -> DFS(2) -> DSF(1) 을 할 때 1 2 3 으로 차례대로 출력된다. 

 

이를 강의에서 그림을 그려주셔서 캡쳐해왔다. ㅎㅎ 

 

우선 DFS(3) 을 먼저 호출하기 때문에 스택에 가장 먼저 쌓인다. 

 

 

 

그리고 3을 호출하기 전에 DFS(2)를 호출하기 때문에 line 6까지만 했다는 것을 함께 기억한다. (DFS(3) 함수가 아직 안끝났다는 얘기임) 

 

 

DFS(2)도 함수를 다 마치기 전에 DFS(1)을 호출한다. 따라서 DFS(2) 도 line 6 까지만 수행했다는 것을 기억하고 있다. 

 

 

DFS(1) 도 DFS(0) 을 호출하고, line 6 까지 수행했다는 것을 기억하고 있는데 DFS(0) 은 이제 아무것도 수행안하고 return 하고 끝난다. 

그러면 다시 DFS(1)로 돌아오고, line 6 다음부터 수행한다. 따라서 1을 먼저 출력하고 DFS(1) 함수를 종료한다. 

그 다음 DFS(2)로 돌아와서, 마찬가지로 line 6 다음부터 수행해 2를 출력하고 DFS2(2) 함수를 종료한다. 

마지막으로 DFS(3) 으로 돌아와 3 출력을 실행하고, DFS(3) 함수를 종료한다.