[Algorithm] Recursive

이번 장에서는 재귀(Recursive)를 활용하여 문제를 해결해본다.
모든 코드는 깃허브 (링크)의 테스트 코드로 정리해두었다.

---

재귀함수

자연수 N이 입력되면 재귀함수를 이용하여 1부터 N까지를 출력하는 프로그램을 작성하세요.

• 입력설명
  첫 번째 줄은 정수 N(3<=N<=10)이 입력된다.
• 출력설명
  첫째 줄에 출력한다.
• 입력예제 1
  3
• 출력예제 1
  1 2 3

public class RecursiveFunction {

    private List<Integer> answer = new ArrayList<>();

    public Integer[] solution1(int number) {
        if (number == 0) {
            return answer.toArray(new Integer[0]);
        } else {
            solution1(number - 1);
            answer.add(number);
        }
        return answer.toArray(new Integer[0]);
    }

    @Test
    @DisplayName("재귀함수")
    public void main() {
        Integer[] expectedAnswer = {1, 2, 3};
        Integer[] answer1 = solution1(3);
        assertArrayEquals(expectedAnswer, answer1);
    }

}

---

재귀함수를 이용한 이진수 출력

10진수 N이 입력되면 2진수로 변환하여 출력하는 프로그램을 작성하세요.
단 재귀함수를 이용해서 출력해야 합니다.

• 입력설명
  첫 번째 줄에 10진수 N(1<=N<=1,000)이 주어집니다.
• 출력설명
  첫 번째 줄에 이진수를 출력하세요.
• 입력예제 1
  11
• 출력예제 1
  1011

public class PrintBinary {

    StringBuilder answer = new StringBuilder();

    public String solution1(int number) {
        if (number == 0) {
            return answer.toString();
        } else {
            solution1(number / 2);
            answer.append(number % 2);
        }
        return answer.toString();
    }

    @Test
    @DisplayName("재귀함수를 이용한 이진수 출력")
    public void main() {
        String expectedAnswer = "1011";
        String answer1 = solution1(11);
        Assertions.assertEquals(expectedAnswer, answer1);
    }

}

---

팩토리얼

자연수 N이 입력되면 N!를 구하는 프로그램을 작성하세요.
예를 들어 5! = 54321=120입니다.

• 입력설명
  첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다.
• 출력설명
  첫 번째 줄에 N팩토리얼 값을 출력합니다.
• 입력예제 1
  5
• 출력예제 1
  120

public class Factorial {

    public int solution1(int number) {
        if (number == 1) {
            return 1;
        } else {
            return number * solution1(number - 1);
        }
    }

    @Test
    @DisplayName("팩토리얼")
    public void main() {
        int expectedAnswer = 120;
        int answer = solution1(5);
        assertEquals(expectedAnswer, answer);
    }

}

---

피보나치 재귀 (메모이제이션)

1) 피보나치 수열을 출력한다.
피보나치 수열이란 앞의 2개의 수를 합하여 다음 숫자가 되는 수열이다.
2) 입력은 피보나치 수열의 총 항의 수이다.
만약 7이 입력되면 1 1 2 3 5 8 13을 출력하면 된다.

• 입력설명
  첫 줄에 총 항수 N(3<=N<=45)이 입력된다.
• 출력설명
  첫 줄에 피보나치 수열을 출력합니다.
• 입력예제 1
  10
• 출력예제 1
  1 1 2 3 5 8 13 21 34 55

public class FibonacciNumbers {

    private int[] fibonacci;
    private int[] fibonacciMemo;

    public int solution1(int loop) {
        switch (loop) {
            case 1:
            case 2:
                return 1;
            default :
                return (solution1(loop - 2) + solution1(loop - 1));
        }
    }

    public int solution2(int loop) {
        switch (loop) {
            case 1:
            case 2:
                return fibonacci[loop - 1] = 1;
            default:
                return fibonacci[loop - 1] = solution2(loop - 2) + solution2(loop - 1);
        }
    }

    // 메모이제이션을 활용한 방법
    public int solution3(int loop) {
        if (fibonacciMemo[loop  - 1] != 0) {
            return fibonacciMemo[loop - 1];
        }
        switch (loop) {
            case 1:
            case 2:
                return fibonacciMemo[loop - 1] = 1;
            default:
                return fibonacciMemo[loop - 1] = solution3(loop - 2) + solution3(loop - 1);
        }
    }

    @Test
    @DisplayName("피보나치 재귀 (메모이제이션")
    public void main() {
        int loop = 10;
        int expectedAnswer1 = 55;
        int answer1 = solution1(loop);
        assertEquals(expectedAnswer1, answer1);

        fibonacci = new int[loop];
        int[] expectedAnswer2 = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55};
        solution2(loop);
        assertArrayEquals(expectedAnswer2, fibonacci);

        fibonacciMemo = new int[loop];
        int[] expectedAnswer3 = expectedAnswer2.clone();
        solution3(loop);
        assertArrayEquals(expectedAnswer3, fibonacciMemo);
    }

}

---

참고한 강의: https://www.inflearn.com/course/%EC%9E%90%EB%B0%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%ED%85%8C%EB%8C%80%EB%B9%84