[Recursive] 재귀 알고리즘

재귀 알고리즘 설계

1. 재귀 메서드 설정 : 반환형 (void, int, long ..), 파라미터 (int n .. )

2. if (재귀 종료 조건) 재귀가 종료 되었을 경우 (Base Condition)

3. else (재귀 수행) : 재귀 로직 설정

 

예제

- 이진수 재귀

- 팩토리얼 재귀

- 피보나치 재귀

 

1. 이진수

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        dfs(n);
    }

    private static void dfs(int n) {
        if (n == 0) return;
        else {
            dfs(n / 2);
            System.out.print(n % 2);
        }
    }
}

 

 

 

2. 팩토리얼

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        System.out.print(dfs(n));
    }

    private static Long dfs(int n) {
        if (n == 1) return 1L;
        else {
            return n * dfs(n - 1);
        }
    }
}

 

 

3. 피보나치

 

재귀 방식

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        System.out.println(dfs(n));

    }

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

 

 

메모지에이션 (계산한 값은 기록해둔다, Top Down DP)

class Main {
    static int[] fibo;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        fibo = new int[n + 1]; 
        
        System.out.println(dfs(n));

    }

    private static int dfs(int n) {
        if (n == 1 || n == 2) return 1;
    	else if (fibo[n] > 0) return fibo[n];   
        else return dfs(n - 1) + dfs(n - 2);
    }
}

 

 

DP 방식

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n + 1];
        arr[0] = 0;
        arr[1] = 1;
        arr[2] = 1;
        
        dp(n, arr);

        for (int i = 1; i <= n; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    private static void dp(int n, int[] arr) {
        if (n == 2) return;
        else {
            dp(n - 1, arr);
            arr[n] = arr[n - 1] + arr[n - 2];
        }
    }
}

 

 

 

DP 방식과 재귀 방식 중 DP 방식이 성능이 더 뛰어나다.

재귀 방식은 스택 프레임을 이용하기 때문에 무겁다.