재귀

재귀란?

예를 들자면 n! = 1 X 2 X 3 X … X (n-1) X n 이고, 여기서 맨 끝의 n을 제외하면 (n-1)!이 된다.

즉 n! = n X (n-1)!이다.

이처럼 어떤 문제나 함수 등이 자신과 성격이 똑같지만 크기가 더 작은 문제를 하나 이상 포함하고 있을 때 재귀적 구조를 갖고 있다고 말한다.

 

재귀 구조의 예

수열

• 초항이 1이고 공차가 3인 등차수열

public class Main {
    public static void main(String[] args){
        int n = 5;
        System.out.println(seq(n));
    }
    
    static int seq(int n) {
        if(n == 1) {
            return 1;
        }
        else {
            return seq(n-1) + 3;
        }
    }
}

재귀 알고리즘은 반복해서 호출하다가 언젠가 끝나야 하는데 이를 위한 경계 조건을 항상 갖고 있어야 한다.

if(n==1)이 수열의 초항이며 경계 조건이다.

• 피보나치 수열

public class Main {
    public static void main(String[] args){
        int n = 5;
        System.out.println(fib(n));
    }

    static int fib(int n) {
        if(n==1||n==2) {
            return 1;
        }
        else {
            return fib(n-1)+fib(n-2);
        }
    }
}

피보나치 수열은 재귀 알고리즘으로 구현하기에 부적합하다.

100번째 피보나치 수를 계산하기 위해 fib(100)을 수행하면 평생 기다려도 결과값을 볼 수 없다.

한 번 계산해놓은 결과를 계속 호출하여 지수함수적인 중복을 일으키기 때문이다.

하노이 탑

public class Main {
    public static void main(String[] args){
        int start = 1;
        int mid = 2;
        int end = 3;

        int n = 5;
        hanoi(n, start, mid, end);
    }

    static void hanoi(int n, int start, int mid, int end) {
         if(n==0) return;
        hanoi(n-1, start, end, mid);
        System.out.printf("%d -> %d\\n", start, end);
        hanoi(n-1, mid, start, end);
    }
}

선택 정렬

public class Main {
    public static void main(String[] args){
        int[] array = {5, 3, 6, 2, 8, 1, 4, 7};
        int n = array.length;
        selectionSort(array, n);
    }

    static void selectionSort(int[] array, int n) {
        if(n>1) {
            int max = 0;
            int maxIndex = 0;
            for(int i=0; i<n; i++) {
                if(array[i]>max) {
                    max = array[i];
                    maxIndex = i;
                }
            }
            int temp = array[n-1];
            array[n-1] = max;
            array[maxIndex] = temp;
            selectionSort(array, n-1);
        }
    }
}

깊이 우선 탐색(DFS)

• 무방향성, 크기 5로 가정

public class Main {
    static List<Integer>[] nodeList;
    static int[] visited;
    public static void main(String[] args){
        int N = 5;
        int[][] nodes = {{0, 1}, {0, 4}, {1, 3}, {1, 4}, {2, 3}};

        nodeList = new ArrayList[N];
        for(int i=0; i<N; i++) {
            nodeList[i] = new ArrayList<>();
            visited = new int[N];
        }

        for(int[] e : nodes) {
            nodeList[e[0]].add(e[1]);
            nodeList[e[1]].add(e[0]);
        }

        visited[0] = 1;
        DFS(0);
    }

    static void DFS(int current) {
        for(int next : nodeList[current]) {
            if(visited[next]==0) {
                visited[next] = 1;
                System.out.println(next);
                DFS(next);
            }
        }
    }
}