알고리즘 자신을 사용하여 정의된 알고리즘
비재귀적 알고리즘과 대비됨
보류된 재귀호출을 위한 변수들에 관련된 저장/복구
→ 컴퓨터에 의해 자동적으로 수행
Alg Factorial(n)
input integer n
output factorial of integer n
1. if(n==1) {base case}
return 1
2. else {recursion case}
return n*Factorial(n-1)
아래 규칙을 따르지 않으면 재귀적으로 문제 해결 불가
규칙을 따르지 못한 경우 아래 문제를 일으킬 수 있음
아래 코드는 재귀적으로 하노이 탑을 해결하는 내용을 담고있다.
원판을 옮기는 것은 from말뚝, to말뚝의 출력으로 표현했다.
#include <stdio.h>
void move(int n, char from, char to){
printf("n=%d\tmove from %c to %c\n", n, from, to);
}
void hanoi(int n, char from, char aux, char to){
if(n==1){
move(n, from, to);
} else {
hanoi(n-1, from, to, aux);
move(n, from, to);
hanoi(n-1, aux, from, to);
}
}
int main(){
int n;
scanf("%d", &n);
hanoi(n, 'A', 'B', 'C');
return 0;
}
위 프로그램은 hanoi
함수를 재귀적으로 호출한다.
이 함수의 재귀케이스를 살펴보면 아래의 절차를 관찰할 수 있다.
아래 파트 1~3 내용을 재귀적으로 호출하여 전체 문제를 해결한다.
파트1. from말뚝의 위쪽 n-1개를 aux말뚝으로 옮긴다.
파트2. from말뚝의 가장 아래(가장 큰) 1개를 to말뚝으로 옮긴다.
파트3. aux말뚝에 있는 n-1개 전부를 to 말뚝으로 옮긴다.
n=3인 경우 출력은 아래와 같다.
n=1 move from A to C 파트1
n=2 move from A to B 파트1
n=1 move from C to B 파트1
n=3 move from A to C ---파트2
n=1 move from B to A ------파트3
n=2 move from B to C ------파트3
n=1 move from A to C ------파트3