[C] 재귀 함수로 피보나치 수열 출력

입력받은 개수만큼 피보나치 수열을 재귀 함수로 출력했습니다. 코드는 간단하지만 같은 값을 반복 계산하므로 N이 커지면 급격히 느려집니다.

1. 문제

N을 입력받아 피보나치 수열의 1번째부터 N번째 항까지 출력합니다. 1, 2번째 항은 1이고, 이후 항은 앞의 두 항의 합입니다.

입력: 10
출력: 1 1 2 3 5 8 13 21 34 55

2. 코드

#include <stdio.h>

int fibo(int i) {
    if (i == 1 || i == 2)
        return 1;                          // 1, 2번째 항은 1
    return fibo(i - 2) + fibo(i - 1);      // 앞의 두 항의 합
}

int main() {
    int a;
    scanf("%d", &a);
    for (int i = 1; i <= a; i++)
        printf("%d ", fibo(i));
    return 0;
}

3. 주의할 점

fibo(i)는 fibo(i-1)과 fibo(i-2)를 각각 다시 호출하므로 같은 항을 여러 번 계산합니다. 호출 횟수가 N에 대해 지수적으로 늘어나 N이 40을 넘어가면 눈에 띄게 느려집니다. 또 int 범위를 넘는 47번째 항부터는 값이 넘칩니다.

 

방식	시간 복잡도	특징
재귀	O(2^N) 수준	코드가 짧고 점화식과 모양이 같음
반복문 또는 메모이제이션	O(N)	이미 구한 값을 재사용

4. 정리

• 피보나치 수열은 fibo(n) = fibo(n-1) + fibo(n-2) 점화식을 그대로 재귀로 옮길 수 있습니다.
• 재귀 방식은 중복 계산이 많아 N이 크면 느립니다.
• 큰 N에는 반복문이나 메모이제이션을 쓰고, 자료형 범위(long long 등)도 함께 고려합니다.