피보나치 수열 재귀, DP, loop 방법으로 구현하고 차이 확인

피보나치 수열을 이용한 재귀 프로그래밍은 대학교 1학년때 처음 재귀를 구하면서 접했었다.

당시에는 재귀의 예제로써 피보나치와 팩토리얼함수를 구현하는 것으로 소개되었다.

하지만 시간복잡도에 대해 다시 공부하던 중 우리가 배웠던 피보나치 수열의 재귀는 좋은 방식이 아니라는 것을 알게되었다.

피보나치 수열의 3가지 방식에 대해 구현해보고 차이를 느껴보자.

우선 피보나치 수열은 현재 값을 구하기위해서는 이전의 값(n-1)과 그 더 이전의 값(n-2)을 더하면서 구한다.

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

0, 1, 1, 2, 3, 5, 8, 13, 21, 34........

1) 재귀방식

재귀로 구현하는 방식은 가장 익숙한 방법이지만 매번 구할 때 마다 처음까지 가야하는 가장 안좋은 BigO(2^n)의 시간 복잡도를 가지게 된다.

/**
    * 재귀를 사용한 피보나치 수열
    * 
    * @param i
    * @return
*/
private static int recurSiveFibo(int i) {
    if (i <= 1) {
        return i;
    } else {
        return recurSiveFibo(i - 2) + recurSiveFibo(i - 1);
    }
}

2) Dynamic Programming

이전에 구해놓은 값을 이용하여 값을 구하는 방식인 DP 알고리즘을 구하면 BigO(n)의 시간 복잡도를 가지게 된다.

/**
     * DP 배열 생성
     * 
     * @param i
     * @return
*/
private static int getDpFibo(int fiboCnt) {
   fiboDpArray = new int[fiboCnt + 1];
        
   fiboDpArray[0] = 0;
   fiboDpArray[1] = 1;
        
   if (fiboCnt > 1) {
     for (int i = 2; i <= fiboCnt; i++) {
        fiboDpArray[i] = fiboDpArray[i - 2] + fiboDpArray[i - 1];
     }
   }
        
    return fiboDpArray[fiboCnt];
}

3) 반복문

반복문을 통해서 값을 구할 때도 동일하게  BigO(n)의 시간 복잡도를 가지게 된다.

/**
     * @param fiboCnt
     * @return
 */
private static int getLoopFibo(int fiboCnt) {
    if (fiboCnt <= 1) {
        return 1;
    } else {
        int a = 0;
        int b = 1;
        int sum = 0;
        
        for (int i = 2; i <= fiboCnt; i++) {
            sum = a + b;
            a = b;
            b = sum;
        }
            
        return sum;
    }
}

무턱대고 재귀함수를 사용하면 안되지만, 재귀함수가 그렇다고 어떤경우에도 다 안 좋은것은 아니다.

상황에 따라 시간복잡도를 잘 고려해서 사용하면 좋은 재귀를 쓸 수있을 것 같다.