[자료구조 입문] 05. 재귀 알고리즘

재귀 (recursive)

팩토리얼 구하기

package 자료구조입문.재귀;

public class Factorial {

static int facto(int x) { //재귀로 구현

if(x > 1) {

return x * facto(x-1);

}

return 1;

}

static int facto2(int x) { // 삼항연산자 + 재귀 구현

return (x > 1) ? x * facto(x-1) : 1;

}

public static void main(String[] args) {

System.out.println(facto2(5));

}



}

직접재귀와 간접재귀

• 직접재귀 : A - A - A 형태로 자신과 동일한 메서드를 호출하는것
• 간접재귀 : A - B - C 형태로 메서드 A 가 B를 호출, B가 C를 호출하는 것

유클리드 호제법

• 두수의 최대공약수를 구하는 방법
• 두수를 직사각형의 두변의 길이라고 생각하고 문제를 풀어보자. 직사각형을 정사각형으로 빈틈없이 채운다. 이렇게 만들어지는 정사각형가운데 가장 긴변의 길이를 구한다.
  

위와 같은 방법을 재귀적으로 반복하여 최대공약수를 구하게 된다.

즉,

• y=0 일때 , 최대공약수 : x
• y!=0 일때, 최대공약수 : gcd(y, x % y)

package 자료구조입문.재귀;

public class 유클리드호제법 {


static int gcd(int x, int y) {

if(y==0) {

return x;

}

return gcd(y, x % y);

}

public static void main(String[] args) {
int x = 31;

int y = 3;

System.out.println("최대공약수 : " + gcd(x,y));
}

}

재귀 알고리즘의 분석

하향식 분석

• top-down Analysis - 가장 위쪽의 메서드부터 아래로 하나씩 분석해 나가는 방법
• 같은 호출이 여러번 있는 경우, 효율이 떨어지는 경우가 있다.

상향식 분석

• bottom-up Analysis - 가장 아래쪽부터 쌓아올리며 분석을 진행하는 방법

---

순수 재귀 (genuinely) - 아래와 같이 재귀 호출을 여러번 실행하는 것.

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) {
        recur(4);
    }

}

순서

1. recur(3) 실행
2. 4를 출력
3. recur(2) 실행

하노이의 탑

하노이의 탑은 쌓아놓은 원반을 최소의 횟수로 옮기기위한 알고리즘이다.
나무위키 바로가기
하노이의탑 게임

문제를 풀기위해서 큰문제를 작은문제로 나누어서 해결하는 방식을 사용해야한다.

package 자료구조입문.재귀;

public class TowersOfHanoi {
	
	static int count;
	
	public static void move(int n, int x, int y) {
		
		if(n > 1) {
			move(n-1, x, 6-x-y); //6-x-y 를 통해 중간기둥을 찾을수있음.
		}
		
		System.out.printf("%d 크기 원반을 %d기둥에서 %d기둥으로 이동 \n", n, x, y);
		count ++;
		
		if(n > 1) {
			move(n-1, 6-x-y, y);
		}
		
	}
	
	public static void main(String[] args) {
		
		int n = 3;
		count = 0;
		
		move(n, 1, 3);
		System.out.println("이동횟수 : " + count);
	}
}

 

 

 

8퀸 문제

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

규칙을 세워서 문제에 접근을 해야하는데 64칸의 체스판에 1개의 퀸을 배치하는 경우의수는 64이고 다음은 63 다음은 62... 이런식으로 조합이 만들어지므로

64 x 63 x 62 x ... 57

이라는 엄청나게 큰 숫자의 조합이 만들어지게 된다.

그래서 2가지 규칙을 추가해보자.

1. 각 열에 퀸을 1개만 배치할수있다.
2. 각 행에 퀸을 1개만 배치할수있다.

이렇게 하노이의탑이나 8퀸문제처럼 문제를 작게 쪼개서 세분화된 작은 문제를 결합하여 문제를해결하는 방법을 분할정복법(Divide and Conquer) 라고 한다. - 퀵정렬, 병합정렬 등

1,2 번 규칙에 마지막 규칙을 더해보자.
행과 열이 겹치지 않게 구현하였으므로 마지막으로 대각선방향을 생각한다.
대각선방향은 오른쪽위에서 왼쪽아래, 왼쪽위에서 오른쪽아래로 향하는 두가지 경우를 생각해야한다.

대각선은 다음과같이 2가지 경우로 생각된다.

static boolean[] flagLTR = new boolean[15];
static boolean[] flagRTL = new boolean[15]; 

 

코드

package 자료구조입문.재귀;

public class Queen8 {

    static int[] pos = new int[8]; //각열에 존재하는 퀸의 위치
    static boolean[] flag = new boolean[8]; //각행에 퀸을 이미 배치했는지 확인
    static boolean[] flagLTR = new boolean[15]; // \ 방향 대각선으로 퀸을 배치했는지 확인 (Left To Right)
    static boolean[] flagRTL = new boolean[15]; // / 방향 대각선으로 퀸을 배치했는지 확인    (Right To Left)

    static void print() {
        for(int i=0; i<pos.length; i++) {
            System.out.printf("%2d", pos[i]);
        }
        System.out.println();
    }

    static void set(int col) {
        for(int row=0; row<pos.length; row++) {

            if(flag[row] == false && 
                flagLTR[row + col] == false && 
                flagRTL[col - row + 7] == false ) {
                    pos[col] = row;
                    if(col == 7) {
                    print();
                    }else {
                        flag[row] = flagLTR[col + row] = flagRTL[col - row + 7] = true;
                        set(col+1);
                        flag[row] = flagLTR[col + row] = flagRTL[col - row + 7] = false;
                }
            }
        }
    }

    public static void main(String[] args) {
        set(0);

    }
}