재귀 알고리즘

재귀란?

어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의되는것을 말한다.

간단한 예로 팩토리얼을 들 수가 있다.

n! = n * (n-1)

 

팩토리얼을 메서드로 구현하여 사용한 코드는 다음과 같다.

import java.util.*;

public class Main {
    //양의 정수 n의 팩토리얼을 반환합니다.
    static int factorial(int n){
        if(n>0)
            return n * factorial(n-1);
        else
            return 1;
    }

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

        System.out.print("정수를 입력하세요.:");
        int x = scanner.nextInt();

        System.out.println(x+"의 팩토리얼은 "+factorial(x)+"입니다.");
    }
}

 

직접재귀와 간접재귀

재귀는 같은 메서드에서 직접적으로 이루어질수도 있고 다른 메서드를 거치는 방식을 간접적으로 이루어질 수도 있다. 

전자를 직접재귀, 후자를 간접재귀라고 한다.

예를 들어 메서드 a내부에서 다시 a를 호출하는 방식으로 재귀가 이루어진다면 직접재귀이고,

메서드 a에서 메서드 b를 호출하고 메서드 b에서 다시 메서드 a를 호출하는 방식으로 재귀가 이루어진다면 간접재귀이다.

 

유클리드 호제법 (최대공약수 구하기)

또 재귀는 유클리드호제법에도 사용되는데, 이를 이용해서 두 정소의 최대공약수를 구할 수 있다.

유클리드호제법이란 두 수가 서로 상대방수를 나누어서 결국 원하는 값을 얻는 알고리즘이다.

import java.util.*;

public class Main {
    //유클리드 호제법으로 최대공약수 구하기
    //정수 x,y의 최대공약수를 구하여 반환합니다.
    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 scanner = new Scanner(System.in);

        System.out.println("두 정수의 최대공약수를 구합니다.");
        System.out.print("x: ");
        int x = scanner.nextInt();
        System.out.print("y: ");
        int y = scanner.nextInt();

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

 

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

다음과 같은 재귀함수 recur이 있다.

recur은 내부에서 재귀호출이 두번 실행되는 순수하게(genuinely) 재귀적인 함수다.

import java.util.*;

public class Main {
    //재귀 함수
    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 scanner = new Scanner(System.in);

        System.out.print("정수를 입력하세요: ");
        int x = scanner.nextInt();

        recur(x);
    }
}

이제 이 함수를 재귀호출없이 같은 기능을 하는 함수로 수정해볼것이다.

 

먼저 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;
    }
}

이렇게 꼬리 재귀는 제거됐는데 문제는 앞에 있는 재귀메서드이다.

 recur(n-1)이 모두 실행되고, 그 다음에 n이 출력돼야 하므로,  recur(n-1)이 실행되는동안 n을 어딘가에 잠시 담아둬야 한다. 그리고 이를 위해 우리는 스택을 사용해 볼 것이다.

여기서 사용할 스택에 대한 설명은 아래 링크에서 확인할 수 있다.

https://star-peanuts.tistory.com/53

스택(Stack)

import java.util.*;

public class Main {

    static class IntStack{
        private int max; //스택 용량
        private int ptr; //스택 포인터
        private int[] stk; //스택 본체

        //실행시 예외: 스택이 비어있음
        public class EmptyIntStackException extends RuntimeException{
            public EmptyIntStackException(){}
        }

        //실행시 예외: 스택이 가득 참
        public class OverflowIntStackException extends RuntimeException{
            public OverflowIntStackException(){}
        }

        //생성자
        public IntStack(int capacity){
            ptr = 0;
            max = capacity;
            try{
                stk = new int[max];
            } catch (OutOfMemoryError e){
                max = 0;
            }
        }

        //스택에 x를 푸시
        public int push(int x) throws OverflowIntStackException{
            if(ptr >= max)
                throw new OverflowIntStackException();
            return stk[ptr++] = x; //데이터 저장 후 포인터+1
        }

        //스택에서 데이터를 팝
        public int pop() throws EmptyIntStackException{
            if(ptr <= 0)
                throw new EmptyIntStackException();
            return stk[--ptr]; //이미 포인터가 하나 올라가있으므로 포인터-1하고 데이터 팝
        }

