Recursive Function : 재귀함수
1,2,3 순으로 출력되는 이유가 뭘까?
재귀함수는 Stack Frame을 사용한다.
class Main2 {
public void DFS(int n) {
if(n==0) return;
else {
DFS(n-1);//3,2,1
System.out.print(n + " ");
}
}
public static void main(String[] args) {
Main2 T = new Main2();
T.DFS(3);
}
}처음 DFS(3)이 돌면 line6에서 DFS(2)를 실행하는 함수를 만나서
'DFS(3)은 line6까지 돌았다' 라는 값과 주소를 stack에 저장한다.
DFS(2) 또한 line6에서 DFS(1)을 실행하는 함수를 만나서,
DFS(2)-line6 값이 stack에 저장된다.
DFS(1)도 line6에서 DFS(0)을 실행하는 함수를 만나,
DFS(1)-line6 값이 stack에 저장되고
DFS(0)이 실행되면 if문에서 n==0이 성립되므로 return되면
line9로 이동하여 DFS(0)이 끝난다.
그 이후 stack에 젤 위부터 pop되어서 DFS(1) line6 이후부터 실행되어 System.out.print(n + " ")을 실행한다.
DFS(1)이 실행을 마치고 종료되면 pop되고 DFS(2)-line6이후 부터가 실행된다.
DFS(2), DFS(3)도 마찬가지로 출력되고 stack이 모두 비워지면 종료된다.
즉, 재귀함수는 stack frame을 이용하기 때문에 가장 나중에 저장된 값부터 pop돼서 가장 먼저 출력된다.
