재귀 알고리즘의 예시와 분석

재귀 알고리즘 분석하기

 재귀 호출을 여러 번 실행하는 순수(genuinely) 재귀의 예시.

package org.study.bohyohshibata;

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
2
3
1
4
1
2

하향식 분석과 상향식 분석

recur(4) 는 아래와 같은 순서대로 실행된다.

1. recur(3)을 실행.
2. 4를 출력.
3. recur(2)를 실행. ‘2’에서 4를 출력하는 것은 1의 실행이 완료된 이후다. 따라서 recur(3)을 먼저 조사한다. 이해하기 쉽도록 아래 그림을 첨부.

 

 위 동작 순서 1번에서 recur(3) 호출 이후에 거치는 과정은 왼쪽 아래로 화살표를 따라 가면되고, 3의 recur(2) 호출 이후에 거치는 과정은 오른쪽 아래로 화살표를 따라 가면 된다. 왼쪽 화살표를 따라 한 칸 아래 상자로 이동하고, 다시 원래 상자로 돌아오면 가운데 네모 안에 숫자를 출력한 뒤, 다시 오른쪽 화살표를 따라 한 칸 아래 상자로 이동. 이와같은 일련의 작업을 반복. ‘-’ 로 표시된 빈상자는 아무것도 하지 않고 돌아간다.

 

 가장 위쪽에 위치한 상자의 메서드를 호출하는 것부터 시작하여 계단식으로 자세히 조사해 나가는 분석 기법을 하향식 분석(top-down analysis)이라고 한다. 그런데 이 그림을 보면 recur(1), recur(2)를 여러 번 호출하고 있다. 여러 번 호출 할 수 있다는 부작용으로 ‘하향식 분석이 반드시 효율적이다’라고 할 수 없다.

 

 위 내용과 대조적으로 아래쪽부터 쌓아 올리며 분석하는 방법이 상향식 분석(bottom-up analysis)이다. recur 메서드는 n이 양수일 때만 실행되므로 recur(1)부터 고려한다.

 

 recur(1)은 아래와 같은 순서로 동작한다.

1. recur(0)을 실행.
2. 1을 출력.
3. recur(-1)을 실행.

 다음 recur(2)의 동작을 실행.

recur(1): recur(0) 1 recur(1) ⇒ ‘1’

recur(2): recur(1) 2 recur(0) ⇒ 1 ‘2’

recur(3): recur(2) 3 recur(1) ⇒ 1 2 ‘3’ 1

recur(4): recur(3) 4 recur(2) ⇒ 1 2 3 1 ‘4’ 1 2