[재귀]02. 재귀 함수와 호출 트리
이번 포스트에서는 재귀 함수가 어떻게 호출되면서 동작하는지 살펴보자. 재귀함수 동작이 처음에 와닿지 않는 경우가 많은데 재귀를 이해하기 위해서는 메모리에서 함수들이 어떻게 동작하는지 손으로 스택을 직접 그려가면서 공부하는 방법이 제일 좋다.
함수의 호출과 메모리
함수들을 호출되면서 stack 영역에 해당 함수만을 위한 메모리 공간을 확보하고 함수의 동작을 처리한다. 함수에서 또 다른 함수를 호출하는 경우 기존 함수의 메모리 공간 위에 새로운 함수를 위한 메모리 공간을 쌓게(stack)된다. 이때 기존의 메모리는 동작을 일시 정지하는 pending 상태가 되고 맨 위의 메모리 공간만 활성화 상태가 된다.
그리고 메서드가 return 되면 점유하고 있던 메모리 공간을 반환하고 기존에 pending 되어있던 메서드가 다시 동작을 재개한다.
잠깐 퀴즈! 그럼 StackOverflowError이란 어떤 의미일까 고민해보자.
재귀 호출과 파라미터
재귀 함수는 일반적으로 동작에 필요한 요소들을 파라미터로 전달해준다. 이때 전달되는 파라미터의 종류에 따라 주의해야할 사항들에 대해 생각해보자.
java에서 메서드의 파라미터는 call by value로 전달되는데 이때의 value는 원본 데이터의 "값"이다. 만약 레퍼런스 타입인 경우 이 값이 "참조값"임을 주의해야 한다.
기본형 변수
먼저 기본형의 파라미터는 메서드가 호출될 때마다 매번 새롭게 생성된다. 다음 메서드의 동작을 직접 손으로 그려가며 k 값의 변화에 주목해서 실제 출력되는 값들을 알아보자.
public static void recur(int k) {
if (k == 0) {
System.out.println("재귀 종료");
return;
}
System.out.println("Before: " + k);
recur(k - 1);
System.out.println("After: " + k);
}
public static void main(String[] args) {
recur(3);
}
 |
# 실행 결과 Before: 3 Before: 2 Before: 1 재귀 종료 After : 1 After : 2 After : 3 |
이제 다 그려보았다면 다시 질문의 시간이다.
이 코드에서는 총 몇 개의 k가 동작했을까?
정답은 총 4개이다. k는 로컬변수로 선언되었으므로 한번 메서드가 호출될 때 메모리에 등장해서 그 메서드 내에서는 단지 하나만 존재한다. 출력되는 k가 6개라고 다른 생각을 하면 안된다.
재귀를 호출하는 코드를 아래와 같이 변경해보면 어떻게 될까?
| System.out.println("Before: " + k); recur(k - 1); System.out.println("After: " + k); |
System.out.println("Before: " + k); recur(--k); System.out.println("After: " + k); |
재귀 호출에서 사용되는 k 값이 오염되어버렸기 때문에 이제 Before와 After의 값이 다르게 출력된다. 즉 동일한 상태의 k를 사용하지 못하게 되는 것이다! 이런 실수를 방지하기 위해서 문제의 크기로 사용되는 파라미터에는 final 키워드를 붙여주는 것도 좋은 습관이다. 그러면 값 자체를 변경하려는 경우 compile error가 발생한다.
public static void recur(final int k) { . . . }
참조형 변수
참조형 변수는 객체의 참조값을 전달한다. 즉 매번 새로운 객체를 만드는 것이 아니라 힙에 생성된 객체를 공유해서 사용한다.
다음 함수의 동작에 대한 메모리를 역시 직접 손으로 그려보자.
public static void recur3(int k, int n, int[] arr) {
if (k == n) {
return;
}
System.out.println(k + " : " + arr[0]);
recur3(k + 1, n, arr);
System.out.println(k + " : " + arr[0]);
}
 |
#실행결과 0 : 0 1 : 0 2 : 0 2 : 0 1 : 0 0 : 0 |
만약 출력 결과에서 배열의 내용을 k의 값과 동일하게 처리하려면 어떻게 해주면 될까?
하나의 배열을 재귀 호출에서 공유하고 있으므로 최고 정점까지 올라간 후 내려오는 과정에서 다시 초기화가 필요하다.
arr[0] = k;
System.out.println(k +" : "+arr[0]);
recur3(k+1, n, arr);
arr[0] = k;
System.out.println(k + " : " + arr[0]);
멤버 변수의 사용
간단한 멤버 변수의 활용
멤버 변수를 활용 할 때도 객체를 참조하는 것 처럼 재귀 함수 입장에서는 공유해서 사용된다. 다음의 코드 동작을 손컴파일링해서 그려보자. 최종적인 cnt는 얼마가 출력될까?
int N = 3;
int cnt;
public void recUseMember(int k) {
if (k == N) {
cnt++;
return;
}
recUseMember(k + 1);
}
recUseMember(0);
System.out.println(cnt);
결과를 보면 약간 싱겁긴 하다.
만약 위의 모든 멤버들이 static 이라면 어떻게 될까?
cnt나 n 값을 class area에서 참조하는 것 빼고는 동일하다. 일반적으로 알고리즘 문제 풀이에는 객체를 잘 사용하지 않고 static 멤버들을 사용하는 편이다.
좀 더 복잡하게 가보면..
위의 예가 너무 쉬웠다면 다음의 동작 결과는 어떨까?
static int N=3;
static int cnt2;
public void reUseMemMulti(int k) {
if (k == N) {
cnt2++;
System.out.println(cnt2);
return;
}
reUseMemMulti(k + 1);
reUseMemMulti(k + 1);
}
reUseMemMulti(0);
System.out.println("최종: " + cnt2);
열심히 그려봤으면 결과가 잘 나왔겠지만 재귀 함수 내에서 다음 재귀를 부르는것 하나 하나는 새로운 가지를 발생시킨다. 위의 코드에서는 reUseMemMulti를 두번씩 부르고 있기 때문에 각 재귀의 단계마다 두 개의 가지가 생성된 것을 알 수 있다. 만약 4방 탐색을 재귀로 진행한다면 당연히 4개의 가지가 생길 것이다.
반환값 활용
반환값 활용
재귀 함수에서는 다음 메서드의 반환값을 이전 메서드에서 사용하는 형태로 처리된다. factorial을 구하는 함수를 살펴보고 손컴파일링 해보자.
public static long factorial(int k) {
if(k==1) {
return 1;
}
return k * factorial(k-1);
}
factorial(4);
좀 더 복잡하게
이제는 거꾸로 아래와 같은 함수 호출 트리를 구성하려면 어떻게 재귀를 작성해야 하는지 고민하고 작성해보자.
public int reReturn(int k) {
if (k == N) {
return 1;
}
return reReturn(k + 1) + reReturn(k + 1);
}
System.out.println(reReturn(0));