알고리즘의 기본적인 스킬을 다룹니다.

이번 포스트에서는 알고리즘의 스킬 중 재귀에 대해서 알아 보려고 합니다.
목차는 다음과 같습니다.

1. Factorial
2. Fibonacci
3. Fibonacci Memoization
4. 관련 알고리즘 문제


Factorial

팩토리얼이라는 단어 많이 들어 보셨을 거라 생각합니다.
간단하게 다음과 같이 식을 세울 수 있습니다.

n! = n * (n - 1)!

즉 예시를 들어 보면 다음과 같겠죠. 
1
2
3
4
5
0! = 1
1! = 1 * (1 - 1)! = 1 * 0! = 1
2! = 2 * (2 - 1)! = 2 * 1! = 2
...
5! = 5 * (5 - 1)! = 5 * 4! = 120
이렇게 n!을 코드로 한번 작성해 보고자 합니다. 아마 대표적인 재귀함수의 기본이지 않을까 싶습니다.
그럼 이제 코드를 한번 살펴 보도록 하겠습니다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Factorial {

  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int N = Integer.parseInt(br.readLine());

    System.out.println(factorial(N));
  }

  // n! : n * (n-1)!
  // n! 계산
  private static long factorial(int n) {
    // 기저(재귀 탈출)
    if (n == 1)
        return 1;

    // 유도(파생)
    return n * factorial(n - 1);
  }
}
이 코드에서 중요한 점은 재귀를 선언하면 무한 반복을 돌지않게 하기 위해 `기저 조건` 과 `다시 호출`을 하는 것이 가장 중요합니다. 재귀로 하고자 한다면 다음과 같이 선언을 한 뒤 사용하는 것이 좋을 것 같습니다. ~(개인적인 견해 입니다.)~ 
1
2
3
4
5
6
7
private static long factorial(int n){
    // 기저 조건
    // 목표값에 도달했을 경우 빠져나가야 하기 때문입니다.

    // 파생 조건
    // 목표값에 도달했지 않았을 경우 계속 돌아야 하기 때문입니다.
}
코드는 직접 한번 작성해보시기 바랍니다 😌

## Fibonacci 피보나치 수열? 이 또한 많이 들어 보셨을 것 같습니다. 0번째 항을 0, 1번째 항을 1로 두고, 2번째 항부터는 바로 앞의 두 수를 더한 수가 됩니다. 16 번째 항까지만 나열해 보자면, 
1
0,  1,  1,  2,  3,  5,  8,  13,   21,   34,   55,   89,   144,  233,  377,  610,  987
규칙은 정말 간단하죠? 그럼 다음과 같이 식을 세울 수 있겠군요.

f(n) = f(n - 1) + f(n - 2)

이제 우리가 해야할 일은 f(n) 의 값은 과연 몇일까?🤔 를 구하는 것 입니다.
그럼 코드로 한번 구현을 해보도록 하겠습니다!

일단 위에서 말했지만, 재귀를 사용하기 위해서는 먼저 틀을 만들어야 합니다.

그리고 코드를 한번 볼까요?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Fibonacci {

  public static void main(String[] args) throws Exception {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int N = Integer.parseInt(br.readLine());
      System.out.println(fibonacci(N));
  }

  private static long fibonacci(int n) {
    // 1. 우선 재귀를 그만둘 수 있는 기저 조건
    // n이 0, 1일때 결과값은 0과 1이기 때문에 return n을 주었습니다.
    if (n <= 1) {
        return n;
    }
    // 그렇다면 계속 파생조건을 주어야 겠죠.
    return fibonacci(n - 1) + fibonacci(n - 2);
  }
}

계산이 어떻게 이루지는지 한번 보도록하겠습니다.

1
2
3
4
5
6
7
8
9
10
11
N에 4를 입력했을 경우,
1. fibonacci(4) 함수 호출
2. n <= 1 아니기 때문에 return fibonacci(4 - 1) + fibonacci(4 - 2) 중에 첫번째 fibbonacci(4 - 1) 함수 호출
3. n <= 1 아니기 때문에 return fibonacci(3 - 1) + fibonacci(3 - 2) 중에 첫번째 fibbonacci(3 - 1) 함수 호출
4. n <= 1 아니기 때문에 return fibonacci(2 - 1) + fibonacci(2 - 2) 중에 첫번째 fibbonacci(2 - 1) 함수 호출
5. n <= 1 이기때문에 return 1; 반환 후 4. 단계에서 두번째 fibonacci(2 - 2) 함수 호출 (현재 결과 값 1)
6. n <= 1 이기때문에 return 0; 반환 후 3. 단계에서 두번째 fibonacci(3 - 2) 함수 호출 (현재 결과 값 1)
7. n <= 1 이기때문에 return 1; 반환 후 2. 단계에서 두번째 fibonacci(4 - 2) 함수 호출 (현재 결과 값 2)
8. n <= 1 아니기 때문에 return fibonacci(2 - 1) + fibonacci(2 - 2) 중에 첫번째 fibbonacci(2 - 1) 함수 호출
9. n <= 1 이기때문에 return 1; 반환 후 8. 단계에서 두번째 fibonacci(2 - 2) 함수 호출 (현재 결과 값 3)
10. n <= 1 이기때문에 return 0; 반환 후 최종 결과 값 3 반환

