이번 포스팅에서는 재귀 알고리즘을 분석하는 방법을 알아보고
재귀 알고리즘을 비재귀적으로 구현하는 방법을 알아보려고 한다.
먼저 재귀 알고리즘을 분석해보자

재귀 알고리즘 분석

재귀 알고리즘 분석을 위해 하향식 분석과 상향식 분석을 두 방법으로
알고리즘을 분석하는 방법을 살펴보려 한다.

먼저 아래 재귀 알고리즘을 가지고 분석을 해보자

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 sc = new Scanner(System.in);
        
        System.out.print("정수를 입력하세요: ");
        int x = sc.nextInt();
        
        recur(x);
    }
}

사용자에게 정수를 입력받아 recur 메서드를 호출한다. recur 메서드는 내부적으로 자신과 동일한 메서드를 호출하고 있으므로 이는 직접 재귀에 해당한다. 하지만 recur 메서드는 재귀 호출을 2번 하고 있는데 이처럼 여러 번 재귀 호출을 하는 메서드를 순수 재귀라고 한다.

이렇게 구조가 복잡한 재귀 메서드는 좀 더 치밀하게 분석해야한다.
이제 하향식 분석과 상향식 분석 두가지 방식을 이용해 recur 메서드를 분석해보자.

하향식 분석

하향식 분석이란?
가장 위쪽에 위치한 상자의 메서드를 호출하는 것부터 시작하여 계단식으로 조사해 나가는 기법.

매개변수 n에 4를 전달하면 recur 메서드는 아래와 같은 동작을 한다.

recur(4)

• recur(3)을 실행.
• 4를 출력
• recur(2)를 실행.

위 이미지에서 recur(3) 호출 이후에 거치는 과정은 왼쪽 아래 화살표로
recur(2)호출 이후 거치는 과정은 오른쪽 아래 화살표로 따라가면 된다.
위의 이미지의 재귀 호출을 차근차근 따라가 보면 굉장히 많은 단계를 거쳐야 함을 알 수 있다.
또한 같은 호출이 여러번 있기 때문에 효율적이라고 볼 수 없다.

상향식 분석

상향식 분석이란?
위쪽에서부터 분석하는 하향식 분석과 다르게 아래쪽부터 쌓아 올리면서 분석하는 방법.

위에서 작성한 recur(); 메서드를 가지고 상향식 분석을 해보자
recur 메서드는 n이 양수일 때만 실행되므로 recur(1) 부터 생각해보자

recur(1)

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

여기서 recur(0)과 recur(-1)은 출력할 내용이 없기 때문에 1만 출력한다.
다음으로 recur(2)를 살펴보자.

recur(2)

• recur(1)을 실행.
• 2를 출력
• recur(0)을 실행.

recur(2)의 경우는 1과 2를 출력한다. 조금 더 상향식 분석을 쉽게 나타내면 아래와 같다.

recur(-1) : 아무것도 하지 않음.
recur(0) : 아무것도 하지 않음.

---

recur(1) / recur(0) / recur(-1) -> 1 출력
recur(2) / recur(1) / recur(0) -> 1, 2 출력
recur(3) / recur(2) / recur(1) -> 1, 2, 3, 1 출력
recur(4) / recur(3) / recur(2) -> 1, 2, 3, 1, 4, 1, 2 출력

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

위에서 예시로 사용한 recur 메서드를 재귀 호출을 사용하지 않고 비재귀적으로 구현해보자.

꼬리 재귀의 제거

recur 메서드의 꼬리 재귀 호출 메서드 recur(n-2)는 '인수로 n-2를 전달하여 recur 메서드를 호출한다.' 는 의미다. 따라서 이 호출은 다음처럼 변경할 수 있다.

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

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

이런식으로 꼬리 재귀를 쉽게 제거할 수 있다.
하지만 꼬리 재귀와 다르게 앞쪽 재귀는 제거하기가 쉽지 않다.

변수 n을 출력하기 전 n-1을 수행해야 하기 때문에 꼬리 재귀를 제거한 방식으로는 할 수 없다.

예를들어 n이 4인경우 재귀 호출 recur(3)의 처리가 완료되지 않으면, n값인 '4'를 저장해야 한다.
그리고 recur(n-1)의 처리가 완료된 다음에 n값을 출력할 때 저장했던 값을 꺼내 출력한다.

위 사항을 참고하여 앞의 재귀를 제거하여 완전히 비재귀적으로 만들어보자.

static void recur(int n) {
	Stack<Integer> s = new Stack<>();

	while(true) {
    	if(n > 0) {
        	s.push(n);                  // 들어온 정수를 스택에 푸시하여 저장
            n = n - 1 ;                 // n - 1 수행
            continue;                   // 다시 while 처음으로 이동하여 n이 0이 될때까지 반복
		}
        if(s.isEmpty() != true) {       // 스택이 비어있지 않다면 (이미 위 조건에서 스택에 넣었기 때문에 있을거임)
        	n = s.pop();                // 스택에 저장된 값들을 pop하여 출력
            System.out.println(n);
            n = n - 2;                  // 그리고 꼬리 재귀 부분을 n = n - 2를 수행
            continue;
		}
		break;
	}
}

예제에서는 Stack을 직접 구현한 IntStack 클래스를 사용하였지만, 이미 우리는 Stack을 구현해보았기 때문에, Java에서 제공하는 Stack 클래스를 이용해서 작성하였다.

위 코드와 같이 스택을 사용하여 앞에 있는 재귀 호출을 비 재귀적으로 바꿀 수 있다.
자세한 코드의 흐름은 주석에 적어 두었다.