[알고리즘] 재귀함수 - 피보나치 수열

재귀함수 - 피보나치 수열

피보나치 수열은 다음과 같다.

1,1,2,3,5,8,13,21,34,55,89,144,233,377...

즉, n+2항은 바로 뒤 2개의 항의 합으로 결정되는 구조이다.

1. 재귀함수 피보나치 수열

 

#include<stdio.h>
 
int main() {
    
    int num, result;
 
    scanf_s("%d", &num);
    result = fibo(num);
    printf("%d", result);
 
    return 0;
}
 
int fibo(int num) {
    
    if ((num == 1)||(num==2)) {
        return 1;
    }
 
    return fibo(num - 1) + fibo(num - 2);                                                                  
}
 

위의 점화식을 재귀함수로 구현하였다.

n+2가 아닌 n을 구해야하기 때문에 양변의 n값에 -2를 하였다. 

또한 num이 첫째항이거나 둘째항일때 1을 반환하도록 했다.

2. 메모이제이션(Memoization) 피보나치

 

#include<stdio.h>
 
#define Capa 100
 
int main() {
    
    int num, result;
 
    scanf_s("%d", &num);
    result = fibo(num);
    printf("%d", result);
 
    return 0;
}
 
int fibo(int num) {
    
    int buf[Capa];
 
    if (buf[num] > 0) {
        return buf[num];
    }
    if ((num == 1)||(num==2)) {
        return buf[num] = 1;
    }
 
    return buf[num] = fibo(num - 1) + fibo(num - 2);                                                       
}
 

다음은 메모이제이션으로 피보나치를 구현한 코드이다.

아래의 fibo 함수를 보면 1차원 행렬을 이용하여 계산된 값이 저장되는 것을 볼 수 있다.

이를 활용하면 앞에서 포스팅한 내용과 마찬가지로 불필요한 계산을 줄여

연산 속도를 높일 수 있다.