재귀 알고리즘의 비재귀적 표현과 메모화

'재귀 알고리즘의 예시와 분석'의 내용을 살펴봤다. 다음으로 재귀 알고리즘의 비재귀적 표현 방식과 메모화를 확인해본다.

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

 recur 메서드를 비재귀적으로 구현하는 방법을 살펴본다.
우선 '꼬리' 재귀를 제거 하는 방법이 있다. recur(n - 2)는 인수로 n - 2를 전달하여 recur 메서드를 호출한다.

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

 

// 수정 이전의 코드
if (n > 0) {
    recur(n - 1);
    System.out.println(n);
    recur(n - 2); // 꼬리를 제거, n - 2로 업데이트하고 메서드의 시작 지점으로 돌아가야 한다
}

 

// 수정 후의 코드, if 문을 while 문으로 수정
while (n > 0) {
    recur(n - 1);
    System.out.println(n);
    n = n - 2;
}

 

재귀의 제거

 꼬리 재귀와는 달리 앞쪽에서 호출하는 재귀 메서드는 제거하기가 쉽지 않다. n값을 출력하기 전에 recur(n - 1)을 먼저 수행해야 하기 때문이다. 단순히 n값을 n - 1 로 업데이트 하고 메서드의 시작지점으로 돌아간다 로 수정할 수 없다. n이 4인 경우 재귀 호출 recur(3)의 처리가 완료되지 않으면 ‘4’를 잠시 저장해야 한다. 그리고 recur(n - 1)의 처리가 완료된 다음에 n값을 출력할 때는 다음 과정을 따른다.

 

 저장했던 n을 다시 꺼내 그 값을 출력.

값을 ‘잠시’ 저장하기 위해서는 스택이 필요하다. 스택을 이용해 아래와 같이 코드를 수정 할 수 있다.

static void recur(int n) {
    IntStack s = new IntStack(n); // stack을 구현한 class입니다.

    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;
    } 
}
// ... 생략

 

1. n값 4를 스택에 푸시.
2. n값을 하나 줄여 3으로 만듬.
3. continue문에 의해 while 문의 맨 앞으로 돌아감.

위 과정이 반복되고 스택에 4, 3, 2, 1이 쌓이게 된다. 스택에 1을 쌓은 다음 n은 값이 0이 되고 while 문의 맨 앞으로 돌아감. n의 값이 0이므로 앞의 if문은 지나간다. 다음 if 문을 통해 아래 과정이 반복된다.

1. 스택에서 팝한 값 1을 n에 대입.
2. n값 1 을 출력.
3. n값을 2 줄여 -1 로 만듬.
4. continue 문에 의해 while 문의 처음으로 돌아감.

n값이 -1 이므로 다시 뒤쪽의 if 문이 실행되고 스택에서 2가 팝되고 그 값을 출력.

n이 0 이하가 되고 스택이 텅 비면 두 if문은 실행되지 않고 break문에 의해 while문이 종료된다.

 

메모화

 메모화(memoization) 기법을 사용하면 동일한 계산을 반복하지 않고 1회만 수행할 수 있다. 예를들어 recur(3)은 1, 2, 3, 1을 차례로 출력하므로 출력할 문자열 “1\n2\n3\n1”을 메모한다. 다시 recur(3)이 호출되었을 때 메모해 둔 문자열을 화면에 출력하면 중복하여 계산할 필요가 없다.

package org.study.bohyohshibata;

import java.util.Arrays;

public class RecurMemo {
    static String[] memo;
    static int counter = 0;

    static void recur (int n) {
        counter++;
        // 메모된 내용 출력
        if (memo[n + 1] != null) System.out.println("memo: " + memo[n + 1]);
        else {
            if (n > 0){
                recur(n - 1);
                System.out.println("출력: " + n);
                recur(n - 2);
                memo[n + 1] = memo[n] + n + memo[n - 1]; // 메모화
                System.out.println("메모화 : " + memo[n+1]);
            } else {
                System.out.println("실행 1");
                memo[n + 1] = "";
            }
        }
    }

    public static void main(String[] args) {
        int x = 4;
        memo = new String[x + 2];
        recur(x);
        System.out.println("Arrays.toString(memo): " + Arrays.toString(memo));
        System.out.println("count: " + counter);
    }
}

recur 메서드를 호출한 횟수에 대해 처음 버전과 메모화 버전을 비교하면 10단계 쯤에서는 약 14배 가량 차이남. (처음 버전: 287, 메모화 버전: 21)