자료구조&기본 알고리즘 입문(자바)- 재귀 알고리즘(1)
● 재귀?
어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 떄 재귀적(rescursive)이라고 한다.
이러한 재귀의 개념을 사용하면 1부터 시작하여 2,3, ...과 같이 무한하게 이어지는 자연수를 아래처럼
정의할 수 있다
1. 1은 자연수다
2. 자연수 n의 바로 다음 수도 자연수다
재귀적 정의(recursive definition)에 의해 무한으로 존재하는 자연수를 위의 두 문장으로 정의 할 수 있다.
재귀를 효과적으로 사용하면 이런 정의뿐만 아니라 프로그램도 간결하게 할 수 있다.
● 팩토리얼 구하기
재귀의 사용예로 음이 아닌 정수의 팩토리얼(factorial)을 구하는 프로그램이 있다. 음이 아닌 정수 n의 팩토리얼(n!)은
다음과 같이 재귀적으로 정의할 수 있다.
1. 0! = 1
2. n > 0 이면 n! = n x (n-1)!
예컨대 10의 팩토리얼인 10!은 10x9!로 구할 수 있고 그 우변에서 사요오디는 식 9!은 9x8!로 구할 수 있다.
import java.util.Scanner;
// 팩토리얼을 재귀적으로 구현
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 stdIn = new Scanner(System.in);
System.out.print("정수를 입력.：");
int x = stdIn.nextInt();
System.out.println(x + "의 팩토리얼은 " + factorial(x) );
}
}factorial 메서드는 매개변수 n에 전달받은 값이 0보다 크면 n*factorial(n-1)을 반환하고, 그렇지 않으면 1을 반환한다
factorial 메서드를 사용해 3으리 팩토리얼 값을 구체적으로 구하는 과정은 다음과 같다. (ex:정수 3을 입력했을 경우)
a. 메서드 호출식 factorial(3)을 실행하면 factorial 메서드가 시작된다. 이 메서드는 매개변수 n에 3을 전달받아
3 * factorial(2)를 반환한다. 그런데 이 곱셈을 수행하려면 factorial(2)의 값을 구해야 한다. 2를 다시 매개변수로
전달하고 factorial 메서드를 호출한다
b. 호출된 factorial 메서드는 매개변수 n에 2를 전달받는다. 다시 곱셈 2 * factorial(1)을 수행하기 위해
factorial 메서드를 호출한다
c. 다시 호출된 factorial 메서드는 매개변수 n에 1을 전달받는다. 1 * factorial(0)을 수행하기 위해
factorial 메서드를 호출한다
d. 호출된 factorial 메서드는 매개변수 n에 전달받은 값이 0이므로 1을 반환한다.
c. 반환된 값 1을 전달받은 factorial 메서드는 1*factorial(0)(1*1)을 반환한다.
b. 반환된 값 1을 전달받은 factorial 메서드는 2*factorial(1)(2*1)을 반환한다.
c. 반환된 값 2를 전달받은 factorial 메서드는 3*factorial(2)(3*2)를 반환한다.
위와 같은 방법으로 factorial(3)을 사용해 팩토리얼 값 6을 얻을 수 있다. factorial 메서드는 n-1의 팩토리얼 값을 구하기
위해 다시 factorial 메서드를 호출한다. 이러한 메서드 호출 방식을 재귀 호출(recursive call)이라고 한다.
● 직접 재귀와 간접 재귀
factorial 메서드는 그 내부에서 factorial 메서드를 호출한다. 이처럼 자신과 같은 메서드를 호출하면 직접(direct)재귀이다. 간접(indirect) 재귀는 메서드 a가 메서드 b를 호출하고, 다시 메서드 b가 메서드 a를 호출하는 구조로 이루어진다.
a. 직접재귀
메서드 a 메서드 a
a( ); -> a( );
b. 간접 재귀
메서드 a 메서드 b 메서드 a
b(); -> a(); -> b();
재귀 알고리즘에 알맞은 경우는 '풀어야 할 문제', '계산할 메서드', '처리할 데이터 구조'가 재귀로 정의되는 경우.
앞에서 살펴본 '팩토리얼 값을 구하는 예' 는 많은 재귀 알고리즘 사용 방법 가운데 하나다.
○ 유클리드 호제법
두 정수의 최대공약수(greatest common divisor)를 재귀적으로 구하는 방법. 두 정수를 직사각형의 두 변의 길이라고
생각하면 두 정수의 최대공약수를 구하는 문제는 다음 문제로 바꿀 수 있따.
직사각형을 정사각형으로 완전히 채운다. 이렇게 만들 수 있는 정사각형의 가장 긴 변의 길이를 구하라.
예를 들어 각 변의 길이가 22와 8일 직사각형으로 구체적인 과정을 설명하면 다음과 같다.
1. 22 x 8 크기의 직사각형에서 짧은 변(8)을 한 변으로 하는 정사각형으로 분할한다. 이렇게 하면 8x8크기의
정사각형 타일 2장이 생긴다. 그리고 8x6크긱의 직사각형이 1개 남는다
2. 남은 8 x 6 크기의 직사각형으로 다시 같은 과정을 수행한다. 6 x 6 크기의 정사각형이 1개, 6 x 2 크기의
직사각형이 1개 남는다
3. 다시 남은 6 x 2 크기의 직사각형으로 같은 과정을 수행한다. 이번에는 2 x 2 크기의 정사각형 3개로 나눌 수 있다. 여기서 얻은 2가 최대공약수이다.
이렇게 두 정수가 주어질 경우 큰 값을 작은 값으로 나누었을 떄 나누어 떨어지는 가장 작은 값이 최대공약수이다.
나누어지지 않으면 작은 값(얻은 나머지)에 대해 나누어 떨어질때까지 같은 과정을 재귀적으로 반복한다.
이 과정을 좀 더 수학적으로 표현하기 위해 두 정 수 x, y의 최대공약수를 gcd(x,y)로 표기하고 x = az와 y = bz를
만족하는 정수 a , b 와 최대의 정수 z가 존재할 때 z를 gcd(x,y)라고 할 수 있다. 다시 말해 최대공약수는 y가 0이면
x이고, y가 0이 아니면 gcd(y,x%y)로 구한다. 이 알고리즘을 유클리드 호제법(Euclidean method if mutual division)이라고 한다. 다음은 유클리드 호제법에 의해 두 정수의 최대공약수를 구하는 프로그램이다
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));
}
}-출처: 자료구조와 함꼐 배우는 알고리즘 입문[자바편] 책 중
http://www.yes24.com/Product/Goods/60547893