1. 재귀란?

어떤 사건이 자기 자신을 포함하고 있거나 또는 자기 자신을 사용하여 정의하고 있을 때 이를 재귀적(recursive)이라고 합니다.

가. 직접 재귀와 간접 재귀

• 직접재귀: 자신과 동일한 메서드를 호출하는 것
• 간접재귀: 메서드 a가 메서드 b를 호출하고, 다시 메서드 b가 메서드 a를 호출하는 구조

나. 팩토리얼

• 0!=1
• n>0이면 n!=n*(n-1)!
• 삼항연산자로 구현하기

int factorial(int n) {
	return (n>0)?factorial(n-1):1;
}

다. 유클리드 호제법

유클리드 호제법(euclidean_algorithm)은 두 수의 최대 공약수를 구하는 알고리즘입니다. 일반적으로 최대 공약수를 구하는 방법은 소인수분해를 이용한 공통된 소수들의 곱으로 표현할 수 있지만 유클리드 호제법은 좀 더 간단한 방법을 제시합니다.

유클리드 호제법의 핵심이론

유클리드 호제법을 수행하려면 먼저 MOD 연산을 이해하고 있어야 합니다. MOD 연산이 최대 공약수를 구하는 데 사용하는 핵심 연산이기 때문입니다.

• MOD 연산 기능: 두 값을 나눈 나머지를 구하는 연산 예제: 10 MOD 4 = 2 ⇒ 10 % 4 = 2
  

MOD 연산을 이해하면 다음과 같은 3단계로 유클리드 호제법을 구현할 수 있습니다.

• MOD 연산으로 구현하는 유클리드 호제법
  1. 큰 수를 작은 수로 나누는 MOD 연산을 수행
  2. 앞 단계에서의 작은 수와 MOD연산 결괏값(나머지)으로 MOD 연산을 수행
  3. 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택

유클리드 호제법의 원리 이해하기

라. 확장 유클리드 호제법

유클리드 호제법의 목적이 두 수의 최대 공약수를 구하는 것이라면 확장 유클리드 호제법의 목적은 방정식의 해를 구하는 것입니다.

확장 유클리드 호제법의 핵심 이론

확장 유클리드 호제법에서 해를 구하고자 하는 방정식은 다음과 같습니다.

해를 구하고자 하는 방정식
ax + by = c (a, b, c, x, y는 정수)

이때 위 방정식은 c%gcd(a,b)=0인 경우에만 정수해를 가집니다. 다시말해 c가 a와 b의 최대 공약수의 배수인 경우에만 정수해를 가지며, 이는 ax+by=c가 정수해를 갖게 하는 c의 최솟값이 gcd(a, b)라는 것을 의미합니다.

• 확장 유클리드 호제법의 원리 이해하기
  

5x+9y=2일 때 이 식을 만족하는 정수 x, y 구하기

• 5x+9y가 정수해를 갖게하는 c의 최솟값이 gcd(5,9)라는 것을 적용하여 식을 다시 놓습니다.
  gcd(5,9)=1이므로 5x+9y=1로 식을 다시 놓고 다음 단계를 진행합니다.

• a, b로 유클리드 호제법을 반복 실행하며 몫, 나머지를 저장하며, 반복은 나머지가 0이 되면 중단합니다.

  
  

• 반복으로 구한 나머지와 몫을 이용해 거꾸로 올라가며 x=y’, y=x’-y’*q를 계산합니다.

• x’는 이전 x, y’는 이전 y를 의미하고, q는 현재 보고 있는 몫을 의미합니다.

• 이때 처음 시작하는 x, y는 이전 값이 없으므로 각각 1, 0으로 지정하여 역계산을 진행합니다.
  

이렇게 재귀 방식으로 알아낸 최종 x, y는 ax+by=gcd(a,b)를 만족합니다.
그리고 c/gcd(a, b)=K를 가정하면 최초 방정식의 해는 Kx, Ky로 간단히 구할 수 있습니다.

