재귀함수에 대해 알아보고자 한다.
쉬운 이해를 위해 간단한 문제를 통해 예시를 들었다.
재귀함수란?
- 자신이 자기 자신을 호출하는 함수
재귀함수 문제
자연수 N이 입력되면 재귀함수를 이용하여 1부터 N까지 출력하는 프로그램을 작성하시오.
입력설명
첫 번째 줄은 정수 N(3<=N<=10)이 입력된다.
출력설명
첫째 줄에 출력한다.
입력예제 : 3 출력예제 : 1 2 3
문제 자체는 정 ~~ 말 간단하다. N이 입력되면 1부터 N까지 출력만 하면 된다.
하지만 지금 이 문제를 푸는 목표는 재귀함수에 대한 정리에 있다.
재귀함수란 무엇인지, 재귀함수가 어떻게 Back tracking 을 할 수 있는 구조인지 스택 프레임에 대해 정리하는 것이 목적이다.
예시 코드
우선 if문을 통한 간단한 코드이다.
import java.io.IOException;
public class Main {
public void DFS(int n){
if(n==0) return; // void 형에서 return 은 함수 종료의 의미도 가지고 있음.
else{
DFS(n-1); //함수 블록 안에서 자기 자신을 호출함. 재귀함수는 반복문의 형태이다.
System.out.print(n + " ");
}
}
public static void main(String[] args) throws IOException {
Main T = new Main();
T.DFS(3);
}
}
위 코드를 돌리면 아래와 같은 결과가 나온다.
1 2 3
여기서 중요한 점은 저 System.out.print(n+" "); 이 코드의 위치에 따라
결과는 다르게 나온다. 예를 들어
System.out.print(n + " ");
DFS(n-1);이렇게 위 아래가 바뀌었다면 결과는
3 2 1
이렇게 나온다.
이와 같이 나오는 이유는 스택 프레임에 대해 알아야 한다.
스택 프레임(Stack Frame)
재귀함수는 스택 프레임을 사용한다. 물론 모든 함수는 호출되면 스택 프레임이 생긴다.
우선 위 코드에서 DFS(3)을 만나게 되면 스택 프레임에 호출된 함수의 정보가 들어가게 된다. 그 정보는 대략 세 가지이다.
- 매개 변수 정보
- 지역 변수 정보
- 복귀 주소
이렇게 세 개의 정보를 가진 프레임이 생성된다.
예시 코드에 따르면
매개 변수 정보 : n
지역 변수 정보 : 지역 변수를 선언할 수도 있으니.
복귀 주소 : 위 DFS 함수가 끝나면 아래 T.DFS(3)로 가는 것.
이런 식이 되겠다.
그럼 위 코드를 보면 DFS(2)를 호출하게 된다.
DFS(n-1);
위와 같은 상황에서 복귀주소는 DFS(2)가 끝나면 DFS(3)으로 복귀를 할 것이다.
이런 식으로 쌓인 스택 프레임을 보자면
위 그림과 같이 쌓이게 된다.
DFS(3) -> DFS(2) -> DFS(1) -> DFS(0) 과 같은 순이다.
우선 처음 DFS(3)을 수행하고
DFS(n-1);위 코드에서 더 이상 내려가지 않고 DFS(2)가 호출된다.
호출이 되는 순간 DFS(3)에 line 7이 기록된다. 이는 line 7 까지 했다는 뜻이며
실제로 Debug 해보면 저렇게 표시가 될 것이다.
최고 상단의 DFS(0)은 (항상 스택 프레임의 제일 상단이 작동한다고 생각하면 된다.)
if(n==0) return;를 만나 바로 return 되어 종료된다.
그리고 자기 할 일 다 했으니, 스택 프레임에서 pop 된다.
이렇게 Back을 하면 DFS(1)은 방금 line 7 이라고 기록되어 있다. 그렇기 때문에 다음 라인에서 System.out.print를 해서 1을 출력한다.
이와 같은 과정으로 1 2 3 을 출력하게 되는 것이다.
위 과정을 이해했다면,
System.out.print(n + " ");
DFS(n-1); 이렇게 순서가 바뀌었을 땐, 3 2 1 이런 식으로 출력 되는 것이 이해가 될 것이다.
주요 정리
- 재귀 함수는 자기 자신을 호출하는 함수이다.
- 재귀함수는 스택 프레임을 사용한다.
- 스택 프레임에는 매개 변수 정보, 지역 변수 정보, 복귀 주소 세 가지 정보가 저장된다.
- 항상 스택 프레임의 최상단이 작동한다고 생각하면 된다.
끝 !
