재귀(1)

재귀?

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

즉 프로그램에서 사건이 발생할 경우 해당 메서드를 호출하며, 호출하여 작업을 수행하는 중 작업이 종료되지 않은 상태에서 자신을 다시 호출하는 경우이다.

정확히는 자기 자신을 호출하는 것이 아닌 자신과 같은 메서드를 작업 중에 호출해서 작업을 처리하는 것이다.

Java의 메서드 호출 시 호출 스택에 작업들이 쌓이는 것을 생각해보면 좀 더 잘 이해를 할 수 있다.

main() -> a()를 호출
a() -> a()를 호출
a() -> a()를 호출 하면 
현재 호출 스택에 main() -> a() -> a() -> a()  이런식으로 쌓이게 된다.

마지막으로 호출된 메서드가 종료 시(return) 호출 스택에서 작업이 하나씩 빠지게 된다. 그리고 최종적으로 main()까지 작업을 마치면 종료하게 된다. 즉, 메서드는 같은 메서드를 호출했지만 실제로는 독립적 작업인 것이다. 

---

재귀를 사용한 예시

팩토리얼 구하기

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

Ex) 10! = 10 * 9!( 9 * 8!( 8 * 7!( 7 * 6!  ~~~ 1 * 0!) ) )

---

public class Factorial {

    static int factorial(int n){
        if(n > 0)
            return n * factorial(n-1);
        else
            return 1;
            
        // return (n > 0) ? n * factorial(n-1) : 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)+ "입니다");
    }
}

Do it 자료구조와 함께 배우는 알고리즘 입문 참조

위 그림과 같이 팩토리얼 식은 n * (n-1!)이며 이를 위하여 팩토리얼 부분을 구하기 위해서 다시 메서드가 호출된다.

이런 메서드 호출 방식을 재귀 호출이라 한다.

---

직접 재귀와 간접 재귀

직접 재귀 : 메서드 내부적으로 자신과 같은 메서드를 호출하는 것  ex) factorial(n) -> factorial(n-1)
간접 재귀 : 다른 메서드를 통해서 자신과 같은 메서드를 호출하는 것  ex) a() -> b() -> a()

---

유클리드 호제법

두 정수가 주어졌을 경우 두 수의 최대공약수를 구할 경우 두 수를 직각 사각형의 두 변의 길이로 놓고 두 수 중 작은 수를 두 변의 길이로 갖는 정사각형을 통하여 직사각형을 나누어 나간다. 이떄 정확히 나누어 떨어진다면 두 수중 작은 수가 두 수의 최대 공약수가 된다.

정확히 나누어 떨어지는 경우)
8 , 24가 있다고 했을 경우 직사각형은 8 , 24를 두변으로 갖으며 두 수중 작은 수인 8을 변으로 갖는 정사각형으로 직사각 형을 나눌 시 정사각형 3개로 정확히 직사각형을 나눌 수 있다. 이렇게 나누어 떨어진다면 이때 두 수의 최대공약수는 두 수중 작은 수인 8이된다. 정말 그런지 살펴본다면
8의 약수 : 1 2 4 8
24의 약수 : 1 2 3 4 6 8 12 24
두 수의 공약수 : 1 2 4 8
두 수의 최대공약수 : 8

정확히 나누어 떨어지지 않는 경우)
8 ,22가 있다고 했을 경우 두 수를 갖는 직각사각형은 정확하게 나누어 떨어지지 않는다. 실제로 나눠보면 가로 길이를 상대적으로 큰 수로 놓았을 경우 2번 나누고 가로길이는 6이 남는다. 이때 상대적으로 작은 수였던 8은 이번에는 상대적으로 큰 수가 된다. 이때 남은 직사각형의 두 변의 길이는 6 , 8 이된다. 그럼 이제는 다시 상대적으로 작은 수인 6을 두 변으로 갖는 정사각형으로 나눈다. 그럼 1개로 나누고 이번에는 세로길이가 2가 남는다. 2 , 6을 갖는 직사각형이 남으며 이때 상대적으로 작은 변이 2를 갖는 정사각형으로 남은 부분을 나눌 시 3개로 정확히 떨어진다. 이제는 나누어 떨어졌기에 이때 정사각형의 변을 갖는 상대적으로 작은 수가 두 수의 최대공약수가 된다.
8의 약수 : 1 2 4 8
22의 약수 : 1 2 11 22
공약수 : 1 2
최대공약수 : 2

마지막으로 계속 나누는 과정에서 한 변이 1인 정사각형이 만들어질 경우 두 수의 최대 공약수는 1이되며
두 수는 서로소라 한다.

이와같이 최대공약수를 구하는 문제에서도 내부적으로 나누는 로직은 변함이 없다. 단지 나누는 상황에서 남은 부분들로 인한 값만 변화한다. 그렇기에 재귀호출을 사용해서 해결할 수 있다. 물론 재귀호출을 사용하지 않고도 해결가능하다.

---

public class EuclidGCD {
    static int gcd(int x , int y){
		/*반복문
        int tmp = 0;
        while (y != 0){
            tmp = x % y;
            x = y;
            y = tmp;
        }
        return x;
        */
        /* 재귀호출
        System.out.println("x: "+ x + ", y: " + y);
        if( y == 0)
            return x;
        else
            return gcd(y, x % y);*/
    }

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

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

        System.out.print("정수를 입력하세요 : "); int x = sc.nextInt();
        System.out.print("정수를 입력하세요 : "); int y = sc.nextInt();
        System.out.println("최대공약수는 " + gcd(x,y) + "입니다.");
    }
}

---