재귀 알고리즘의 분석

재귀 알고리즘을 분석할 때 항상 두서 없이 대충 머리로 찍찍 굴리면서 알고리즘을 분석했었다.

그러다보니 아~~~~~ 대충 이렇게 작동하나? 라는 생각만 들고 정확하게 재귀를 이해하지 못하거나 과거의 수학적 지식을 통해 이해하는 등 정확하게 재귀를이해하지 못했다.

 

그렇기에 재귀 알고리즘을 분석하는 2가지 방법을 학습했다.

 

분석해야할 코드

public class Recur {

    static void recur(int num) {
        if (num > 0) {
            recur(num - 1);
            System.out.println("num = " + num);
            recur(num - 2);
        }
    }

    public static void main(String[] args) {
        recur(4);
    }
}

num  값이 클 경우는 너무 많은 처리를 하나하나 해야한다. 그렇기에 적당히 4로 잡았다.

 

하향식 분석

가장 위에 호출한 메서드부터 호출해서 하나하나 계단처럼 내려가는 분석 기법

생각보다 글씨가 나쁘지 않군

가장 먼저 recur(4)를 분석

그이후 recur(3) 분석

....

이렇게 단계적으로 분석해 나가는 것이다.

 

이렇게 분석 시 많은 중복이 발생한다.

위의 사진만 보더라도 num=2 ,1 일때 여러번 중복이 발생하는 것을 알 수 있다.

그렇기에 효율적이지 않을 수 있다.

 

상향식 분석

아래쪽부터 쌓아 올리면서  분석하는 방법

나는 이런 분석 방식이 추후 DP로 넘어가는 과정에서 자연스럽게 더 좋은 분석 방식이라고 생각한다.

 

recur(1) -> 1

recur(2) -> (recur(1)( =1) 2 

recur(3) -> recur(2) 3 recur(1)

...

 

이런 방식으로 진행된다.

자 여기서 위의 결과를 저장한다면?

DP의 동작을 알 수 있다.

 

 

재귀의 분석은 천천히 집중해서 해보면 이해할 수 있다.

 

그렇기 때문에 귀찮다고 눈으로만 보는 행위 같은 경우는 삼가하는 것이 좋아보인다.