5-2. 재귀 알고리즘 분석(Analysis on Recursive Algorithm)

: factorial 메서드 혹은 gcd 메서드와 달리 메서드 안에서 재귀 호출을 여러 회 실행하는 메서드를 순수하게(genuinely) 재귀적이라고 하며, 실제 동작은 매우 복잡하다. 이러한 복잡한 구조를 가진 재귀 메서드를 보다 전략적으로 분석하기 위해 하향식, 상향식의 두 방향으로 분석한다.

 

 

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

 

 

 

 

 

・하향식 분석(top down)

 

-매개변수 n으로 4를 전달한 경우

[1] recur(3) 실행
[2] 4를 출력
[3] recur(2) 실행

 

[1]로 인해 재귀 호출이 실행되고, 모든 재귀 호출을 수행한 뒤 [2]가 실행된다. 하나의 재귀 작업을 상자에 비유한다면, 빈 상자에 도달하게 되었을 때, 비로소 한 칸 위의 상자로 돌아가며 차례로 모든 작업을 완료해야 한다.

 

꼭대기(top)부터 분석하면 같은 메소드의 호출이 여러 번 나올 수 있기 때문에(ex. recur(1), recur(2)) 하향식 분석은 반드시 효율적이라고는 할 수 없다.

 

 

 

 

 

・상향식 분석(bottom up)

: 아래쪽부터 쌓아 올리며 분석

 

 

 

 

 

・재귀 알고리즘의 비재귀적 표현

-꼬리 재귀의 제거

 

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

 

맨 마지막 재귀 호출을

n의 값을 n - 2로 업데이트하고 메서드의 시작 지점으로 돌아간다.

로 바꾸어 메서드의 끝에서 실행하는 꼬리 재귀를 제거했다.

 

 

 

 

 

-재귀의 제거

 

앞에서 호출한 재귀 메서드의 제거는 쉽지 않다.

1. n의 값을 n - 1로 업데이트하고 메서드의 시작 지점으로 돌아간다.
2. 현재 n의 값을 '잠시' 저장한다. //(Stack 사용)
3. 저장했던 n을 다시 꺼내 그 값을 출력한다.

 

앞에서 호출한 재귀 메서드의 구현은 꼬리 재귀보다 복잡하다.

 

 

 

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