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

예제 재귀 알고리즘

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

 

 

꼬리 재귀의 제거

메서드의 꼬리에서 재귀 호출하는 메서드 recure(n-2)는 아래처럼 바꿀 수 있다.

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

 

코드로 표현하자면 이렇게 할 수 있다.

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

 

재귀의 제거

앞에 재귀를 제거하기 위해서는 n의 값을 잠시 저장해야 할 필요가 있다.  n을 출력하기 전에 recur(n-1)을 실행해야 하기 때문이다.

이때 문제를 해결하기 위해서는 스택이 필요하다.

 static void recur(int n) {
    Stack<Integer> stack = new Stack<>();
    while (true) {
        if (n > 0) {
            stack.push(n);
            n = n - 1;
            continue;
        }
        if (!stack.isEmpty()) {
            n = stack.pop();
            System.out.println(n);
            n = n - 2;
            continue;
        }
        break;
    }
}