Chapter 05-2. 재귀 알고리즘_재귀 알고리즘 분석

재귀 함수 이해

package ch05_2;

import java.util.Scanner;

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

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

        recur(x);
    }
}
/*
정수를 입력하세요.: 4
1
2
3
1
4
1
2
 */

 

하향식 분석(top-down analysis)

가장 위쪽에 위치한 메서드를 호출하는 것부터 시작하여 계단식으로 자세히 조사해 가는 분석 기법

꼭대기부터 분석하다 보면 같은 메서드를 여러 번 호출할 수 있기에 반드시 효율적이진 않음

 

상향식 분석(bottom-up analysis)

아래쪽부터 쌓아 올리며 분석하는 방법

 

재귀 메서드 recur2 분석

package ch05_2;

import java.util.Scanner;

// 재귀 메서드 recur2 분석
public class Ex02_recur2 {
    // 재귀 메서드
    static void recur(int n) {
        if (n > 0) {
            recur(n - 2);
            System.out.println(n);
            recur(n - 1);
        }
    }

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

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

        recur(x);
    }
}
/*
상향식 분석
recur(1) -> recur(-1) 1 recur(0) -> 1
recur(2) -> recur(0) 2 recur(1) -> 2 1
recur(3) -> recur(1) 3 recur(2) -> 1 3 21
recur(4) -> recur(2) 4 recur(3) -> 21 4 1321

하향식 분석
recur(4) -> recur(2) 4 recur(3)
    recur(2) -> recur(0) 2 recur(1) -> 2
        recur(1) -> recur(-1) 1 recur(0) -> 1
    -> 4
    recur(3) -> recur(1) 3 recur(2)
        recur(1) -> recur(-1) 1 recur(0) -> 1
        -> 3
        recur(2) -> recur(0) 2 recur(1) -> 2
            recur(1) -> recur(-1) 1 recur(0) -> 1
 */

 

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

package ch05_2;

import ch04_1.IntStack;

import java.util.Scanner;

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

1. 꼬리 재귀를 제거 -> n값을 n-2로 업데이트하고 메서드 시작점으로 돌아감
2. 현재 n값을 잠시 저장하고 처리 후 저장했던 n값을 꺼내 출력
 */
public class Ex03_recurX1 {
    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 -= 2; // 꼬리 재귀를 제거
                continue;
            }
            break;
        }
    }

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

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

        recur(x);
    }
}

 

재귀 함수를 메모화로 구현

package ch05_2;

import java.util.Scanner;

// 재귀 함수를 메모화로 구현
public class Ex04_recurMemo {
    static String[] memo;

    // 메모화를 도입한 recur 메서드
    static void recur(int n) {
        if (memo[n + 1] != null) {
            System.out.print(memo[n + 1]); // 메모가 있는 경우 메모를 출력
        } else {
            if (n > 0) {
                recur(n - 1);
                System.out.println(n);
                recur(n - 2);
                memo[n + 1] = memo[n] + n + "\\n" + memo[n - 1]; // 메모가 없는 경우 메모화
            } else {
                memo[n + 1] = ""; // recur(0)과 recur(-1)은 빈 문자열
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("정수를 입력하세요.: ");
        int x = scanner.nextInt();

        memo = new String[x + 2];
        recur(x);
    }
}
/*
정수를 입력하세요.: 4
1
2
3
1
4
1
2
 */

 

재귀 함수 이해 - 호출한 횟수 카운트

package ch05_2;

import java.util.Scanner;

// 재귀 함수 이해 - 호출한 횟수 카운트
public class Ex05_recurCount {
    static int count;

    // 재귀 함수
    static void recur(int n) {
        count++;
        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);

        System.out.println("메서드 호출 횟수: " + count);
    }
}
/*
정수를 입력하세요.: 4
1
2
3
1
4
1
2
메서드 호출 횟수: 15
 */

 

재귀 함수를 메모화로 구현 - 호출한 횟수 카운트

package ch05_2;

import java.util.Scanner;

// 재귀 함수를 메모화로 구현 - 호출한 횟수 카운트
public class Ex06_recurMemoCount {
    static int count;
    static String[] memo;

    // 메모화를 도입한 recur 메서드
    static void recur(int n) {
        count++;
        if (memo[n + 1] != null) {
            System.out.print(memo[n + 1]); // 메모가 있는 경우 메모를 출력
        } else {
            if (n > 0) {
                recur(n - 1);
                System.out.println(n);
                recur(n - 2);
                memo[n + 1] = memo[n] + n + "\\n" + memo[n - 1]; // 메모가 없는 경우 메모화
            } else {
                memo[n + 1] = ""; // recur(0)과 recur(-1)은 빈 문자열
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("정수를 입력하세요.: ");
        int x = scanner.nextInt();

        memo = new String[x + 2];
        recur(x);

        System.out.println("메서드 호출 횟수: " + count);
    }
}
/*
1
2
3
1
4
1
2
메서드 호출 횟수: 9
 */