재귀 알고리즘

직접 재귀: 자신과 같은 함수를 호출

간접 재귀: 함수 a가 함수 b를 호출하고 다시 함수 b가 함수 a를 호출하는 구조

 

• 순차곱셈 (팩토리얼)

int factorial(int n){
    if(n > 0)
    	return  n * factorial(n-1);
    else
    	return 1;
}

 

• 유클리드 호제법(최대공약수)

int gcd(int x, int y){
    if(y == 0)
    	return x;
    else return gcd(y, x%y);
}

 

• 하노이의 탑

작은 원반이 위에, 큰 원반이 아래에 위치할 수 있도록 원반을 3개의 기둥 사이에서 옮기는 문제.
모든 원반은 규칙에 맞게 첫 번째 기둥에 쌓여 있고,
이 상태에서 모든 원반을 세 번째 기둥으로 최소의 횟수로 옮겨야 함.

 

해결 방법: 맨 밑의 원반을 제외한 위의 원반들을 '그룹'이라고 할 때 

        1. 그룹을 시작 기둥에서 중간 기둥으로 옮김

        2. 맨 밑의 원반을 목표 기둥으로 옮김

        3. 그룹을 중간 기둥에서 목표 기둥으로 옮김

 

#include <stdio.h>

void move(int no, int x, int y) { /*no: 옮겨야 할 원반 개수, x: 시작 기둥 번호, y: 목표 기둥 번호 */
	if (no > 1) move(no - 1, x, 6 - x - y); /* 각 기둥 번호는 1, 2, 3*/
	printf("원반[%d]를(을) %d 기둥에서 %d 기둥으로 옮김\n", no, x, y);
	if (no > 1) move(no - 1, 6 - x - y, y);
}

int main(void) {
	int n; //원반 개수
	printf("하노이의 탑\n원반 개수: ");
	scanf_s("%d", &n);
	move(n, 1, 3);

	return 0;
}

 

• 8퀸 문제

서로 공격하여 잡을 수 없도록 8개의 퀸을 체스판에 놓으세요.

해결 방법:

        1. 각 행에는 1개의 퀸만 놓을 수 있음 : flag_a[8]

        2. 각 대각선 /에는 1개의 퀸만 놓을 수 있음 : flag_b[15]   // j행 i열인 값은 flag_b[i+j]

        3. 각 대각선 \에는 1개의 퀸만 놓을 수 있음 : flag_c[15]   // j행 i열의 값은 flag_c[i-j+7]

-> 3개의 flag값이 모두 0인 곳에만 퀸을 배치함으로써 불필한 분기를 줄임

 

#include <stdio.h>

int flag_a[8];
int flag_b[15];
int flag_c[15];
int pos[8]; //각 열에서 퀸의 위치

void print(void) {
	int i;
	for (i = 0; i < 8; i++)
		printf("%2d", pos[i]);
	putchar('\n');
}

void set(int i) {
	int j;
	for (j = 0; j < 8; j++) {
		if (!flag_a[j] && !flag_b[i + j] && !flag_c[i - j + 7]) {
			pos[i] = j;
			if (i == 7) print(); //모든 열에 배치함
			else {
				flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = 1;
				set(i + 1);
				flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = 0;
			}
		}
	}
}

int main(void) {
	int i;
	for (i = 0; i < 8; i++) flag_a[i] = 0;
	for (i = 0; i < 15; i++) flag_b[i] = flag_c[i] = 0;
	set(0);

	return 0;
}