재귀 함수(DFS)

간단하게 설명하자면 자기가 자기자신을 호출하는 함수

 

문제) 

자연수 N입력 시 재귀함수를 사용하여 1~N까지 출력

 

풀이)

//재귀함수 - 깊이 우선 탐색
public class Main{
	//무한적으로 작동되므로 if~else로 멈추게 하기!
	public void DFS(int n) {
		if(n==0) {
			return;//void에서는 종료를 뜻함.
		}else {
			System.out.print(n + " ");
            DFS(n-1);
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Main R = new Main();
		R.DFS(3);
	}
}

위 코드에 3을 입력 시 ,else 절에서 DFS메소드를 호출 시 값이 3 2 1 로 출력된다.

원하는 값은 1 2 3 이므로 소스를 아래와 같이 변경해야한다. 

줄만 서로 바꿨을 뿐인데 출력값의 정렬이 변경되었을까?

- 재귀함수는 Stack(LIFO) 프레임 구조를 사용하기 때문이다

 

간단하게 설명하자면 5번째 라인의 DFS(n-1) 이 실행되면 public void DFS를 다시 실행하게 되는 방식인데,

반복적으로 n이 0이 될때 까지 DFS의 위치를 stack에 저장해놓는다

DFS(3) -- 5번째 라인 >>>> DFS(2) -- 5번째 라인 >>>> DFS(1) -- 5번째 라인 이라고 저장해놓는다.

이렇게 저장 후 n=0이 되면 DFS라인 위치를 기억해놨다가 syso의 부분을 다시 실행시킨다.

Stack의 특성으로 가장 마지막으로 저장되었던  DFS(1) 라인부터 출력이 되는 것이다!

그러므로 1 2 3 으로 출력이 되는 것이다.

 

Stack Frame에 자세한 내용은 TCP School 사이트를 추천합니다.

http://www.tcpschool.com/c/c_memory_stackframe