알고리즘 공부 - 재귀함수 1편

Programming/Computer Science

알고리즘 공부 - 재귀함수 1편

긍정왕웹서퍼 2022. 8. 2. 00:04

728x90

재귀함수란?

여기서 재귀(recursive)는 어떤 사건이 자기 자신을 포함한 채로 다시 자기 자신을 사용하여 정의될 때, 즉

자기 스스로를 재사용할 때 라고 편하게 줄일 수 있을 거 같습니다. 익숙한 현상을 이야기 해보자면 엘리베이터 속 거울안에 거울같은 느낌!

코드로 간단하게 구현해보겠습니다.

class Factorial {
	// 재귀함수 factorial 구현해보기 
	static int factorial(int n) {
		if(n > 0) {
        	return n * factorial(n - 1);
        } else {
        	return 1;
        }
    }
    
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        factorial(x);
    }

위 코드에서처럼 factorial 함수는 매개변수 n을 전달받은 값이 0보다 크면 n * factorial(n-1)을 하고 그렇지 않다면 1을 반환합니다.

이와같이 factorial 메서드가 그 내부에서 자기자신을 직접 호출하며 이를 직접(direct) 재귀 라고 합니다.

간접(indirect) 재귀는 메서드가 a와 b를 호출하고 다시 메서드 b가 a를 호출하는 구조로 서로를 호출하는 방식이라 할 수 있습니다.

유클리드 호제법

두 정수의 최대공약수(greatest common divisor)를 재귀적으로 구하는 방법이 필요합니다.

두 정수를 직사각형의 두 변의 길이라고 생각하면 두 정수의 최대공약수를 구하는 문제와 과정을 설명해보자면

직사각형을 정사각형으로 완전히 채웁니다. 이렇게 만들 수 있는 정사각형의 가장 긴변의 길이를 구하시오
각 변의 길이가 22와 8인 직사각형을 예로 들겠습니다.

22 x 8 크기의 직사각형에서 짧은 변(8)을 한 변으로 하는 정사각형으로 분할(a)합니다. 이렇게 하면 (b)처럼 8 x 8 크기의 정사각형 타일 2장이 생깁니다. 그리고 8 x 6 크기의 직사각형이 1개 남습니다.
남은 8 x 6 크기의 직사각형으로 다시 같은 과정을 수행(c)합니다. 6 x 6 크기의 정사각형이 1개, 6 x 2 크기의 직사각형이 1개 남습니다.
다시 남은 6 x 2크기의 직사각형으로 같은 과정을 수행(d)합니다. 이번에는 2 x 2 크기의 정사각형 3개로 나눌 수 있습니다. 여기서 얻은 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)로 구합니다. 이 알고리즘을 유클리드 호제법(Euclidean method of mutual division) 이라고 합니다.

유클리드 호제법에 의해 두 정수의 최대공약수를 구하는 코드를 표현해보겠습니다.

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);
        
        int x = sc.nextInt();
        int y = sc.nextInt();
        int result = gcd(x,y);
        System.out.println("최대공약수는 "+result+" 입니다.);
    }
}

재귀 알고리즘 분석

재귀 알고리즘을 분석하기 위해 하향식 분석(top down)과 상향식 분석(bottom up) 방식으로 살펴보고 재귀알고리즘을 비재귀적으로 구현하는 방법까지 코드로 알아보겠습니다.

재귀알고리즘의 분석

class Recur {

	static void recur(int n) {
    	if(n > 0) {
        	recur(n - 1);
            System.out.println(n);
            recur(n - 2);
        }
    }
    
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        recur(x);
    }
}

recur 메서드는 factorial 메서드나 gcd 메서드와 달리 메서드안에서 재귀 호출을 2회 실행합니다.

재귀호출을 여러회 실행하는 메서드를 순수하게(genuinely) 재귀적이라 하며 실제 동작은 매우 복잡합니다.

이중 하향식 분석으로 분석해보자면 매개변수 n으로 4를 전달하면 recur 메서드는 이와같이 실행합니다.

1. recur(3)을 실행합니다.
2. 4를 출력합니다.
3. recur(2)를 실행합니다.

이런 과정을 거치면서 가장 위쪽에 위치한 메서드호출부터 시작해 계단식으로 자세히 조사하는 분석 기법이며

다시말해 트리형태의 방식을 하향식 분석(top-down analysis) 라고 합니다. 하지만 이와 같이 메서드의 호출이 여러번 나올 수 있기 때문에 하향식 분석이 반드시 효율적이라고 할 순 없습니다.

위쪽부터 아래로 분석하는 하향식분석과는 대조적으로 아래쪽부터 쌓아 올리며 분석하는 방법이 상향식 분석(bottom-up analysis)

이라 합니다. recur 메서드는 n이 양수일 때만 실행하므로 먼저 recur(1)을 생각해보자면

1. recur(0)을 실행합니다.
2. 1을 출력합니다.
3. recur(-1)을 실행합니다.

여기서 1. 의 recur(0)과 3. 의 recur(-1)은 출력할 내용이 없습니다. 따라서 2. 의 1만 출력합니다.

recur(2) 에 대해 살펴보자면

1. recur(1)을 실행합니다.
2. 2를 출력합니다.
3. recur(0)을 실행합니다.

1. 의 과정 recur(1)은 1을 출력하고 3. 의 과정 recur(0)은 출력할 내용이 없습니다. 전체 과정을 거치면 1과 2가 출력됩니다.

이 작업을 recur(4)까지 쌓아올려보겠습니다.

recur(1) : recur(0) 1. recur(-1) -> 1
recur(2) : recur(1) 2. recur(0) -> 1,2
recur(3) : recur(2) 3. recur(1) -> 1,2,3,1
recur(4) : recur(3) 4. recur(2) -> 1,2,3,1,4,1,2