        //스택에서 데이터를 피크 (꼭대기에 있는 데이터 엿보기)
        public int peek() throws EmptyIntStackException{
            if(ptr<=0)
                throw new EmptyIntStackException();
            return stk[ptr-1];
        }

        //스택에서 x를 찾아 인덱스를 반환. 없으면 -1을 반환
        public int indexOf(int x){
            for (int i = ptr-1; i >= 0; i--) {
                if(stk[i]==x)
                    return i;
            }
            return -1;
        }

        //스택 비우기
        public void clear(){
            ptr = 0;
        }

        //스택의 용량을 반환
        public int capacity(){
            return max;
        }

        //스택에 현재 쌓여있는 데이터 수 반환
        public int size(){
            return ptr;
        }

        //스택이 비어있는지
        public boolean isEmpty(){
            return ptr<=0;
        }

        //스택이 가득 찼는지
        public boolean isFull(){
            return ptr>=max;
        }

        //스택 안의 모든 데이터를 바닥>꼭대기 순서로 출력.
        public void dump(){
            if(ptr<=0)
                System.out.println("스택이 비어 있습니다!");
            else{
                for (int i = 0; i < ptr; i++) {
                    System.out.print(stk[i]+" ");
                }
                System.out.println();
            }
        }
    }

    //재귀 함수
    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;
        }
    }

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

        System.out.print("정수를 입력하세요: ");
        int x = scanner.nextInt();

        recur(x);
    }
}

전체 코드는 이렇게 되는데 여기서 recur함수만 자세히 보자!

//재귀 함수
static void recur(int n){
    IntStack s = new IntStack(n);

    while (true){
    	//구간 A
        if(n>0){
            s.push(n);
            n = n-1;
            continue;
        }
        //구간 B
        if (s.isEmpty() != true){
            n = s.pop();
            System.out.println(n);
            n = n-2;
            continue;
        }
        //구간 C
        break;
    }
}

만약 recur(4)를 호출한다고 가정해보자.

 

4는 0보다 크므로 구간A에서 걸리게되고, 스택에 4를 추가하고 n은 n-1=3이 되고 continue문에 의해 다시 while문의 처음으로 돌아간다. 

그리고 이 과정을 n이 3, 2, 1일때 역시 동일하게 반복하고, 스택에는 4, 3, 2, 1이 쌓이게 된다.

그런데 스택에 마지막 1이 쌓인뒤에 n은 0이 된다.

따라서 이제는 구간A에 걸리지 못하고 구간B로 넘어가게 된다.

 

구간B에서는 스택에 쌓여있는 1을 꺼내서 n에 저장하고, 이 n을 출력하고, n을 2 줄여서 -1로 만들고, 다시 while문의 처음으로 돌아간다.

 

그리고 이 과정을 반복해서 n이 0이하가되면서 스택이 모두 비면 구간A,B 중 어떤것에도 걸리지 않고 구간C로 넘어가서 프로그램은 종료된다.

 

하노이의 탑

 

기둥번호를 1, 2, 3으로 나타내고, 시작기둥은 x, 목표기둥은 y로 둔다.

기둥번호의 합은 6이기 때문에 목표기둥이 어떤 기둥이더라도 중간기둥은 6-x-y이다.

import java.util.*;

public class Main {
    //no개의 원반을 x번 기둥에서 y번 기둥으로 옮김
    static void move(int no, int x, int y){
        if(no>1)
            move(no-1, x, 6-x-y);
        System.out.println("원반["+no+"]을"+x+" 기둥에서 "+y+"기둥으로 옮김");
        if(no>1)
            move(no-1, 6-x-y, y);
    }

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

        System.out.println("하노이의 탑");
        System.out.print("원반 개수: ");
        int n = scanner.nextInt();

        move(n, 1, 3); //1번 기둥의 n개 원반을 3번 기둥으로 옮김.
    }
}

 

8퀸 문제

8퀸문제란 서로 공격하여 잡을 수 없도록 8개의 퀸을 8*8 체스판에 놓는 문제이다.

퀸은 같은 열,행에 있거나 자신의 대각선에 있는 다른 퀸을 공격하여 잡을 수 있다.

