자료구조&기본 알고리즘 입문(자바)- 재귀 알고리즘(2)

● 재귀알고리즘 분석
재귀 메서드 recur 메서드와 main 메서드로 구성. 

import java.util.Scanner;
// 유클리드 호제법으로 최대공약수 구하기

class EuclidGCD {
	// 정수 x, y의 최대공약수를 구하여 반환. 
	static int gcd(int x, int y) {
		if (y == 0)
			return x;
		else
			return gcd(y, x % y);
	}

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);

		System.out.println("두 정수의 최대공약수를 구하기.");

		System.out.print("정수를 입력：");	int x = stdIn.nextInt();
		System.out.print("정수를 입력：");	int y = stdIn.nextInt();

		System.out.println("최대공약수는 " + gcd(x, y));
	}
}

recur 메서드는 factorial 메서드나 gcd 메서드와 달리 메서드 안에서 재귀 호출을 2회 실행한다. 
재귀 호출을 여러 회 실행하는 메서드를 순수하게(genuinely) 재귀적이라 하며, 실제 동작은 매우 복잡하다. 
recur 메서드에 매개변수로 4를 전달하면 '1231412'라고 숫자에 한 줄에 한 글자씩 출력하는데,  
여기서 recur 메서드를 하향식과 상향식의 두 방법으로 분석한다. 

 

○하향식 분석
매개변수 n으로 4를 전달하면 recur 메서드는 아래 과정을 순서대로 실행한다. 

1. recur(3)을 실행한다
2. 4를 출력한다
3. recur(2)를 실행한다 

가장 위쪽에 위치한 상자의 메서드 호출부터 시작해 계단식으로 자세히 조사하는 분석 기법을 하향식 분석(top-down analysis)라고 한다. 꼭대기부터 분석하면 같은 메서드의 호출이 여러 번 나올 수 있기 때문에 하향식 분석이 반드시 효율적이다라고 말할 수는 없다. 

 

○상향식분석
위쪽부터 분석하는 하향식 분선과 대조적으로 아래쪽부터 쌓아 올리며 분석하는 방법이 상향식 분석(bottom-up analysis). recur 메서드는 n이 양수일 때만 실행하므로 먼저 recur(1)을 생각해보면, 수행하는 작업은 다음과 같다. 

1. recur(0)을 실행한다
2. 1을 출력한다
3. recur(-1)을 실행한다

여기서 recur(0)과 recur(-1)은 출력할 내용이 없다. 따라서 1만 출력한다. 다음은 recur(2)의 과정이다

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

recur(1)은 1을 출력하고 recur(0)은 출력할 내용이 없다. 전체 과정을 거치면 1과 2가 출력된다. 이 같은 과정을 거치면
recur(4)가 출력된다. 

 

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

○꼬리재귀의 제거
메서드의 꼬리에서 재귀 호출하는 메서드 recur(n-2)라는 말은 '인자로 n-2를 전달하여 recur 메서드를 호출한다'는 의미.  따라서 이 호출은 아래와 같이 바뀔 수 있다 .

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

import java.util.Scanner;
// 꼬리 재귀가 없는 재귀 함수 이해하기

class RecurX1 {
	// 꼬리 재귀를 제거. 
	static void recur(int n) {
		while (n > 0) {
			recur(n - 1);
			System.out.println(n);
			n = n - 2;
		}
	}

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);

		System.out.print("정수를 입력.：");
		int x = stdIn.nextInt();

		recur(x);
	}
}

○재귀의 제거
꼬리 재귀와는 다르게 앞에서 호출한 재귀 메서드의 제거는 변수 n의 값을 출력하기 전에 recur(n-1)을 먼저 수행해야 하기 때문에 쉽지 않다. 재귀 호출 recur(n-1)은 다음과 같이 바꿀 수 있다

n의 값을 n-1로 없데이트하고 메서드의 시작 지점으로 돌아간다 
현재 n의 값을 '잠시' 저장한다
저쟁했던 n을 다시 꺼내 그 값을 출력한다.

재귀 호출을 제거하기 위해서 변수 n의 값을 '잠시' 저장해야한다. 이런 문제를 잘 해결 할 수 있는 데이터 구조가 
스택(stack)이다. 

import java.util.Scanner;
// 꼬리 재귀가 없는 재귀 함수 이해하기

class RecurX2 {
	// 꼬리 재귀를 제거. 
	static void recur(int n) {
		IntStack s = new IntStack(n);

		while (true) {
			if (n > 0) {
				s.push(n);						// n의 값을 푸시
				n = n - 1;
				continue;
			}
			if (s.isEmpty() != true) {			// 스택이 비어 있지 않다면
				n = s.pop();					// 저장하고 있던 스택의 값을 팝
				System.out.println(n);
				n = n - 2;
				continue;
			}
			break;
		}
	}

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);

		System.out.print("정수를 입력.：");
		int x = stdIn.nextInt();

		recur(x);
	}
}

-출처: 자료구조와 함꼐 배우는 알고리즘 입문[자바편] 책 중
http://www.yes24.com/Product/Goods/60547893