[Algorithm] 피보나치 수열에 대하여!

안녕하세요. 게임개발자 놀이터 입니다.

이번 포스팅에선 피보나치 수열에 대하여 정리 해보려고합니다.

피보나치 수열

피보나치 수열은 앞의 두 수 를 더해서 현재 위치의 수를 만드는 수열을 말합니다.

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

시작 두 수 인 0, 1을 제외하고 3번째 수부터 바로 전 수 와 전 전 수의 합계를 나타내면 됩니다.

0, 1, (0+1) , ((0+1) + 1) , (((0+1) + 1) +(0+1)) ...

간단한 알고리즘이라서 그런지 구현 방법은 여러가지가 있습니다.

먼저 재귀함수 호출을 이용한 피보나치 수열 구현 입니다.

int Algorithm(int n){
    if (n == 1)
        return 0;
    else if (n == 2)
        return 1;
    else
        return Algorithm(n - 1) + Algorithm(n - 2);
}

1번째와 2번째의 값은 0과 1로 정해져있으니, 각각 0과 1을 반환하고, n의 전 값과, n의 전전 값을 더해서 리턴하는 형식을 가지고 있습니다.

간단하게 구현을 완료했지만, Algorithm 함수를 들어갈때마다 계속 n이 1인지, 2인지를 검사 하고 시작해야 하네요.

반복전인 2회 검사를 제거 하기 위해 이번엔 반복문으로 구현해봤습니다.

int Algorithm(int n){
    if (n == 1)
        return 0;
    else if (n == 2)
        return 1;
    else
    {
        int beforevalue = 0;
        int current = 1;
 
        for(int i=1; i<n; ++i)
        {
            int temp = current;
            current += beforevalue;
            beforevalue = temp;
        }
        return current;
    }
}

간단하게 재귀 함수를 호출하는 부분을 for문으로 변경해봤습니다.

current는 현재 숫자, beforevalue는 이전 숫자입니다.

다음 숫자는 현재 숫자 + 이전숫자 이므로, current와 beforevalue를 더해서 구합니다.

이것 외에 다른 방법은.. 성능상으로는 비슷하지만 코드상으로는 다른 '꼬리 재귀 함수'를 이용한 구현법이 있습니다.

int Algorithm(int n){
    return AlgorithmTail(n, 0, 1);
}
 
int AlgorithmTail(int n, int before, int next){
    if (n == 0)
        return before;
    else
        return AlgorithmTail(n - 1, next, before + next);
}

구하려는 n번째 자리수를 이용하여 n을 한단계씩 줄여가며 before와 next를 더해가는겁니다. 

한 타임이 지나면

before는 next가 되며

next는 before + next가 됩니다.

그렇게 반복되며 꼬리재귀함수를 돌다가 n값이 0 이라면 현재 값(before)를 반환합니다.

꼬리 재귀 함수에 관해선 다른 포스팅에서 자세히 다루도록 하겠습니다.

감사합니다.