[JAVA] 재귀 알고리즘 분석(하향식, 상향식 분석)

Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다.

---

재귀 알고리즘을 분석하는 방법은 아래의 두가지가 있다.

• 하향식(top down) 분석 방법
• 상향식(bottom up) 분석 방법

아래의 코드를 바탕으로 하향식과 상향식 분석 방법을 정리하겠다.

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

위 메소드에 파라미터에 4를 넘기면 아래와 같은 결과가 나온다.

 

 

하향식 분석

파라미터에 4를 넘기면 recur 메소드는 아래 과정을 순서대로 실행한다.

• ① recur(3)을 실행
• ② 4를 출력
• ③ recur(2)를 실행

아래의 그림에서 상자는 recur 메서드의 동작을 나타낸다. 전달받은 값이 0 이하면 아무 일도 하지 않으므로 검은색 상자로 표시되어 있다.

출처 : https://velog.io/@jimmy48

위의 그림은 맨 꼭대기에서 왼쪽 화살표를 따라 하나 아래 상자로 이동하고, 다시 원래의 상자로 돌아오면 회색박스의 내용을 출력하고 이어서 오른쪽 화살표를 따라 한 칸 아래 상자로 이동하면서 해석하면 된다.

 

이처럼 가장 위쪽에 위치한 상자의 메소드 호출부터 시작해 계단식으로 자세히 조사하는 분석 기법을 하향식 분석이라고 한다. 그런데 이 그림 안에는 recur(1), recur(2)와 같은 동일한 호출이 여러 번 있다. 꼭대기부터 분석하면 이렇게 같은 메소드의 호출이 여러 번 나올 수 있기 때문에 하향식 분석이 반드시 효율적이라고 말할 수 없다.

 

 

상향식 분석

위쪽부터 분석하는 하향식 분석과는 대조적으로 아래쪽부터 쌓아 올리며 분석하는 방법이 상향식 분석이다.

recur(1)이 수행하는 작업은 아래와 같다.

• ① recur(0)을 실행
• ② 1를 출력
• ③ recur(-1)을 실행

①과 ③은 출력할 내용이 없다 따라서 ②의 1만 출력한다.

 

recur(2)의 수행하는 작업은 아래와 같다.

• ① recur(1)을 실행
• ② 2를 출력
• ③ recur(0)을 실행

이러한 작업을 recur(4)까지 과정은 아래의 그림과 같다.

출처 : https://velog.io/@jimmy48

 

---

그림 출처 : https://velog.io/@jimmy48