06_재귀 알고리즘

• 재귀(recursive): 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의되는 것

       → 병합 정렬, 퀵 정렬, 이진검색트리 등에도 사용됨

 

•  재귀 호출(recursive call): 자기 자신과 똑같은 메서드를 호출

① 팩토리얼

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

 

② 유클리드 호제법 : 두 정수의 최대공약수 구하는 알고리즘

직사각형을 동일한 크기의 정사각형으로 완전히 채울 때, 이렇게 만들 수 있는 정사각형의 가장 긴 변의 길이

(= 최대공약수)

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

- 두 정수 중 큰 값을 작은 값으로 나누었을 때, 나누어떨어지는 가장 작은 값 → 최대공약수

- 나누어 떨어지지 않으면, 나누어 떨어질 때까지 재귀적으로 반복

 

• 재귀 알고리즘 분석

- 하향식 분석: 가장 먼저 실행되는 메서드 호출부터 시작해서 계단식으로 자세히 분석하는 기법

- 상향식 분석: 아래쪽부터 쌓아 올리며 분석하는 기법

  ex) n이 양수일 때만 실행하는 recur() 메서드가 있다면,

        recur(1) 일 때 어떤 작업을 하는지, recur(2) 일 때 어떤 작업을 하는지⋯⋯ 쭉- 분석

• 재귀 함수 호출 과정 → 스택 push(), pop() 과 비슷함

 

③ 하노이의 탑 

- 가장 큰 원반 제외 나머지를 그룹으로 묶으면 → 총 3단계로 완료

1) 그룹을 시작 기둥 → 중간 기둥으로 이동

2) 가장 큰 원반을 시작 기둥 → 목표 기둥으로 이동

3) 그룹을 중간 기둥 → 목표 기둥으로 이동

→ 이 과정을 계속 반복하면 문제 해결 가능

// no개의 원반을 x번 기둥에서 y번 기둥으로 옮김
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);
}

 

④ 8퀸 문제 : 서로 공격하여 잡을 수 없도록 8개의 퀸을 8 x 8 체스판에 놓기

- 퀸은 체스판의 어떤 지점으로든 여덟 방향으로 직선 이동이 가능함

1) 각 열에 퀸을 1개만 배치

2) 각 행에 퀸을 1개만 배치

3) 대각선(/) 방향에 퀸을 1개만 배치

4) 대각선(\) 방향에 퀸을 1개만 배치

    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_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;
                }
            }
        }
    }