Algorithm - 재귀(recursive)

재귀란?
어떤 사건이 자기 자신을 포함하고 있거나 또는 자기 자신을 사용하여 정의하고 있을 때 이를 재귀적이라고 함

 

재귀에 관한 기본적인 내용은 https://dusen0528.tistory.com/31?category=991091 를 참고하도록 하자

 

가장 기초적인 재귀 팩토리얼에 대해 알아보자

5!의 경우 5*4*3*2*1 = 120이다.

재귀의 핵심 포인트는 종료조건과 재귀조건이다. 위의 식을 보면 알 수 있듯이 n*(n-1)*(n-2)..등의 패턴이 반복되는 것을 알 수 있다. 이를 코드로 옮기면

import java.util.Scanner;

public class Factorial {
    static int factorial(int n){
        if(n>0) return n*factorial(n-1);
        else return 1;
    }   
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        System.out.println("정수를 입력하세요");
        int x = stdIn.nextInt();
        System.out.println(x+"팩토리얼의 값은 "+factorial(x));

        stdIn.close();
    }
}


---------------
정수를 입력하세요
5
5팩토리얼의 값은 120

 

위의 factorial 함수를 보면 매개변수 n에 전달받은 값이 0보다 클 경우 n*factorial(n-1)을 반환하고

n에 전달받은 값이 0보다 작을 경우 1을 반환한다.

return (n>0)?n*facotrial(n-1):1;

이를 삼항연산자를 이용하여 간단하게 표현할 수 있다.

 

n이 0보다 클 경우 n*factorial(n-1)을 아닐 경우 1을 반환한다.

 

순서를 보면 factorial(5)를 호출 시 n>0 조건에 의해 5*factorial(4)->5*4*factorial(3)...

등의 과정을 거치고 factorial(0)을 호출하면 종료조건인 1을 반환하며 5*4*3*2*1 = 120이라는 결과가

나오는 것이다.

 

유클리드 호제법

- 두 정수의 최대공약수를 재귀적으로 구하는 방법이다.

1.길이가 가로 22, 세로 8인 직사각형을 상상해보자
2.22를 8로 나누면 가로길이가 8, 8, 6로 나뉘어진다.
3.가로길이가 6인 정사각형은 현재 세로 길이는 그대로 8이다 이를 6으로 나누면 6,2
4.위의 사각형에도 이러한 방식으로 작업하여 2x2 즉, 최종적으로 정사각형만으로 구성했을 때 변의 길이가 최대공약수이다.

이렇게 두 정수가 주어질 경우 큰 값을 작은 값으로 나누었을 때 나누어떨어지면 그중에 작은 값이 최대공약수이다.(4단계)
나누어떨어지지 않으면 작은 값과 나머지로 나누어떨어질 때까지 같은 과정을 재귀적으로 반복한다(1,2단계)

이를 정리하면 최대공약수는 다음과 같이 구할 수 있다
y = 0일 때 최대공약수 : x
y != 0일 때 최대공약수 : gcd(y, x%y)

이 알고리즘을 유클리드 호제법이라고 한다.

 

import java.util.Scanner;

public class UclidGCD {
    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 stdIn = new Scanner(System.in);
        System.out.println("두 정수의 최대 공약수를 구합니다");
        System.out.print("정수를 입력하세요: "); int x = stdIn.nextInt();
        System.out.print("정수를 입력하세요: "); int y = stdIn.nextInt();

        System.out.println("최대 공약수는 " + gcd(x,y) + "입니다"); 
        stdIn.close();
    }
}

-------------
두 정수의 최대 공약수를 구합니다
정수를 입력하세요: 532
정수를 입력하세요: 12
최대 공약수는 4입니다

 

하향식 분석법

위의 사진과 같이 위에서 아래로 내려오며 메소드를 호출하며

계단식으로 자세히 조사해 나가는 분석기법을 하향식 분석(top-down analysis)라고 한다.

 

위의 그림을 보면 fib(1) fib(2) 등.. 같은 메소드가 여러번 호출되는 것을 알 수 있다. 

이와 같은 이유로 하향식 분석이 반드시 효율적이라고 할 순 없다.

 

상향식 분석법

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

static void recur(int n){
    if(n>0) {
        recur(n-1);
        System.out.println(n);
        recur(n-2);
    }
}

이러한 메소드가 있다고 생각해보자,