따라서 8개의 퀸이 각각 서로의 대각선이나 같은 행,열에 위치하지 않게 놓이는 경우의 수를 찾아야한다.

 

우선 각 열에 퀸을 한개만 배치하기로 하고, 퀸을 배치할 수 있는 모든 조합을 가지뻗기(Branching)로 생각해보자.

import java.util.*;

public class Main {
    static  int[] pos = new int[8];

    //각 열의 퀸의 위치를 출력
    static void print(){
        for (int i = 0; i < 8; i++) {
            System.out.printf("%2d", pos[i]);
        }
        System.out.println();
    }

    //i열에 퀸을 놓기
    static void set(int i){
        for (int j = 0; j < 8; j++) {
            pos[i] = j;
            if(i==7)
                print();
            else
                set(i+1);
        }
    }

    public static void main(String[] args) {
        set(0);
    }
}

이렇게 하면 8*8*8*8*8*8*8*8 = 16777216개의 조합의 수가 나온다.

그러면 이제 각 행에도 퀸을 1개만 배치하기로 하자.

import java.util.*;

public class Main {
    static boolean[] flag = new boolean[8];
    static  int[] pos = new int[8];

    //각 열의 퀸의 위치를 출력
    static void print(){
        for (int i = 0; i < 8; i++) {
            System.out.printf("%2d", pos[i]);
        }
        System.out.println();
    }

    //i열에 퀸을 놓기
    static void set(int i){
        for (int j = 0; j < 8; j++) {
            if(flag[j]==false){
                pos[i] = j;//i열의 퀸은 j행에 배치
                if(i==7)
                    print();
                else{
                    flag[j] = true; //j행에 배치된 퀸이 있으므로 flag[j]는 true로 둔다.
                    set(i+1); //set(i+1) 재귀호출+실행이 끝나면 퀸이 j행에서 제거된다.
                    flag[j] = false; //flag[j]를 false로 바꾼다.
                }
            }
        }
    }

    public static void main(String[] args) {
        set(0);
    }
}

이렇게 필요하지 않은 분기를 없애서 불필요한 조합을 줄이는 방법을 한정(bounding)조작이라고 하고,

가지뻗기와 한정조작을 조합하여 문제를 푸는 방법을 분기한정법이라고 한다.

 

이제 마지막으로 8*8 체스판에서 나올수있는 모든 대각선에 퀸이 1개씩만 놓이는 한정조작을 추가하자.

import java.util.*;

public class Main {
    static boolean[] flag_a = new boolean[8]; //각 행에 퀸을 배치했는지
    static boolean[] flag_b = new boolean[15]; // "/"대각선 방향으로 퀸을 배치했는지
    static boolean[] flag_c = new boolean[15]; // "\"대각선 방향으로 퀸을 배치했는지
    static  int[] pos = new int[8]; //각 열의 퀸의 위치

    //각 열의 퀸의 위치를 출력
    static void print(){
        for (int i = 0; i < 8; i++) {
            System.out.printf("%2d", pos[i]);
        }
        System.out.println();
    }

    //i열에 퀸을 놓기
    static void set(int i){
        for (int j = 0; j < 8; j++) {
            if(flag_a[j]==false && flag_b[i+j]==false && flag_c[i-j+7]==false){
                pos[i] = j;
                if(i==7)
                    print();
                else{
                    flag_a[j] = flag_b[i+j] = flag_c[i-j+7] = true;
                    set(i+1);
                    flag_a[j] = flag_b[i+j] = flag_c[i-j+7] = false;
                }
            }
        }
    }

    public static void main(String[] args) {
        set(0);
    }
}

같은 행, / 대각선방향, \ 대각선방향중 어느것이든 1개의 라인이라도 퀸이 배치되었으면 그 칸에는 이제 퀸을 놓을 필요가 없으므로 퀸을 놓는 실행을 건너뛴다.

flag_a[j]==false && flag_b[i+j]==false && flag_c[i-j+7]==false

다시말해 이렇게 같은 행에도, / 대각선에도, \ 대각선에도 퀸이 놓이지 않은 경우에만 퀸을 놓는 실행을 한다.

이 프로그램을 실행하면 총 92개의 조합이 출력된다.