재귀
자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적이라고 한다.
팩토리얼 구하기
import java.io.IOException;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws IOException{
System.out.println(factorial(5));
}
static int factorial(int n) {
if (n > 0)
return n * factorial(n-1);
else
return 1;
}
}직접 재귀와 간접 재귀
직접 재귀 : 자신과 같은 메서드를 호출
간접 재귀 : 다른 메서드를 통해 자기 자신과 같은 메서드를 호출(메서드 A가 메서드 B를 호출하고, 다시 메서드 B가 메서드 A를 호출하는 구조)
유클리드 호제법
두 정수의 최대공약수를 재귀적으로 구하는 방법
두 정수 x,y의 최대공약수를 gcd(x,y)로 표기
import java.io.IOException;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws IOException{
System.out.println(gcd(22,8));
}
static int gcd(int x, int y) {
if (y == 0)
return x;
else
return gcd(y, x % y);
}
}하노이의 탑
작은 원반이 위에, 큰 원반이 아래에 위치할 수 있도록 원반을 3개의 기둥 사이에서 옮기는 문제
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class Hanoi {
static void move(int no, int x, int y) {
if(no > 1)
move(no - 1, x, 6 - x - y);
System.out.printf("원반 %d를 %d기둥에서 %d기둥으로 옮김\n",no,x,y);
if(no > 1)
move(no -1 , 6-x-y, y);
}
}
public class Main {
public static void main(String[] args) throws IOException{
Hanoi ha = new Hanoi();
ha.move(3, 1, 3);
}
}
no는 옮겨야 할 원반의 개수, x는 시작 기둥의 번호, y는 목표 기둥의 번호
기둥 번호를 정수 1,2,3으로 나타낸다. 기둥 번호의 합이 6이므로 시작 기둥 , 목표 기둥이 어느 기둥이더라도
중간 기둥은 6-x-y로 구할 수 있다.
move 메서드
- 바닥 원반을 제외한 그룹(원반[1] ~ 원반[no - 1]을 시작 기둥에서 중간 기둥으로 옮긴다.
- 바닥 원반 no를 시작 기둥에서 목표 기둥으로 옮겼음을 출력한다.
- 바닥 원반을 제외한 그룹(원반[1] ~ 원반[no - 1]을 중간 기둥에서 목표 기둥으로 옮긴다.
8퀸 문제
서로 공격하여 잡을 수 없도록 8개의 퀸을 8 * 8 체스판에 놓으세요.
- 각 열에 퀸을 1개만 배치합니다.
- 각 행에 퀸을 1개만 배치합니다.
가지뻗기
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class QueenB {
static int[] pos = new int[8]; //각 열의 퀸의 위치
//각 열의 퀸의 위치를 출력합니다.
static void print() {
for (int i =0; i< 8; i++)
System.out.printf("%2d", pos[i]);
System.out.println();
}
//i열에 퀸을 놓습니다.
static void set(int i) {
for(int j=0; j<8; j++) {
pos[i] = j; //퀸을 j행에 배치합니다.
if(i == 7) //모든 열에 배치합니다.
print();
else
set(i+1); //다음 열에 퀸을 배치합니다.
}
}
}
public class Main {
public static void main(String[] args) throws IOException{
QueenB qu = new QueenB();
qu.set(0); //0열에 퀸을 배치합니다.
}
}모든 조합을 나열하는 프로그램
i열에 놓인 퀸의 위치가 j행이면 pos[i]의 값을 j로 한다.
(pos[1]의 값 4는 1열의 퀸이 4행에 배치된 상태)
하노이의 탑이나 8퀸 문제처럼 문제를 세분하고 세분된 작은 문제의 풀이를 결합해 전체 문제를 풀이하는 기법을
분할 정복법이라고 한다.
분기 한정법
가지 뻗기로 퀸을 배치하는 조합을 나열할 수는 있지만 8퀸 문제의 답을 얻을 수는 없습니다.
다음은 앞에서 분기를 한정하기 위해 정했던 규칙입니다.
[규칙 2] 각 행에서 퀸을 1개만 배치합니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class QueenBB {
static boolean[] flag = new boolean[8]; //각 행에 퀸을 배치했는지 체크
static int[] pos = new int[8]; //각 열의 퀸의 위치
//각 열의 퀸의 위치를 출력합니다.
static void print() {
for(int i = 0; i < 8; i++)
System.out.printf("%2d", pos[i]);
System.out.println();
}
//i열의 알맞은 위치에 퀸을 배치합니다.
static void set(int i) {
for(int j = 0; j < 8; j++) {
if(flag[j] == false) { //j행에는 퀸을 아직 배치하지 않았다면
pos[i] = j;
if(i == 7)
print();
else {
flag[j] = true;
set(i + 1);
flag[j] = false;
}
}
}
}
}
public class Main {
public static void main(String[] args) throws IOException{
QueenBB qu = new QueenBB();
qu.set(0); //0열에 퀸을 배치합니다.
}
}j행에 퀸을 배치하면 flag[j]의 값을 true로 하고, 배치되지 않은 상태의 값은 false로 한다.
0열에 퀸을 배치하고 flag[0]의 값을 true로 변경한다.
그런 다음 set메서드를 재귀적으로 호출
이렇게 호출한 set메서드는 다음 1열에 퀸을 배치
재귀 호출한 set(i + 1)메서드 실행이 끝나면 퀸이 j행에서 제거되었기 때문에 flag[j]에는 false를 대입
8퀸 문제를 푸는 프로그램
대각선 방향
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class EightQueen {
static boolean[] flag_a = new boolean[8]; //각 행에 퀸을 배치했는지 체크
static boolean[] flag_b = new boolean[15]; //대각선 방향으로 퀸을 배치했는지 체크
static boolean[] flag_c = new boolean[15]; //대각선 방향으로 퀸을 배치했는지 체크
static int[] pos = new int[8]; //각 열의 퀸의 위치
static void print() {
for(int i =0; i<8; i++)
System.out.printf("%2d", pos[i]);
System.out.println();
}
static void set(int i) {
for(int j = 0; j<8; j++) {
if (flag_a[j] == false && //가로(j행에)에 아직 배치하지 않았습니다.
flag_b[i + j] == false && // 대각선 /에 아직 배치하지 않았습니다.
flag_c[i - j + 7] == false) { //대각선 \에 아직 배치하지 않았습니다.
pos[i] = j;
if(i == 7)
print();
else {
flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = true;
set(i + 1);
flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = false;
}
}
}
}
}
public class Main {
public static void main(String[] args) throws IOException{
EightQueen eq = new EightQueen();
eq.set(0); //0열에 퀸을 배치합니다.
}
}가장 긴 대각선의 값은 7이다