오늘은 재귀 알고리즘의 개념과 재귀에 대해 분석을 해보자.
📘 재귀란?
어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적(resursive)이라고 한다.
예를 들어, 무한으로 존재하는 자연수를 재귀적 정의(resursive definition)로 표현할 수 있다.
- 1은 자연수이다.
- 자연수 n의 바로 다음 수도 자연수이다.
이렇듯 재귀를 효과적으로 사용하면 이런 정의뿐 아니라 프로그램도 간결하게 할 수 있다.
📘 팩토리얼
재귀의 사용 예로 첫번째 팩토리얼(factorial)을 알아보자.
음이 아닌 정수 n의 팩토리얼(n!)은 아래처럼 재귀적으로 정의할 수 있다.
- 0! = 1
- n > 0 이면 n! = n x (n - 1)!
다음은 이 정의를 이용하여 코드로 살펴보자.
✏ 팩토리얼 코드
import java.util.Scanner;
public class Factorial {
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("팩토리얼 값 : " + factorial(x));
}
}factorial 메서드는 매개변수 n에 전달받은 값이 0보다 크면 n * factorial(n - 1)을 반환하고, 그렇지 않으면 1을 반환한다.
factorial 메서드를 사용하여 재귀 호출을 이용해 매개변수의 값을 전달받아 자신을 재호출하여 값을 얻어내게 된다.
✏ 직접 재귀와 간접 재귀
factorial 메서드는 그 내부에서 factorial 메서드를 호출한다. 이처럼 자신과 같은 메서드를 호출하면 직접(direct) 재귀이다.
간접(indirect) 재귀는 예를 들어 메서드 a가 메서드 b를 호출하고, 다시 메서드 b가 메서드 a를 호출하는 구조로 이루어진다.
📘 유클리드 호제법
두 정수의 최대공약수를 재귀적으로 구하는 방법을 알아보자.
유클리드 호제법이란 2개의 자연수의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
최대공약수를 구할 때 두 정수를 직사각형의 두 변의 길이라고 생각해보자. 그럼 문제가 다음처럼 바뀔 수 있다.
=> 직사각형을 정사각형으로 완전히 채울때, 만들 수 있는 정사각형의 가장 긴 변의 길이를 구하라.
예로 들어 22 X 8 크기의 직사각형을 생각해보면, 짧은 변(8)으로 하는 정사각형으로 분할하면 8 X 6 크기의 직사각형이되고, 짧은 변(6)으로 하는 정사각형으로 나누어보면 6 X 2 크기가 되고 또 같은 과정을 수행하면 2 X 2크기의 정사각형으로 나눌 수 있으므로 여기서 얻은 2가 최대 공약수이다.
이 설명을 코드로 보자.
✏ 유클리드 호제법 코드
import java.util.Scanner;
public class Euclid {
static int euclid(int x, int y) {
if (y == 0)
return x;
else
return euclid(y, x % y);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("정수를 입력(x) : "); int x = sc.nextInt();
System.out.print("정수를 입력(y) : "); int y = sc.nextInt();
System.out.println("최대공약수 : " + euclid(x, y));
}
}최대공약수는 y가 0이면 x고, y가 0이 아니면 euclid(y, x % y)로 구한다.
