재귀 알고리즘 분석
import java.util.Scanner;
public class recur {
static void recur(int n){
if(n > 0){
recur(n - 1);
System.out.println(n);
recur(n - 2);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("정수를 입력하세요 : ");
int x = sc.nextInt();
recur(x);
}
}Do it 자료구조와 함께 배우는 알고리즘 입문 p170 실습 5-3문제를 참조해봤다.
재귀(1)에서 다룬 factorial(), gcd()와는 다르게 메서드 안에서 재귀 호출을 2회 실행하고 있는 문제이다.
이처럼 재귀 호출을 여러번 실행하는 메서드를 순수(genuinely)재귀라 한다.
메서드 자체만으로는 단순해 보이지만, 실제로 재귀호출이 되는 과정을 생각만으로 알아보기는 꽤나 복잡하다.
이때, 두 가지 분석방법이 있다.
하향식 분석
- recur(4) 호출 시
- recur(3)을 실행
- 4를 출력
- recur(2)를 실행
단순하게 메서드 호출 시 3단계 작업을 수행한다. 그러나 실제는 1번에서 메서드를 호출하고 작업이 완료되어야
다음 2번 출력 시 수행되며 3번에 메서드가 완료되어야 비로소 처음 호출 된 recur(4) 메서드는 종료가 된다.
실제 recur(4) 메서드가 호출 된 후부터 끝나기까지 일어나는 작업들은 아래(↓)와 같다.
이처럼 초기 메서드가 호출되는 시점부터하여 재귀 호출되는 메서드를 순차적으로 내려가며 어떤 식으로 작업이 이루어지는지를 분석해 나가는 기법을 하향식 분석이라 한다.
이때 위 그림에서 확인할 수 있듯이 내려가면서 분석할 때 recur(1), recur(0)과 같이 여러차례 호출되는 것을 확인할 수 있다. 그렇기에 반드시 효율적인 기법이라고 말하기는 어려울 수 있다.
상향식 분석
하향식 분석과 대조적으로 아래쪽부터 쌓아 올리며 분석하는 기법을 상향식 분석이라 한다.
간단히 예시 코드를 정리해보면
- 재귀 호출이 일어나기 위해서는 매개변수로 넘어 온 값이 n > 0 조건을 만족해야한다.
- 1번 조건이 만족할 경우 현재 매개변수 n에 대해서 recur(n -1) , recur(n - 2) 2번의 재귀호출이 발생한다.
- 재귀 호출이 일어날 수 있는 가장 작은 매개변수는 n = 1일 때이다. 이때 발생할 수 있는 재귀호출은 recur(0), recur(-1) 이다
- 3번에서 두 번의 재귀호출은 1번 조건을 만족하지 않기에 추가적으로 재귀 호출은 일어나지 않고 호출된 메서드가 종료된다.
- 최종적으로 recur(1)은 n값 호출인 1을 출력하고 끝이난다.
- 다음으로 recur(1)을 호출한 recur(2)에서는 1을 출력하고 돌아올 시 현재 n값이 2를 출력한다. 그리고 recur(n-2)를 수행한다. 그러나 이는 recur(0)이므로 1번 조건에 따라 아무 일도 없게된다.
- 여기까지 정리하면 recur(2)를 호출할 시 1 , 2를 출력하는 일을 하게된다. 그리고 호출한 recur(3)으로 돌아간다.
간단하게 순서로 정리해봤듯이 상향식 분석은 최하위부터 하나씩 쌓아올리며 분석하는 기법이다. 이렇게 분석할 경우 하향식 분석때와는 다르게 중복해서 호출하는 메서드가 없게된다.
간단하게 recur(3)은 recur(2) , recur(1)을 재귀 호출할 것이며, 이는 이미 어떠한 결과가 나타날지 선행으로 분석했기에 추가적으로 분석할 필요가 없게된다. 그리고 자신이 받은 매개변수 값 n인 3을 출력하는 일을 할 것이다.
재귀 알고리즘의 비재귀적 표현
기존의 recur() 메서드를 재귀함수를 사용하지 않고 비재귀적으로 구현하는 방법
꼬리 재귀(메서드에서 수행되는 2번째 재귀)의 제거
recur(n - 2) 부분 다시말하면 현재 매개변수에서 2를 뺀 값으로 메서드를 다시 시작
static void recur(int n){
while(n > 0){
recur(n - 1);
System.out.println(n);
n = n - 2;
}
}간단하게 하향식으로 한번 살펴보자
- 처음으로 recur(4)가 호출되었다고 가정하자.
- 반복문 조건에 따라 recur(3)이 호출될 것이다.
- 다음으로 반복문 조건에 따라 recur(2)가 호출된다.
- 다음으로 반복문 조건에 따라 recur(1)이 호출된다.
- 다음으로 반복문 조건에 따라 recur(0)이 호출된다.
- 반복문 조건에 맞지 않으므로 반복문 내부를 처리하지 않고 메서드가 종료된다.
- recur(0) 메서드 종료로 recur(1)에서는 1을 출력한다. 그리고 현재 n은 1 이므로 n - 2를 해서 n이 -1이되고 반복문을 빠져나오면서 메서드가 종료된다.
- recur(1) 종료로 인해 recur(2) 메서드에서 n= 2이므로 2를 출력하고 현재 값에서 2를뺀다. n = 0 이므로 메서드가 종료된다.
- recur(2) 종료로 recur(3)에서 3이 출력되고 n - 2로 n = 1이 되므로 반복문을 수행한다 . recur(0)을 실행한다. 결과는 위에서 알 수 있듯이 반복문 조건에 위해서 내부 작업을 수행하지 않고 종료된다.
- 현재 n 값이 1이기에 1을 출력하고 n - 2 를 하여 -1이 되므로 반복문을 나오며 종료된다.
- recur(4)로 돌아와 현재 n값을 출력하고 n을 2 감소시킨다.
- recur(2)를 호출하며 내용은 위 호출 당시와 같다. 즉 1 , 2를 출력하고 끝이난다.
- n값이 2에서 2를 빼므로 0이되어 반복문을 빠져나온다. 최종적으로 모든 호출된 메서드가 종료된다.
이렇게 작성할 경우 n <= 2 경우 recur(n - 2)를 호출할 필요가 없음에도 기존에는 무조건 호출을 했어야 했지만, 꼬리재귀를 제거함으로 불필요한 메서드 호출을 줄일 수 있게 된다.
재귀의 제거
꼬리부분 재귀의 경우는 반복문 내부에서 마지막 부분에서 n값을 줄이는 것이기에 지장이 없으나 처음으로 수행되는 재귀 호출의 경우는 다르다.
이 값을 n = n -1로 변경 시 이후 작업처리에 영향을 미치게 된다.
예를들어 매개변수 값이 4라고 했을경우 해당 메서드 출력부분에서는 4가 아닌 3으로 출력이 되는 문제가 생긴다.
이 부분을 해겨하기 위해 스택을 사용해볼 수 있다. 스택은 LIFO구조이며, 이를 활용하여 현재 매개변수의 값을 임시로 저장하고 필요할 때 꺼내서 사용해보자.
static void recur(int n){ // n = 4라고 가정
IntStack s = new IntStack(n);
while(true){
// recur(n - 1)
if(n > 0){
s.push(n);
n--;
continue;
}
if(s.isEmpty() != true){
n = s.pop();
System.out.println(n);
n = n - 2;
continue;
}
break;
}
}- 메서드를 처음으로 호출하면 매개변수 n에 값이 들어온다. n = 4라고 가정해보자
- 값을 임시로 담을 스택을 하나 만든다. 여기서는 스택을 공부하면서 만들어본 스택을 사용했다.
- 재귀 호출에서를 생각해보면 먼저는 recur(n - 1)이 반복적으로 호출되면서 매개변수 값이 0이 될 떄까지 호출되었다.그 부분을 생각해보면 n 값은 1개씩 줄어서 전달되고 호출된 메서드들은 매개변수에 값을 갖고 있다. 4 -> 3 -> 2 - > 1 -> 0 이런식으로말이다. 그리고 0인 시점에는 아무것도 수행하지 않았다. 그럼 여기서는 4~1까지 스텍에 순서대로 저장이 되었다 n = 0이 되는 시점에는 조건문을 수행하지 않고 다음 조건문을 수행한다. 스택이 비어있지 않으면 pop을하여 값을 얻고 출력후 n - 2를 수행한다. 자세한 부분은 위에 내용들과 동일하다.
그림을 통해서 보면, 직접적으로 재귀 호출을 하지 않고 조건문과 반복문, 스택을 통하여 메서드를 1회만 호출함으로 문제를 해결할 수 있다.
다만, 비재귀적으로 구현함으로 단순했던 코드가 점점 재귀 호출 부분들을 처리하기 위해 추가적으로 요구된다. 반면 반복문 내부적으로 처리함으로 재귀 호출을 하면서 발생할 수 있는 비용을 절감할 수 있다.
메모화
기존에 재귀를 사용할 경우 같은 메서드를 반복적으로 수행해야했다.
n의 값이 증가한다면 반복 수행 횟수도 당연히 증가하게된다.
이때 메모화 기법을 사용하면 메서드를 1회만 수행하고 수행했을 때 결과를 메모해두었다. 동일한 작업을 수행해야할 경우 메모해 놓은 결과를 활용할 수 있다.
public class RecurMemo {
static String[] memo;
static void recur(int n){
if(memo[ n + 1 ] != null) // 이미 재귀 호출되어 결과를 얻었으면 결과를 출력
System.out.print(memo[n + 1]);
else{ // 호출된 적이 없을 시 결과를 얻기위해 수행
if(n > 0){
recur(n - 1);
System.out.println(n);
recur(n - 2);
memo[n + 1] = memo[n] + n + "\n" + memo[n - 1]; //recur(n-1) , recur(n-2) 호출 시 결과를 메모
}else
memo[n + 1] = "";
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("정수를 입력하세요 : ");
int x = sc.nextInt();
// 재귀 호출을 할 경우 최종적으로 n = -1까지 수행하고 조건에 의해 더 이상 호출되지 않는다.
// n = -1 -> 0번 인덱스 / n = 0 -> 1번 인덱스
memo = new String[x + 2];
recur(x);
}
}문제에 따라 재귀 호출 시 무엇을 저장해야할지는 다를 수 있다. 여기서는 재귀 호출 시 결과적으로는 현재 자신의 n값을 출력하는 것이 결과이기에 String[] 배열을 이용해서 각 단계에 맞게 결과들을 메모해두었다 이후 같은 같은 n값에 대해서는 반복 호출할 것 없이 이미 결과를 메모했기에 메모한 위치에서 값을 얻어서 사용할 수 있게 된다.
아래 표에서와 같이 메모화 기법을 사용할 경우 n값에 따라 얼마만큼의 메서드 호출수의 차이가 발생하는지 확인해볼 수 있다. 메서드 호출을 한다는 것인 JVM 호출 스택 영역을 사용해야하는 것이기에 성능, 비용등도 생각해볼 수 있을 것 같다
**공부 후 생각을 정리해보면 재귀호출도 결과적으로는 메서드를 호출하고 메서드가 호출이 되면 처음부터 다시 수행하게된다. 반복문을 생각해볼 수 있다. 그리고 조건 및 작업을 모두 처리했으면 호출한 쪽으로 다시 돌아와서 남은 작업을 수행한다. 이 부분에서 많이 헷갈리고 딱 코드만 놓고 볼 때 직관적으로 받아들이기는 많이 어려웠다. 그래서 그림으로도 많이 그려보고 분석 기법도 여러가지 문제를 만들어 풀어봤다. 흐름을 잘 따라갈 수 있는 연습이 필요할 듯 싶다. 물론 재귀 알고리즘 뿐만 아니라 프로그램이 수행되는 흐름을 잘 따라갈 수 있는 것도 '실력'이라 생각한다 결론은 그래도 어렵다ㅜㅜ
'알고리즘&자료구조 > 재귀 알고리즘' 카테고리의 다른 글
| 재귀(4) - 8-Queen problem (2) | 2022.09.24 |
|---|---|
| 재귀(3) - 하노이의 탑 (0) | 2022.09.24 |
| 재귀(1) (0) | 2022.09.18 |