2. 재귀 알고리즘 분석

재귀 알고리즘을 분석하는 방법을 살펴보고 재귀 알고리즘을 비재귀적으로 구현하는 방법을 알아보겠습니다.

가. 재귀 알고리즘 분석하기

import java.util.Scanner;

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 scan = new Scanner(System.in);

		System.out.println("정수 입력: ");
		int x = scan.nextInt();

		recur(x);
	}
}

// 출력: 한 줄에 하나씩 '1231412'

순수재귀

: 메서드 안에서 재귀 호출을 여러 번 실행하는 매서드

이렇게 구조가 복잡한 재귀 메서드는 세밀하게 분석해야합니다.

하향식 분석

매개변수 n에 4를 전달하면 recur 메서드는 다음 과정을 순서대로 실행합니다.

아래에서 4가 출력되려면 위의 실행이 완료되어야 합니다. 따라서 recur(3)을 먼저 조사해야합니다. 이해하기 쉽도록 아래 그림을 통해 설명하도록 하겠습니다.

• 각각의 상자는 recur 메서드의 동작을 나타냅니다. 또, 전달받은 값이 0이하면 recur메서드는 아무일도 하지 않으므로 빈 상자로 표시됩니다.

• 이렇게 가장 위쪽에 위치한 상자의 메서드를 호출하는 것부터 시작하여 계단식으로 자세히 조사해 나가는 분석 기법을 하향식 분석이라고 한다.

• 그런데 이 그림을 보면 recur(1), recur(2)를 여러 번 호출하고 있습니다. 꼭 대기(top)부터 분석하다보면 잉렇게 같은 메서드를 여러 번 호출 할 수 있기 때문에 ‘하향식 분석이 반드시 효율적이다’라고 말할 수는 없습니다.

상향식 분석

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

여기서 위의 recur(0)과 마지막의 recur(-1)은 출력할 내용이 없습니다. 따라서 recur(1)은 1만 출력합니다.

최상단의 recur(1)은 1을 출력하고 마지막의 recur(0)은 출력할 내용이 없습니다. 따라서 전체 과정을 거치면 1과 2가 출력됩니다.

이 작업을 recur(4)까지 쌓아 올려 설명한 내용은 다음과 같습니다.

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

recur메서드를 재귀 호출을 사용하지 않고 비재귀적으로 구현하는 방법 살펴보기

꼬리 재귀의 제거

메서드의 꼬리에서 재귀 호출하는 메서드 recur(n-2)는 ‘인수로 n-2를 전달하여 recur메서드를 호출한다’는 의미입니다. 따라서 이 호출은 다음처럼 바꿀 수 있습니다.

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

import java.util.Scanner;

class Recur {
	// 재귀함수
	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 scan = new Scanner(System.in);

		System.out.println("정수 입력: ");
		int x = scan.nextInt();

		recur(x);
	}
}

재귀의 제거

꼬리 재귀와는 달리 앞쪽에서 호출하는 재귀 메서드는 제거하기 쉽지 않습니다. 왜냐하면 변수 n값을 출력하기 전에 recur(n-1)을 먼저 수행해야하기 때문입니다. 그래서 재귀호출 recur(n-1)을 다음처럼 바로 바꿀 수 없습니다.

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

예를 들어 n이 4인 경우 재귀 호출 recur(3)의 처리가 완료되지 않은면 n값인 ‘4’를 저장해야한다.

• 현재 n값을 ‘잠시’ 저장한다. 그리고 recur(n-1)의 처리가 완료된 다음에 n값을 출력할 때는 다음 과정을 따르게 됩니다.

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

이런 재귀 호출을 제거하기 위해서는 변수 n값을 ‘잠시’ 저장해야한다는 사실을 알았습니다.
이때 이런 문제를 잘 해결할 수 있는 데이터 구조가 스택입니다.