재귀 알고리즘의 분석
먼저 아래의 프로그램을 통해 재귀 알고리즘을 분석하는 두 가지 방법을 알아볼 것이다.
다음 포스트에서는 goto 문과 스택을 활용하여 재귀 알고리즘을 비재귀적으로 구현하고, 메모이제이션을 활용해 효율을 높여볼 것이다.
#include <stdio.h>
void recur(int n){
if(n>0){
recur(n-1);
printf("%d\n", n);
recur(n-2);
}
}
void main(){
int x;
printf("정수를 입력 : ");
scanf("%d", &x);
recur(x);
}
--------------------------
결과
정수를 입력 : 4
1
2
3
1
4
1
2
상향식 분석
상향식 분석은 아래쪽부터 쌓아 올리며 분석하는 방법이다.
recur 함수는 n이 양수일 때만 생각하므로 recur(1)부터 조사한다.
| 1. recur(0)을 실행 -> 아무 일도 없음
recur(1) | 2. 1를 출력
| 3. recur(-1)를 실행 -> 아무 일도 없음
이에 따라 계속 상향식으로 분석해보자면 아래와 같다.
| 1. recur(1)을 실행 -> 1을 출력
recur(2) | 2. 2를 출력
| 3. recur(0)를 실행 -> 아무 일도 없음
| 1. recur(2)을 실행 -> 1을 출력 후 2를 출력
recur(3) | 2. 3를 출력
| 3. recur(1)를 실행 -> 1을 출력
| 1. recur(3)을 실행 -> 1 2 3 1을 출력
recur(4) | 2. 4를 출력
| 3. recur(2)를 실행 -> 1 2를 출력이런식으로 recur(4)까지 쌓아올리면서 어떤 결과값이 나오는지 분석하는 방법이다.
앞에서부터 전부 다 확인해야해 비효율적이라 생각할 수 있겠지만, 이 예제에서 recur(2)처럼 같은 함수의 호출이 여러 번 나오는 경우에는 상향식 분석이 더욱 효율적일 수도 있다.
하향식 분석
하향식 분석은 가장 위쪽에 위치한 함수의 호출부터 시작해 계단식으로 자세히 조사해가는 분석 기법이다.
| 4-1. recur(3)을 실행
recur(4) | 4-2. 4를 출력
| 4-3. recur(2)를 실행
여기서 1의 실행이 완료되어야 2가 실행된다. 따라서 recur(3)을 먼저 조사해야한다.
| 3-1. recur(2)을 실행
recur(3) | 3-2. 3를 출력
| 3-3. recur(1)를 실행
recur(3)에서도 1이 먼저 실행되어야 하므로 쭉쭉 조사해보겠다.
| 2-1. recur(1)을 실행
recur(2) | 2-2. 2를 출력
| 2-3. recur(0)를 실행 -> 아무 일도 없음
| 1-1. recur(0)을 실행 -> 아무 일도 없음
recur(1) | 1-2. 1를 출력
| 1-3. recur(-1)를 실행 -> 아무 일도 없음1-1과 1-3에서는 아무 출력도 없으므로 가장 먼저 출력되는건 1-2의 1이다
그 후 2-1이 끝났으니 2-2가 진행되고 2가 출력될 것이다.
그럼 2-3이 진행될 차례지만 아무 일도 없다. 여기까지 총 1, 2가 출력될 것이다.
그럼 3-1이 끝났으니 3-2의 3이 출력된다.
3-2가 끝났으니 3-3이 진행되고 즉 1-1과 1-2와 1-3을 조사하고 1이 출력된다는 사실을 확인한다.
그러면 지금까지 총 1, 2, 3, 1이 출력된다는 사실을 확인했고 이제 4-2로 넘어갈 차례이므로 4를 출력한다.
마지막 4-3만 확인하면 끝이난다.
2-1을 조사한 결과 1-1 1-2 1-3으로 가고 1이 출력된다는 사실을 알게되었다.
2를 출력하고
다음엔 아무일도 일어나지 않는다.
즉 1, 2, 3, 1, 4, 2가 차례대로 출력된다는 사실을 확인하였다.
이 사실을 확인하고자 코드를 아래와 같이 보완하여 출력해보았다.
#include <stdio.h>
void recur(int n){
printf("recur(%d) ", n); //함수 호출시에 recur(n) 출력
if(n>0){
recur(n-1);
printf("%d\n", n);
recur(n-2);
}
}
void main(){
int x;
printf("정수를 입력 : ");
scanf("%d", &x);
recur(x);
}
------------------------------
결과
정수를 입력 : 4
recur(4)recur(3)recur(2)recur(1)recur(0)1
recur(-1)2
recur(0)3
recur(1)recur(0)1
recur(-1)4
recur(2)recur(1)recur(0)1
recur(-1)2
recur(0)이처럼 하향식 분석은 하나의 작업이 완료되어야 한 칸 위의 단계로 돌아갈 수 있다. 이러한 점 때문에 하향식 분석이 반드시 효율적이라고 말할 수는 없다.
위와 같은 예제에서는 recur(1)나 recur(2)의 결과를 점차 알아가며 조사하는 상향식 분석이 더욱 효율적이다.
이렇게 재귀적 분석에 대해 알아보았다.
다음 포스트에서는 같은 함수를 활용해 스택을 통한 비재귀적 표현과 메모리제이션을 활용한 최적화까지 다뤄보겠다.
