[JAVA] 팩토리얼 , 최대공약수 구하는 알고리즘 - 재귀 기초

Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다.

---

재귀란 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적(Recursive)이라고 한다.

재귀는 직접 재귀와 간접 재귀로 나뉜다.

• 직접 재귀 : 메소드 a가  자신(메소드 a)을 호출
• 간접 재귀 : 메소드 a가 메소드 b를 호출하고, 메소드 b는 메소드 a를 호출

재귀 메소드는 정지조건(재귀 앵커)을 제대로 설정하지 않으면 무한 루프와 같이 끝없이 재귀 메소드가 호출되므로 유의하여야 한다.

 

팩토리얼 구하기

음이 아닌 정수 n의 팩토리얼(n!)은 아래처럼 재귀적으로 정의할 수 있다.

1. 0! = 1
2. n > 0 이면 n! = n * (n-1)!

위의 정의를 그대로 구현하면 아래와 같다.

static int factorial(int n)
{
    if(n > 0) return n * factorial(n-1);
    else return 1; //정지 조건
}

 

실행 예제

public class Main{
	
	static int factorial(int n)
	{
		if(n > 0) return n * factorial(n-1);
		else return 1;
	}
	
	public static void main(String[] args) {
		
		for(int i = 0; i < 10; ++i) System.out.println(i + " : " + factorial(i));

	}
}
/*
0 : 1
1 : 1
2 : 2
3 : 6
4 : 24
5 : 120
6 : 720
7 : 5040
8 : 40320
9 : 362880
 */

 

재귀를 사용하지 않고 팩토리얼을 구하는 알고리즘은 아래와 같다.

static int factorial(int n)
{
    if(n == 0) return 1;
    int tmp = 1;
    for(int i = 1; i <= n; ++i) tmp *= i;
    return tmp;
}

 

두 정수의 최대공약수 구하기

static int gcd(int x, int y)
{
    if(y == 0) return x;
    else return gcd(y, x % y);
}

 

실행 예제

public class Main{
	
	static int gcd(int x, int y)
	{
		if(y == 0) return x;
		else return gcd(y, x % y);
	}
	
	public static void main(String[] args) {
		
		System.out.println("22와 8의 최대공약수 : " + gcd(22, 8));

	}
}
/*
22와 8의 최대공약수 : 2
*/

 

유클리드 호제법
위 알고리즘은 유클리드 호제법을 이용한 것이다.
두 정수를 직사각형의 두 변의 길이라고 생각하면 두 정수의 최대공약수를 구하는 문제는
직사각형을 정사각형으로 완전히 채우고 이렇게 만들 수 있는 정사각형의 가장 긴 변의 길이를 구하면 된다.

1. 짧은 변의 길이를 한 번으로 하는 정사각형으로 채운다.
2. 남은 직사각형에 대해 같은 작업을 반복
3. 정사각형만으로 구성되었을 때의 변의길이가 최대공약수

 

재귀를 사용하지 않은 두 정수의 최대공약수를 구하는 알고리즘은 아래와 같다.

static int gcd(int x, int y)
{
    while(y != 0)
    {

        int temp = y;
        System.out.println(y + " " + x);
        y = x % y; //y에 나머지 저장
        x = temp;
    }
    return x;
}

 

 

배열의 모든 원소의 최대공약수 구하기

import java.util.Scanner;
public class Main{
	
	static int gcd(int x, int y) {
		if(y == 0) return x;
	    else return gcd(y, x % y);
	}

	static int gcdArray(int arr[], int start, int no) {
		if (no == 1) return arr[start];
		else if (no == 2) return gcd(arr[start], arr[start + 1]);
		else return gcd(arr[start], gcdArray(arr, start + 1, no - 1));
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.print("정수 몇 개의 최대 공약수를 구할까요?：");
		int num;
		do {
			num = sc.nextInt();
		} while (num <= 1);

		int[] arr = new int[num];

		for (int i = 0; i < num; i++) {
			System.out.print("x[" + i + "]：");
			arr[i] = sc.nextInt();
		}

		System.out.println("최대 공약수는 " + gcdArray(arr, 0, num) + "입니다.");
		}
	}
/*
정수 몇 개의 최대 공약수를 구할까요?：3
x[0]：25
x[1]：1525
x[2]：2000
최대 공약수는 25입니다.
*/