Chapter 05-1. 재귀 알고리즘_재귀 알고리즘의 기본

재귀란?

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

재귀의 개념을 사용하면 1부터 2, 3, …과 같이 무한히 계속되는 자연수를 아래와 같이 정의 가능

• 1은 자연수 입니다.
• 자연수 n의 바로 다음 정수도 자연수입니다.

재귀적 정의(recursive definition)를 사용하여 무한으로 존재하는 자연수를 위의 두 문장으로 정의함

 

팩도리얼 구하기

음이 아닌 정수 n의 팩토리얼(factorial) n!은 아래와 같이 재귀적으로 정의 가능

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

예를 들어, 10의 팩토리얼인 10!은 109!로 구할 수 있고, 9!은 98!로 구할 수 있음

 

팩토리얼값을 재귀적으로 구함

package ch05_1;

import java.util.Scanner;

// 팩토리얼값을 재귀적으로 구함
public class Ex01_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 scanner = new Scanner(System.in);

        System.out.print("정수를 입력하세요.: ");
        int x = scanner.nextInt();

        System.out.println(x + "의 팩토리얼은 " + factorial(x) + "입니다.");
    }
}

/*
정수를 입력하세요.: 3
3의 팩토리얼은 6입니다.
 */

 

재귀 호출(recursive call)

위의 factorial 메서드는 n-1의 팩토리얼 값을 구하기 위해 다시 factorial메서드를 호출하는데, 이러한 메서드 호출 방식을 재귀 호출이라 함

 

직접 재귀(direct)

자신과 동일한 메서드를 호출하는 것

 

간접 재귀(indirect)

다른 메서드를 통해 자기 자신과 같은 메서드를 호출하는 것

메서드 a가 메서드 b를 호출하고, 다시 메서드 b가 메서드 a를 호출하는 구조

 

유클리드 호제법

두 정수의 최대공약수(greatest common divisor)를 재귀적으로 구하는 방법

두 정수가 주어질 경우 큰 값을 작은 값으로 나누었을 때 나누어 떨어지면 그중에 작은 값이 최대공약수, 나누어 떨어지지 않으면 작은 값과 나머지로 나누어 떨어질 때까지 같은 과정을 재귀적으로 반복

• 두 정수 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)

 

유클리드 호제법으로 최대공약수를 구함

package ch05_1;

import java.util.Scanner;

// 유클리드 호제법으로 최대공약수를 구함
public class Ex02_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 scanner = new Scanner(System.in);

        System.out.println("두 정수의 최대공약수를 구합니다.");

        System.out.print("정수를 입력하세요: ");
        int x = scanner.nextInt();
        System.out.print("정수를 입력하세요: ");
        int y = scanner.nextInt();

        System.out.println("최대공약수는 " + gcd(x, y) + " 입니다.");
    }
}
/*
두 정수의 최대공약수를 구합니다.
정수를 입력하세요: 22
정수를 입력하세요: 8
최대공약수는 2 입니다.
 */

 

비재귀적 팩토리얼

package ch05_1;

import java.util.Scanner;

// 비재귀적 팩토리얼
public class Ex03_factorialEx {
    // 음이 아닌 정수 n의 팩토리얼 값 반환
    static int factorial(int n) {
        int temp = 1;
        while(n > 0) {
            temp *= n--;
        }
         return temp;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("정수를 입력하세요: ");
        int x = scanner.nextInt();

        System.out.println(x + "의 팩토리얼은 " + factorial(x) + "입니다.");
    }
}
/*
정수를 입력하세요: 4
4의 팩토리얼은 24입니다.
 */

 

유클리드 호제법 최대공약수를 비재귀적으로 구하기

package ch05_1;

import java.util.Scanner;

// 유클리드 호제법 최대공약수를 비재귀적으로 구하기
public class Ex04_euclidGCDEx {
    // 정수 x, y의 최대공약수를 비재귀적으로 구하여 반환
    static int gcd(int x, int y) {
        while(y != 0) {
            int temp = y;
            y = x % y;
            x = temp;
        }
        return x;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.println("두 정수의 최대공약수를 구합니다.");

        System.out.print("정수를 입력하세요: ");
        int x = scanner.nextInt();
        System.out.print("정수를 입력하세요: ");
        int y = scanner.nextInt();

        System.out.println("최대공약수는 " + gcd(x, y) + " 입니다.");
    }
}
/*
두 정수의 최대공약수를 구합니다.
정수를 입력하세요: 3
정수를 입력하세요: 18
최대공약수는 3 입니다.
 */

 

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

package ch05_1;

import java.util.Scanner;

// 배열의 모든 요소의 최대 공약수를 구하기
public class Ex05_GCDArray {
    // 정숫값 x, y의 최대공약수를 비재귀적으로 구하여 반환
    static int gcd(int x, int y) {
        while (y != 0) {
            int temp = y;
            y = x % y;
            x = temp;
        }
        return x;
    }

    // 요솟수가 n인 배열 a의 모든 요소의 최대 공약수 구하기
    static int gcdArray(int a[], int start, int no) {
        if (no == 1) {
            return a[start];
        } else if (no == 2) {
            return gcd(a[start], a[start + 1]);
        } else {
            return gcd(a[start], gcdArray(a, start + 1, no - 1));
        }
    }

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

        int[] x = new int[num]; // 길이가 num인 배열

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

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