recur(1) 호출시
STEP1 recur(0)을 실행
STEP2 1을 출력
STEP3 recur(-1)을 실행

여기서 STEP 1의 recur(0)과 recur(-1)은 출력할 내용이 없다. 따라서 recur(1)은 1만 출력한다.

 

다음으로

recur(2) 호출시
STEP1 recur(1)을 실행
STEP2 2를 출력한다
STEP3 recur(0)을 실행

STEP1의 recur(1)은 1을 출력하고 STEP3의 recur(0)은 출력할 내용이 없다

따라서 전체과정을 거치면 1과 2가 출력이 된다.

이 작업을 recur(4)까지 쌓아 올려 설명한 내용은 다음 그림과 같다

 

 

위의 개념들을 토대로 한가지 문제를 풀어보자

static void recur2(int n){
    if(n>0) {
        recur2(n-2);
        System.out.println(n);
        recur2(n-1);
    }
}

위의 메소드를 하향식 분석과 상향식 분석을 해보면

 

 

재귀 알고리즘의 비재귀적 표현

 

• 꼬리 재귀의 제거
  • 메소드의 꼬리에서 재귀 호출하는 메소드 recur(n-2)는 인수로 n-2를 전달하여 recur 메소드를 호출한다는 의미이다.
  • 이는 "n값을 n-2로 업데이트하고 메소드의 시작 지점으로 돌아간다"라는 말로 호출 방식을 바꿀 수 있다.

static void recur(int n){
	while(n>0){
    	recur(n-1);
        System.out.println(n);
        n = n-2;
	}
}

이와 같은 방식으로 꼬리 재귀를 쉽게 제거할 수 있다.

 

• 그러나 꼬리 재귀와는 달리 앞쪽에서 호출하는 재귀 메소드는 제거하기가 쉽지 않다. 왜냐하면 변수 n값을 출력하기 전에 recur(n-1)을 먼저 수행해야 하기 때문이다. 그래서 재귀 호출 recur(n-1)을 다음과 같이 바로 바꿀 수 없다

- "n값을 n-1로 업데이트 하고 메소드의 시작 지점으로 돌아간다" 는 불가능하다.

- 예를 들어 n이 4인 경우 재귀 호출 recur(3)의 처리가 완료되지 않으면 n값인 '4'를 저장해야 한다.

- 즉 현재 n값을 '잠시' 저장한다. 그리고 recur(n-1)의 처리가 완료된 후에 n값을 출력할 때는 다음 과정을 따른다

- 저장했던 n을 다시 꺼내 그 값을 출력한다

 

이러한 재귀 호출을 제거하기 위해서는 변수 n값을 잠시 저장해야 한다는 사실을 알았다.

이러한 경우 활용할 수 있는 자료구조가 스택이다.

//스택을 활용한 recur 메소드를 비재귀적으로 구현
static void recur(int n){
        IntStack s = new IntStack(n);
        while(true){
            if(n>0){
                s.push(n);
                n = n-1;
                continue;
            }
            if(s.isEmpty()!=true){
                n = s.pop();
                System.out.println(n);
                n = n-2;
                continue;
            }
            break;
        }
    }

 

과정

STEP1 n값 4를 스택에 푸쉬한다
STEP2 n값을 하나 줄여 3으로 만든다
STEP3 continue문에 의해 while문의 맨 앞으로 돌아간다

n값 4는 0보다 크므로 맨 앞의 if문이 실행된다. 그 결과 위의 과정이 봔복되며 스택에 4,3,2,1이 쌓이게 된다.

스택에 1을 쌓은 다음 n값은 0이 되고 while 문의 맨 앞으로 돌아간다. 그렇다면 맨앞의 if문은 지나가고 두번째 if문에 의해

다음과 같은 과정이 진행된다

STEP4 스택에서 팝한 값 1을 n에 넣는다
STEP5 n값 1을 출력한다
STEP6 n값을 2 줄여 -1로 만든다
STEP7 continue문에 의해 while문의 처음으로 돌아간다

n값이 -1이므로 다시 뒤쪽 if문이 실행->스택에서 2가 팝되고 그 값을 출력한다. 이렇게 진행되면 결국

n은 0이하가 되고 스택이 텅 비면 두 if문 모두 실행되지 않고 break문이 실행되므로 메소드가 종료된다.