5. 재귀 알고리즘
재귀란?
어떤 사건이 자기 자긴을 포함하고 있거나 자기 자신을 사용하여 정의하고 있을 때를 재귀적이라고 한다.
간단한 예시를 통해 재귀 알고리즘을 알아보자
대표적인 예시로 팩토리얼 구하는 알고리즘, 유클리드 호제법이 있다.
팩토리얼 알고리즘 코드
import java.util.Scanner;
public class Factorial {
// 음이 아닌 정수 n의 팩토리얼값을 반환
static int factorial(int n) {
if(n > 0)
return n * factorial(n - 1);
else
return 1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("정수를 입력하세요: ");
int x = sc.nextInt();
System.out.println(x + "의 팩토리얼은 " + factorial(x) + "입니다.");
}
}
factorial 메서드가 반환하는 값
- 매개변수 n에 전달받은 값이 0보다 클 때 : n * factorial(n - 1)
- 매개변수 n에 전달받은 값이 0보다 크지 않을 때 : 1
이 메서드는 조건 연산자를 사용하면 한 줄로 나타낼 수도 있다.
return (n > 0) ? n * factorial(n - 1) : 1;
재귀 호출은 처음에 보면 어느 순간부터 이해가 안될 것이다. 하지만 코드를 그려보면서 흐름을 이해한다면 빠르게 이해할 수 있다.
factorial 메서드는 n - 1의 팩토리얼 값을 구하기 위해 다시 factorial 메서드를 호출한다. 이러한 메서드 호출 방식을 재귀 호출(recursive call)이라고 한다.
팩토리얼을 재귀 메서드 호출 없이 메서드를 작성해 보면 아래와 같은 코드가 만들어진다.
import java.util.Scanner;
public class Factorial2 {
static int factorial(int n) {
int total = 1;
for(int i = 1; i <= n; i++) {
total *= i;
}
return total;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("정수를 입력하세요: ");
int x = sc.nextInt();
System.out.println(x + "의 팩토리얼은 " + factorial(x) + "입니다.");
}
}
직접 재귀와 간접 재귀
직접 재귀 : 자신과 동일한 메서드를 호출하는 것
간접 재귀 : 메서드 a가 b를 호출하고, 다시 b가 a를 호출하는 구조
유클리드 호제법
y = 0 일 때 최대공약수 : x
y != 0 일 때 최대공약수 : gcd(x % y)
큰 값을 작은 값으로 나눴을 때 나눠 떨어지면 그 작은 값이 최대 공약수이다.
알고리즘 코드
import java.util.Scanner;
public 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 sc = new Scanner(System.in);
System.out.println("두 정수의 최대공약수를 구합니다.");
System.out.print("정수를 입력하세요: ");
int x = sc.nextInt();
System.out.print("정수를 입력하세요: ");
int y = sc.nextInt();
System.out.println("최대공약수는 " + gcd(x, y) + "입니다.");
}
}알고리즘은 간단하게 나타낼 수 있다.
그렇다면 gcd도 재귀 메서드를 호출하지 않고 작성한다면 어떻게 만들어질까?
아래처럼 코드를 짤 수 있다.
import java.util.Scanner;
public class EuclidGCD2 {
// 정수 x, y의 최대공약수를 구하여 반환
static int gcd(int x, int y) {
int tmp;
while(y != 0) {
tmp = x;
x = y;
y = tmp % y;
}
return x;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("두 정수의 최대공약수를 구합니다.");
System.out.print("정수를 입력하세요: ");
int x = sc.nextInt();
System.out.print("정수를 입력하세요: ");
int y = sc.nextInt();
System.out.println("최대공약수는 " + gcd(x, y) + "입니다.");
}
}
배열 a의 모든 요소의 최대공약수를 구하는 메서드도 작성해 보겠다.
import java.util.Scanner;
public class EuclidGCD3 {
// 정수 x, y의 최대공약수를 구하여 반환
static int gcd(int x, int y) {
if (y == 0)
return x;
else
return gcd(y, x % y);
}
// 배열 a의 모든 요소의 최대공약수를 구하여 반환
static int gcdArray(int[] a) {
int result = a[0];
for (int i = 1; i < a.length; i++) {
result = gcd(result, a[i]);
}
return result;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("배열 요소들의 최대공약수를 구합니다.");
System.out.print("배열의 크기를 입력하세요: ");
int n = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
System.out.print("정수[" + i + "]: ");
arr[i] = sc.nextInt();
}
System.out.println("최대공약수는 " + gcdArray(arr) + "입니다.");
}
}
재귀 알고리즘 분석
아래의 코드를 봐보자.
import java.util.Scanner;
public 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);
}
}변수 x에 정수 4를 입력하면 어떤 결과가 나올지 생각해 보자.
recur 메서드는 factorial이나 gcd 메서드와 달리 메서드 안에서 재귀 호출을 2회 실행한다. 이처럼 재귀 호출을 여러 번 실행하는 메서드를 순수 재귀라고 한다. 이 순수 재귀의 실제 동작은 매우 복잡하다.
recur 메서드를 하향식과 상향식 두 방법으로 분석해 보면 다음과 같다.
하향식 분석
recur(4)
1) recur(3)을 실행한다.
2) 4를 출력한다.
3) recur(2)를 실행한다.
recur(3)
1) recur(2)을 실행한다.
2) 3을 출력한다.
3) recur(1)을 실행한다.
위와 같이 recur 메서드를 재귀적으로 먼저 호출한 후 완료되면 그 뒤에 2)에 있는 값을 출력하게 되는 구조이다.
그림으로 보면 더 이해가 빠르게 될 것이다.
'왼쪽 화살표를 따라 한 칸 아래 상자로 이동하고, 다시 원래 상자로 돌아오면 ■안의 값을 출력한 뒤, 다시 오른쪽 화살표를 따라 한 칸 아래 상자로 이동한다'를 하나로 이어진 일련의 작업으로 생각하면 된다. 이렇게 하나의 작업을 완료해야 한 칸 위의 상자로 돌아갈 수 있게 된다.
상향식 분석
위쪽부터 분석하는 하향식 분석과는 대조적으로 아래쪽부터 쌓아 올리며 분석하는 방법
recur 메서드는 n이 양수일 때만 실행되므로 먼저 recur(1)을 생각해 보자.
recur(1)
1) recur(0)을 실행한다.
2) 1을 출력한다.
3) recur(-1)을 실행한다.
recur(2)
1) recur(1)을 실행한다.
2) 2을 출력한다.
3) recur(0)을 실행한다.
이런 구조를 반복하여 recur(4)까지 쌓아 올리면 1 -> 2 -> 3 -> 4 -> 1 -> 2가 출력되게 된다.
메모화
recure 메서드는 실행 과정에서 같은 계산을 여러 번 반복해 수행한다. n값이 커지면 반복하는 계산 횟수는 더욱 늘어나게 된다.
하지만 메모화 기법을 사용하면 동일한 계산을 반복하지 않고 1회만 수행할 수 있다.
어떤 문제(recur 메서드가 전달받는 n)에 대한 답을 구할 경우 그것을 메모해 둔다.
ex) recur(3)은 1, 2, 3, 1을 차례로 출력하므로 출력할 문자열 "1\n2\n3\n1"을 메모한다. 이후 recur(3)가 다시 호출될 경우 메모해 둔 문자열을 화면에 출력하면 중복하여 계산할 필요가 없어진다.
메모화를 사용하여 구현한 프로그램
import java.util.Scanner;
public class RecurMemo {
static String[] memo;
static void recur(int n) {
if(memo[n + 1] != null)
System.out.println(memo[n + 1]);
else {
if(n > 0) {
recur(n - 1);
System.out.println(n);
recur(n - 2);
memo[n + 1] = memo[n] + n + "\n" + memo[n - 1]; // 메모화
}else {
memo[n + 1] = ""; // 메모화 : recur(0)과 recure(-1)은 빈 문자열
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("정수를 입력하세요: ");
int x = sc.nextInt();
memo = new String[x + 2];
recur(x);
}
}
하노이의 탑
쌓아 놓은 원반을 최소 횟수로 옮기기 위한 알고리즘
작은 원반이 위에, 큰 원반이 아래에 위치하도록 샇은 원반을 3개의 기둥 사이에서 옮기는 문제이다.
모든 원반은 크기가 다르고 처음에는 모든 원반이 이 규칙에 맞게 첫 번째 기둥에 쌓여 있다. 이 상태에서 모든 원반을 세 번째 기둥으로 최소의 횟수로 옮기면 된다. 원반은 1개씩만 옮길 수 있고 큰 원반을 작은 원반 위에 쌓을 수는 없다.
알고리즘 코드
import java.util.Scanner;
public class Hanoi {
// no개의 원반을 x번 기둥에서 y번 기둥으로 옮김
static void move(int no, int x, int y) {
if(no > 1)
move(no - 1, x, 6 - x - y);
System.out.printf("원반[%d]을(를) %d번 기둥에서 %d번 기둥으로 옮김\n", no, x, y);
if(no > 1)
move(no - 1, 6 - x - y, y);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("하노이의 탑");
System.out.print("원반의 개수: ");
int n = sc.nextInt();
move(n, 1, 3); // 1번 기둥에 쌓인 n개의 원반을 3번 기둥으로 옮김
}
}
6 - x - y를 한 이유 : 기둥 번호를 정수 1, 2, 3으로 나타내고, 기둥 번호의 합이 6이므로 시작 기둥, 목표 기둥이 어느 기둥이더라도 중간 기둥은 6 - x - y로 구할 수 있기 때문이다.
1) 바닥의 원반을 제외한 그룹(원반[1] ~ 원반[no - 1])을 시작 기둥에서 중간 기둥으로 옮깁니다.
2) 바닥의 원반 no를 시작 기둥에서 목표 기둥으로 옮깁니다.
3) 바닥의 원반을 제외한 그룹을 중간 기둥에서 목표 기둥으로 옮깁니다.
이 3단계를 거쳐 no개의 원반을 옮길 수 있다.
1) 과 3) 단계는 재귀 호출을 사용해서 실현한다.