재귀함수(스택프레임)

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

 

▣ 입력 설명

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

 

▣ 출력설명

첫째 줄에 출력한다.

 

▣ 입력예제

 3

 

▣ 출력예제

1 2 3

 

 

---

 

 

 

Chapter 7에서는 이론과 코드구현을 중심으로 진행할 예정입니다.

필수 개념과 그 개념을 구현하는 방법을 익힌다고 생각하면서 가볍게 보시면 될 것 같습니다. 

다음 Chapter에서 공부하게 될 DFS, BFS 알고리즘 문제를 풀이할 때 기본이 되는 중요한 개념입니다.

 

재귀 함수 : 자기가 자기 자신을 호출하는 함수로 반복문의 한 형태입니다. 
    주로 메서드 이름은 DFS( )를 사용합니다.
    if ~ else를 활용하는 것을 초보자 단계에서 추천합니다. 

 

 

예제  

public class Main {
	public void DFS(int n) {
		
		DFS(n-1);
		
	}

	public static void main(String[] args) {
		Main T = new Main();
		T.DFS(3);

	}

}

 

이 예제를 출력하면 끝없는 수가 나오게 됩니다, 무한 반복으로 자기를 호출하는 것인데요.

+ 이 경우 종료를 알려줘야 합니다.

 

 

if ~ else문을 통해 구현해보겠습니다. 

public class Main {
	public void DFS(int n) {
		if(n == 0) return; // 함수 바로 종료 -> 9라인으로 이동
		else {
			System.out.print(n + " ");
			DFS(n-1);
		}	
	}

	public static void main(String[] args) {
		Main T = new Main();
		T.DFS(3);
	}
}

 

💡 return 역할
1. 호출한 곳에 반환 
2. void형 함수에서 return은 함수 바로 종료.

 

출력

3 2 1 

하지만 우리는 1 2 3 출력을 원하므로 출력 함수의 위치를 바꿔주겠습니다.

 

 

 

 

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

	public static void main(String[] args) {
		Main T = new Main();
		T.DFS(3);
	}
}

출력

 

1 2 3

 

 

---

 

 

여기서 의문이 들 수 있습니다. 다른 코드는 똑같고 출력 함수 위치를 바꿨을 뿐인데 출력 결과가 왜 달라지는 것일까요?

System.out.print(n + " ");

 

이번 강에서는 이것을 이해하는 것이 제일 중요합니다.

 

 

 

재귀는 스택(프레임)이라는 자료구조를 이용합니다, 이제부터는 그림을 그려서 설명하는 게 빠르므로

그림을 그려 설명드리겠습니다. 

 

 

여기서 알아두셔야 할 첫번째는 "Stack 맨 상단에 있는 게 작동"한다는 점입니다. 

그리고 자신의 할 일을 다했다면 pop() 한 후 복귀 주소로 이동하는 것을 반복합니다. 

 

그림에서 이해하신 것 처럼 DFS(3)이 DFS(2)를 호출하고, DFS(2)은 DFS(1)을, DFS(1)은 DFS(0)을 호출한 뒤

DFS(0)에서는 line 5를 만나 함수를 종료하고(line 10) 거꾸로 복귀하면서 출력하게 됩니다. 

 

따라서 Stack의 구조상의 이유로 1 2 3으로 출력됩니다.