이해가 가지 않을 수 있습니다. 눈으로 보는 것 보다, 그리고 머리로 생각하는 것 보다 손으로 한번 써보는게 더 기억에 잘 남는다고 하니 한번 손으로 작성해보는 것도 좋은 방법인듯 합니다.

자! 여기서 잠깐… 혹시 N의 입력 값에 42이상의 값을 입력 해보셨나요? 결과 값이 조금 늦게 나오지 않았나요?
음 늦게 나오지않았다면 정말 좋은 컴퓨터를 사용중이시네요 그럼 100을 입력해보시죠 하루를 걸려서라도 결과값은 나오지 않을거에요…

이거 왜이러는 걸까요?

그림을 한번 볼까요?

함수안에서 같은 함수를 호출(재귀)하게되면 콜스택에 쌓이게 됩니다. 그렇다면 위 그림을 비교해서 보자면 fibonacci(5) 즉, 5번째는 어떤 피보나치 수가 될지 확인해보기 위해서는 fibonacci(0)을 3번, fibonacci(1)을 5번, fibonacci(2)을 3번 … 이렇게 앞에 구했던 함수를 계속해서 함수 호출을 통해 5번째 피보나치 수를 구할 수 있게 됩니다.

그렇다면 이미 구했다면 더 이상 구하지 않게 하기 위해서는 어떤 방법이 필요할까요? 바로 Memoization! 을 이용하면 되겠습니다.



Fibonacci Memoization

우선 바로 코드를 보도록 하겠습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import java.util.Scanner;

public class FibonnaciMemoization {
    static long[] call1, call2, memo;
    static long totalCnt1, totalCnt2;

    private static long fibo(int n) { // 메모를 하지 않은 경우
        call1[n]++;
        totalCnt1++;
        if (n <= 1)
            return n;
        return fibo(n - 1) + fibo(n - 2);
    }

    private static long fibo2(int n) { // 메모를 한 경우
        call2[n]++;
        totalCnt2++;
        if (n <= 1)
            return n;
        // n항의 값을 계산한 적이 있었다면(메모 확인) 메모된 값 리턴
        if (memo[n] != 0) {
            return memo[n];
        }
        return memo[n] = fibo2(n - 1) + fibo2(n - 2);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        call1 = new long[N + 1];
        call2 = new long[N + 1];
        memo = new long[N + 1];
        System.out.println(fibo2(N));
        for (int i = 1; i <= N; i++) {
            System.out.println("fibo2(" + i + ") : " + call2[i]);
        }
        System.out.println("fibo2 call count : " + totalCnt2);
        System.out.println("============================");
        System.out.println(fibo(N));
        for (int i = 1; i <= N; i++) {
            System.out.println("fibo(" + i + ") : " + call1[i]);
        }
        System.out.println("fibo call count : " + totalCnt1);
        System.out.println("============================");
    }
}

이제 5 를 입력하고 돌려보시면 다음과 같은 결과를 보실 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
5
5
fibo2(1) : 2
fibo2(2) : 2
fibo2(3) : 2
fibo2(4) : 1
fibo2(5) : 1
fibo2 call count : 9
============================
5
fibo(1) : 5
fibo(2) : 3
fibo(3) : 2
fibo(4) : 1
fibo(5) : 1
fibo call count : 15
============================

같은 함수를 호출(재귀) 하면서 이전에 이미 구해놓았던 memo[-] 결과 값이 있다면 바로 리턴을 해주며 값을 계속 구하고 있는 모습을 보실 수 있습니다.

이렇게 돌려본 결과
단순히 재귀를 돌렸을 경우 총 카운트는 15번
메모이제이션을 한 뒤 돌렸을 경우 총 카운트는 9번
으로 함수 콜스택을 줄여준 결과를 보여주고 있습니다.



이렇게 재귀함수에 대해서 알아 보았습니다.
그럼 관련 알고리즘 문제 링크를 걸어드리며 마무리 짓도록 하겠습니다. 감사합니다.😁

관련 알고리즘 문제

  피보나치 수

  피보나치 수 2