C++로 피보나치 수열 출력하기: 동적 프로그래밍과 재귀 완벽 정리

피보나치 수열(Fibonacci Series)은 각 항이 바로 앞의 두 항의 합으로 이루어지는 수열입니다. 이 규칙에 따라 다음과 같은 정수 시퀀스가 만들어집니다.

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

피보나치 수를 정의하는 점화식은 아래와 같습니다.

F(n) = F(n-1) + F(n-2)
F(0) = 0
F(1) = 1

피보나치 수열 출력 프로그램

C++에서 피보나치 수열을 출력하는 대표적인 방법은 두 가지입니다. 하나는 동적 프로그래밍(Dynamic Programming), 다른 하나는 재귀 프로그래밍(Recursive Programming)입니다. 각각의 방법을 예제 코드와 함께 살펴보겠습니다.

방법 1: 동적 프로그래밍

예제 코드

#include<iostream>
using namespace std;
void fib(int n) {
   int f[n];
   int i;
   f[0] = 0;
   f[1] = 1;
   for (i = 2; i < n; i++) {
      f[i] = f[i-1] + f[i-2];
   }
   for (i = 0; i < n; i++) {
      cout<<f[i]<<" ";
   }
}
int main () {
   int n = 10;
   fib(n);
   getchar();
   return 0;
}

실행 결과

0 1 1 2 3 5 8 13 21 34

코드 설명

위 프로그램에서 main()은 프로그램의 진입점 역할을 하는 드라이버 함수입니다. 실제로 피보나치 수열을 생성하는 코드는 fib() 함수에 작성되어 있으며, main()에서 이 함수를 호출하여 실행합니다.

먼저 배열 f[n]을 선언하여 피보나치 수열의 처음 n개 항을 저장할 공간을 마련합니다. 그리고 배열의 첫 번째와 두 번째 요소를 각각 0과 1로 초기화합니다.

f[0] = 0;
f[1] = 1;

이후 for 반복문을 사용해 세 번째 항부터는 앞의 두 항을 더한 값을 배열에 차례대로 저장합니다.

for (i = 2; i < n; i++) {
   f[i] = f[i-1] + f[i-2];
}

마지막으로 반복문을 통해 배열에 저장된 피보나치 수열 전체를 화면에 출력합니다.

for (i = 0; i < n; i++) {
   cout<<f[i]<<" ";
}

동적 프로그래밍 방식은 각 항을 한 번씩만 계산하므로 시간 복잡도가 O(n)으로 효율적이라는 장점이 있습니다.

방법 2: 재귀 프로그래밍

이번에는 재귀 호출을 이용해 피보나치 수열을 출력하는 방법을 알아보겠습니다.

예제 코드

#include<iostream>
using namespace std;
int fib(int n) {
   if (n <= 1)
   return n;
   return fib(n-1) + fib(n-2);
}
int main () {
   int n = 10, i;
   for(i=0;i<n;i++)
   cout<<fib(i)<<" ";
   return 0;
}

실행 결과

0 1 1 2 3 5 8 13 21 34

코드 설명

위 프로그램에서는 for 반복문 안에서 재귀 함수를 호출하여 피보나치 수열의 각 항을 생성합니다. 즉, 수열의 모든 항에 대해 fib() 함수를 호출하는 방식입니다.

for(i=0;i<n;i++)
cout<<fib(i)<<" ";

fib() 함수는 n이 0 또는 1일 경우 해당 값을 그대로 반환합니다. 그렇지 않으면 자기 자신을 재귀적으로 호출하여 앞의 두 항의 합을 구하고, 올바른 값이 반환될 때까지 이 과정을 반복합니다.

if (n <= 1)
return n;
return fib(n-1) + fib(n-2);

재귀 방식은 코드가 간결하고 점화식을 직관적으로 표현할 수 있다는 장점이 있지만, 같은 값을 여러 번 중복 계산하기 때문에 n이 커질수록 실행 시간이 급격히 늘어나는 단점이 있습니다. 따라서 큰 n값을 다룰 때는 동적 프로그래밍 방식을 사용하는 것이 좋습니다.