재귀 함수를 알기 전에, 먼저 스택에 대해 정확히 알고 넘어가야한다.
메서드(함수) 호출 시마다 각각의 스택 프레임(그 메서드만을 위한 공간)이 생성되고 메서드 안에서 사용되는 값들을 저장(Runtime Constant Pool에 대한 참조)하고, 호출된 메서드의 매개변수, 지역변수, 리턴 값 및 연산 시 일어나는 값들을 임시로 저장한다. 메서드 실행이 끝나면 프레임별로 제거된다.
예시로 다음 코드를 보면,
public class Recursive {
public static void main(String[] args) {
Recursive T = new Recursive();
T.DFS(3);
}
public void DFS(int n) {
if (n == 0) {
return;
} else {
System.out.print(n + " ");
DFS(n - 1);
}
}
}
Java
복사
이 코드의 결과는 3 2 1 이다. DFS 함수로 인자 값 3이 들어오면, 인자 값이 0이 될때까지 재귀적으로 DFS 함수를 호출하는 것이다. 그렇다면 1 2 3 순서로 오름차순으로 표현하고자 한다면 어떻게 해야할까?
public class Recursive {
public static void main(String[] args) {
Recursive T = new Recursive();
T.DFS(3);
}
public void DFS(int n) {
if (n == 0) {
return;
} else {
DFS(n - 1); // line 11
System.out.print(n + " ");
}
}
}
Java
복사
답은 간단하다. print 메서드를 DFS 함수 아래로 위치하면 된다. 이 원리가 바로 스택(스택 프레임)을 활용한 것이다.
스택은 LIFO 방식으로 후입선출 즉, 가장 나중에 저장된 데이터가 가장 먼저 인출되는 방식으로 동작한다.
1.
처음 인자값으로 3이 들어오고 DFS 함수를 실행한다.
2.
0이 아니기 때문에 else문을 타게 되고 안에서 DFS(n - 1) 함수를 타게 된다. 이때, 가장 중요한 것은 처음 DFS(3) 함수는 line 11에 멈춰있는 상태로 스택에 쌓이게 된다. 그 다음 System.out.print() 메서드가 실행되지 않는 상태로 스택에 쌓인다는 뜻.
3.
다음은 인자 값으로 2가 들어온다. 이번에도 0이 아니기 때문에 2번 문항과 똑같이 실행된다. 그렇게 하나씩 계속 인자 값이 0이 될 때까지 쌓이게 된다.
4.
마지막으로 DFS() 함수에 0이 들어오고, 바로 return하게 되기에 해당 함수는 바로 종료된다. 이후에 스택에 잠시 멈춰있던 함수들이 차례로 실행된다. 즉, 마지막으로 쌓였던 인자 값 1부터 실행된다는 뜻이다.
이런 재귀 함수를 다양한 방식으로 사용할 수 있다.
이진수
public class Binary {
public static void main(String[] args) {
Binary T = new Binary();
T.DFS(13);
}
public void DFS(int n) {
if (n == 0) {
return;
} else {
DFS(n / 2);
System.out.print(n % 2 + " ");
}
}
}
// 결과 : 1 1 0 1
Java
복사
10진수를 2진수로 변환하기 위해서는 아래 그림과 같이 2로 나누고 나머지를 누적해야 한다. 이때도 스택을 사용하면 쉽게 아래에서부터 나머지를 표시할 수 있다.
팩토리얼
public class Factorial {
public static void main(String[] args) {
Factorial T = new Factorial();
System.out.println(T.DFS(5));
}
public int DFS(int n) {
if (n == 1) {
return 1;
} else {
return n * DFS(n - 1);
}
}
}
// 결과 : 120
Java
복사
재귀를 1에서 멈추는 것 이외에는 위의 예시들과 동일하게 작동한다. 1에서 멈추는 이유는 팩토리얼은 모든 양의 정수의 곱이기 때문이다.
처음 인자 값으로 5가 들어오면 5 * DFS(4) → 스택에 쌓임, 그 다음 4가 들어오면 4 * DFS(3) → 스택에 쌓임. 이런식으로 반복되어 인자 값이 1이 될 때까지 진행이 되고, 스택이 다 쌓였으면 맨 위의 스택부터 꺼내서 결국 1 * 2 * 3 * 4 * 5 = 120 의 결과를 얻게 된다.
