[DFS,BFS 기초] 재귀함수

문제

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

 

입력설명

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

 

출력설명

첫째 줄에 출력한다.

 

입력예제 1

3

 

출력예제 1

1 2 3

 

---

 

재귀함수는 자기가 자기 자신을 호출하는 함수

자기가 자기 자신을 호출하는것이므로 DFS(n-1) 이렇게 해주면 자기 자신을 호출해주는 것

만약에 3이 넘어가면 DFS(2)를 호출하고 또 다음에는 DFS(1)을 호출하고 계속 호출하게 된다 -> 무한반복

재귀함수는 반복문의 형태

 

무한반복이므로 종료조건을 줘야됨 if(n==0) return; -> DFS(0)은 바로 종료될 것이다

void형에서 return;하면 함수의 종료의 의미를 갖고있음

 

System.out.print(n+" "); 이 코드를 DFS(n-1) 위에다가 놓으면 3 2 1 출력이고 아래다가 놓으면 1 2 3 출력이다.

이유는 재귀함수는 스택을 사용하기 때문이다

 

+ 여기서 스택 프레임이 생김 (매개변수 정보, 지역변수 정보, 이 함수가 끝나면 복귀될 주소)

 

처음 D(3)이 작동하면 6라인까지 가서 DFS(n-1)를 만나서 올라간다 7라인부터는 실행을 안한다 그래서 D(2)가 호출이 되어서

스택 맨 상단에 D(2)가 생성된다. D(3)은 대기상태가 됨 (7,8,9라인 안함 아직) 

D(2)도 6라인까지 하고 D(1)이 호출되고 맨 상단 스택에 D(1)이 생성된다.

D(1)도 6라인까지 하고 D(0)이 호출되고 맨 상단 스택에 D(0)이 생성된다.

D(0)은 0이니까 종료되므로 9라인까지 가서 자기 할 일을 다 했다. 그러니까 스택에서 pop 된다

 

< 스택은 맨 상단이 항상 작동된다 >

 

그러면 D(0)에서 back 해서 이제 D(1)로 다시 복귀된다 그러면 n을 출력하므로 1을 출력한다

-> D(2) 2 출력 -> D(3) 3 출력

그러므로 출력 순서가 1 2 3 이렇게 된다