재귀(Recursion)는 함수가 자기 자신을 다시 호출하는 프로그래밍 기법입니다. 피보나치 수열은 각 항이 앞의 두 항의 합으로 정의되기 때문에 재귀적으로 표현하기에 적합한 대표적인 예제입니다.
다음은 재귀를 사용하여 피보나치 수열을 출력하는 C++ 프로그램입니다.
예제 코드
#include <iostream>
using namespace std;
int fib(int x) {
if((x==1)||(x==0)) {
return(x);
}else {
return(fib(x-1)+fib(x-2));
}
}
int main() {
int x , i=0;
cout << "Enter the number of terms of series : ";
cin >> x;
cout << "\nFibonnaci Series : ";
while(i < x) {
cout << " " << fib(i);
i++;
}
return 0;
}실행 결과
Enter the number of terms of series : 15 Fibonnaci Series : 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377
코드 설명
위 프로그램에서 실질적인 핵심 로직은 fib 함수에 들어 있습니다.
if((x==1)||(x==0)) {
return(x);
}else {
return(fib(x-1)+fib(x-2));
}이 코드의 동작 방식을 살펴보면 다음과 같습니다.
- 기저 조건(Base Case): x가 0 또는 1이면 더 이상 재귀 호출을 하지 않고 해당 값을 그대로 반환합니다. 이는 무한한 재귀 호출을 방지하는 역할을 합니다.
- 재귀 호출: 그 외의 경우에는 바로 앞의 두 항인 fib(x-1)과 fib(x-2)를 각각 호출하여 그 결과를 더해 반환합니다. 피보나치 수열의 정의 f(n) = f(n-1) + f(n-2)를 그대로 코드로 옮긴 것입니다.
main() 함수에서는 사용자로부터 출력할 항의 개수를 입력받은 후, while 반복문을 통해 0번째 항부터 차례대로 fib() 함수를 호출하며 수열을 화면에 출력합니다.
cout << "Enter the number of terms of series : ";
cin >> x;
cout << "\nFibonnaci Series : ";
while(i < x) {
cout << " " << fib(i);
i++;
}참고 사항
재귀 방식은 코드가 직관적이라는 장점이 있지만, 같은 값을 여러 번 중복 계산하기 때문에 항의 개수가 커지면 실행 시간이 지수적으로 증가하는 단점이 있습니다. 성능이 중요한 경우에는 메모이제이션(Memoization)을 적용하거나 반복문을 사용한 동적 계획법(DP) 방식을 고려하는 것이 좋습니다.