[알고리즘-03] 재귀 알고리즘

1. 재귀란?

- 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적(recursive)이라고 함

- 재귀를 효과적으로 사용하면 정의뿐만이 아니라 프로그램도 간결하게 할 수 있음

 

2. 재귀의 사용 예 - 팩토리얼 구하기

1) 재귀적 정의

- 음이 아닌 정수 n의 팩토리얼(n!)은 재귀적으로 정의할 수 있음

 

① 0! = 1
② n > 0이면 n! = n × (n-1)!

 

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

 

2) 재귀 호출(recursive call)

- 위의 코드와 같이 자기 자신과 똑같은 메서드를 호출하는 것

- factorial 메서드 안에서 factorial 메서드를 호출

 

3) 직접 재귀(direct recursive)

- 자신과 같은 메서드를 호출하는 것

자기 자신과 같은 메서드를 호출

 

4) 간접 재귀(indirect recursive)

- 메서드 a가 메서드 b를 호출하고, 다시 메서드 b가 메서드 a를 호출하는 구조

다른 메서드를 통해 자기 자신과 같은 메서드를 호출

 

 

 

3. 재귀 알고리즘 분석

1) 재귀 함수

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) {
    	Scanner stdIn = new Scanner(System.in);
        
        int x = stdIn.nextInt();
        
        recur(x);
    }
}
    

 

- recur 메서드 : 메서드 안에서 재귀 호출을 2회 실행

- 이처럼 재귀 호출을 여러 회 실행하는 메서드를 순수하게(genuinely) 재귀적이라고 함

 

2) 하향식 분석(top down)

recur 메서드의 하향식 분석

- 매개변수 n으로 4를 전달했을 시, 아래 과정을 순서대로 실행

(1) recur(3) 실행

(2) 4를 출력

(3) recur(2) 실행

 

- 하향식 분석(top-down analysis) : 가장 위쪽부터 메서드 호출을 시작해 계단식으로 자세히 조사하는 분석 기법

- 같은 메서드의 호출이 여러 번 나올 수 있기 때문에 하향식 분석이 반드시 효율적이진 않음

3) 상향식 분석(bottom up)

- 상향식 분석(bottom-up analysis) : 가장 아래쪽부터 쌓아 올리며 조사하는 분석 기법

 

- recur(1)의 실행 순서

(1) recur(0) 실행 -> 출력할 내용이 없음

(2) 1 출력

(3) recur(-1) 실행 -> 출력할 내용이 없음

 

- recur(2)의 실행 순서

(1) recur(1) 실행 -> 1을 출력

(2) 2 출력

(3) recur(0) 실행 -> 출력할 내용이 없음

 

.

.

recur 메서드의 상향식 분석

4) 재귀 알고리즘의 비재귀적 표현

- recur메서드를 재귀 호출을 사용하지 않고 구현

 

① 꼬리 재귀(tail recursion)의 제거

static void recur(int n) {
    while (n > 0) {
    	recur(n - 1);
        System.out.println(n);
        n = n - 2;
    }
}

- 꼬리 재귀(tail recursion) : 메서드의 끝에서 실행하는 것

- 메서드의 꼬리에서 재귀 호출하는 메서드 recur(n-2) = 인자로 n-2를 전달하여 recur 메서드를 호출한다

- 즉, n의 값을 n-2로 업데이트하고 메서드의 시작 지점으로 돌아감

 

② 재귀의 제거

static void recur(int n) {
    IntStack s = new IntStack(n);
    
    while(true) {
    	if (n > 0) {
            s.push(n);
            n = n-1;
            continue;
        }
        if (s.isEmpty() != true) {
            n = s.pop();
            System.out.println(n);
            n = n - 2;
            continue;
        }
    }
}

 

 

4. 하노이의 탑

- 하노이의 탑(Towers of Hanoi) : 작은 원반이 위에, 큰 원반이 아래에 위치할 수 있도록 원반을 3개의 기둥 사이에서 옮기는 문제

 

class Hanoi {
    // no개의 원반을 x번 기둥에서 y번 기둥으로 옮김
    static void move(int no, int x, int y) {
        if(no > 1)
            move(no-1, x, 6-x-y);
        System.out.println("원반[" + no + "]을" + x + "기둥에서 " + y + "기둥으로 옮김");
        
        if(no > 1)
            move(no-1, 6-x-y, y);
    }
    
    public static void main(String[] args) {
        move(3, 1, 3);	// 1번 기둥의 3개의 원반을 3번 기둥으로 옮김
    }
}

 

- move 메서드는 3단계를 거침

 

① 바닥 원반을 제외한 그룹(원반[1]~원반[no-1])을 시작 기둥에서 중간 기둥으로 옮김 (재귀 호출)
-> move(no-1, x, 6-x-y)
② 바닥 원반 no를 시작 기둥에서 목표 기둥으로 옮겼음을 출력
③ 바닥 원반을 제외한 그룹(원반[1]~원반[no-1])을 중간 기둥에서 목표 기둥으로 옮김 (재귀 호출)
-> move(no-1, 6-x-y, y)

 

- 기둥 번호는 정수 1,2,3

- 기둥 번호의 합이 6이므로 중간 기둥은 6 - x - y

 

1번 기둥의 3개의 원반을 3번 기둥으로 옮길 때

 

 

 

 

 

 

 

 

참고 - Do it! 자료구조와 함께 배우는 알고리즘 입문 : 자바 편 (저자 : 보요 시바타, 출판 : 이지스 퍼블리싱)