재귀 알고리즘 기초 이해하기

 

재귀란?

어떤 사건이 자기 자신을 포함하고 있거나 또는 자기 자신을 사용하여 정의하고 있을 때 이를 재귀적(recursive)이라고 합니다.
재귀적 정의를 사용하여 무한으로 존재하는 자연수를 정의한다면
- 1은 자연수입니다.
- 자연수 n의 바로 다음 정수도 자연수입니다.
재귀를 효과적으로 사용하면 이런 정의뿐만 아니라 프로그램도 간결하게 작성할 수 있습니다.

 

팩토리얼 구하기.

재귀를 사용한 예로 가장 먼저 음이 아닌 정수의 팩토리얼(factorial) 값을 구하는 프로그램을 살펴봅시다.
음이 아닌 정수 n의 팩토리얼은(n!) 다음과 같이 재귀적으로 정의할 수 있습니다.
- 0! = 1
- n > 0 이면 n! = n * (n-1)!

즉, 5! 은 5 * 4! 이고 4! 은 4 * 3! 입니다.

import java.util.Scanner;

public class FactorialTest {
    public static int factorial(int n) {
        if (n > 0) { // 매개변수 n이 0보다 크다면
            return n * factorial(n - 1); // n * factorial(n-1)
        } else {
            return 1; // 0보다 크지 않다면 1
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(n + " 의 팩토리얼은 " + factorial(n) + "입니다.");
        // n = 5
        // 5 의 팩토리얼은 120입니다.
    }
}

위 factorial 함수를 삼항연산자를 사용해 한 줄로 사용한다면?

    public static int factorial(int n) {
        return (n > 0) ? n * factorial(n - 1) : 1;
    }

 

직접 재귀와 간접 재귀.

factorial 메서드는 그 내부에서 factorial 메서드를 호출하는데
자신과 동일한 메서드를 호출하는 것을 직접(direct) 재귀라고 하고
간접(indirect) 재귀는 메서드 a가 메서드 b를 호출하고
다시 b가 메서드 a를 호출하는 구조로 이루어집니다.

 

유클리드 호제법.

두 정수의 최대공약수(gcd, greaatest common divisor) 를 재귀적으로 구하는 방법을 알아봅시다.
두 정수를 직사간형 두 변의 길이라고 생각하면 두 정수의 최대 공약수를 구하는 문제는 다음으로 바꿀 수 있습니다.

- 직사각형의 짧은 변을 기준으로 정사각형으로 가득 채웁니다.
- 이렇게 만들어지는 정사각형 가운데 모두 정사각형이 되는 가장 긴 변의 길이를 구하세요.

예로 변의 길이가 22, 8인 직사각형을 예로 들어 최대 공약수를 구하는 과정을 그림으로 표현하면
다음과 같은 그림으로 표현할 수 있고 최대 공약수가 2인 것을 확인할 수 있습니다.

 

이렇듯 두 정수가 주어질 경우 큰 값을 작은 값으로 나누었을 때 나누어 떨어지면 그 중에 작은 값이 최대 공약수이며 (3)
나우어 떨어지지 않으면 작은값과 나머지로 나누어 떨어질 때까지 반복합니다. (1, 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)

import java.util.Scanner;

public class GcdTest {
    // 재귀 함수 안쓰고 구현
    private static int solution(int x, int y) {
        while (y != 0) {
            int z = x % y;
            x = y;
            y = z;
        }
        return x;
    }

    // 재귀함수로 구현
    private static int solution1(int x, int y) {
        if (y == 0) {
            return x;
        } else {
            return solution1(y, x % y);
        }

    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int y = sc.nextInt();

        System.out.println(solution(x, y));
        System.out.println(solution1(x, y));
    }
}