재귀란?

재귀란
어떤 사건이 자기 자신을 포함하고 있거나 또는 자기 자신을 사용하여 정의하고 있을때를
재귀적이라고 표현한다. 재귀의 개념을 사용하면 프로그램을 간결하게 작성할 수 있는 장점이 있다.

재귀 호출을 이용하여 재귀를 표현한 이미지이다.
코드로 직접 재귀 호출을 사용하여 이해해보자. 이미지와 마찬가지로 팩토리얼을 구하는 프로그램을 작성할 것이다.

재귀 호출로 팩토리얼 구하기

팩토리얼이란
특정 정수에서 1까지의 수를 모두 곱하는 것을 뜻한다.
ex) 4! = 4x3x2x1 즉 4! = 24이다.

재귀 호출로 팩토리얼을 구하는 코드를 작성해보자.

// 어떤 자연수가 주어졌을때 그 수에 해당하는 팩토리얼을 구해서 출력
public class Factorial {
	
    static int factorial(int n) {
    	if(n > 0) {
        	return n * factorial(n-1);	// 재귀적으로 factorial을 구하기 위해 자기 자신을 호출하면서 매개변수로 n-1을 넘겨준다.
        } else {
        	return 1;	// 0보다 작은 수가 들어오면 1을 반환
        }
    }
    
   public static void main(String[] args)  {
   		Scanner sc = new Scanner(System.in);
        
        System.out.println("정수를 입력하세요: ");
        int x = sc.nextInt();
        
        System.out.println(x + "의 팩토리얼은 " + factorial(x) + "입니다.");
   }
}

위와 같이 어떤 정수에 대한 팩토리얼을 구하는 프로그램을 작성해 보았다.
factorial 메서드가 반환하는 값은 다음과 같다.

매개변수 n에 전달받은 값이 0보다 클 때 : n * factorial(n-1)
매개변수 n에 전달받은 값이 0보다 작을때: 1

factorial 메서드를 통해 3의 팩토리얼을 구하는 과정은 아래 이미지와 같다.

직접 재귀와 간접 재귀

직접 재귀
factorial 메서드는 자기 자신 내부에서 factorial 메서드를 호출한다.
이처럼 자신과 동일한 메서드를 호출하는 것을 직접 재귀라고 한다.

간접 재귀
간접 재귀는는 직접 재귀와 다르게 a메서드가 b메서드를 호출하고,
다시 b메서드가 a메서드를 호출하는 구조로 이루어진다.
(다른 메서드를 통해 자기 자신과 같은 메서드를 호출한다.)

재귀를 사용하여 최대 공약수 구하기

재귀 알고리즘을 사용하여 두 정수의 최대 공약수를 구하는 프로그램을 작성할것이다.

최대공약수
정수를 나누어 떨어지지 않는 수 중에 두 정수의 공통되는 약수중 최대 값

예를 들어 10, 14 두 정수가 있다면 두 정수에 약수는 다음과 같다.
10 : 1, 2, 5, 10
14 : 1, 2, 7, 14

그 중 공통되는 약수중 최대값을 가진 약수 '2'가 최대 공약수인것이다.

최대 공약수를 구하기 위해 모든 수로 두 수를 나누어 둘다 떨어지는 값을 구하는 방법도 있지만 시간복잡도가 O(n)이기 때문에 성능적으로 좋지 않을 수 있다.

그런 단점을 해결하기 위해서 사용하는 알고리즘이 존재하는데 그것이 바로 '유클리드 호제법' 이다.

유클리드 호제법

유클리드 호제법은 두 수 x, y의 최대 공약수는 y, r의 최대 공약수와 같다는 원리를 이용한다.

계속해서 x값에는 y값을 대입하고, y값에는 r값을 대입하다 보면,
언젠가는 r이 0이되는데 이때 y에 있는 값이 최대 공약수이다. 참고링크

위와 같이 유클리드 호제법을 사용하면 쉽고 빠르게 두 정수의 최대 공약수를 구할 수 있다.
유클리드 호제법을 사용하여 두 정수의 최대 공약수를 구하는 프로그램을 작성해보자.

유클리드 호제법과 재귀호출을 사용한 최대공약수 구하기

class EuclidGCD {

	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 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) + "입니다.");
    }
}

위와 같이 유클리드 호제법과 재귀호출을 통해 쉽게 두 정수의 최대 공약수를 구할 수 있다.