[자료구조]피보나치 수열 재귀와 비재귀

1. 문제개요

C++을 이용하여 피보나치수열을 프로그래밍 하여본다. 단, 비재귀함수를 이용한 피보나치수열과 재귀함수를

이용한 피보나치수열 두 종류로 과제를 수행할 수 있도록 한다. 이때 각각의 방법에서 피보나치수열을 수행하는

함수가 몇 번 실행되었는지 Static 변수를 이용하여 출력할수 있도록 한다.

 

2. 문제분석

- 피보나치수열이란 무엇인가

▷ Fn = F(n-2) + F(n-1) 의 형식을 가지고 있는 수열을 피보나치수열이라 한다.

- 비재귀함수의 구현방법

▷ 반복문을 사용하여 입력받은 숫자만큼의 피보나치수열을 출력한다.

- 재귀함수의 구현방법

▷ 출력할 개수만큼을 입력받은 만큼 반복문을 수행한다. 반복문을 통하여 넘어오는 숫자를 비교하여 첫 번째와

두 번째 수열은 1을 리턴하고, 세 번째 이상의 수열부터는 재귀함수를 이용하여 피보나치 연산을 수행하고

결과를 리턴한다.

3. 결 과

- 소스부분

▷ 메인부

#include "fibonacci.h" // 피보나치 헤더파일 include

#include <iostream>

using std::cout;

using std::cin;

using std::endl;

int main()

{

 

fibonacci fibo; // 비재귀 피보나치 객체생성

 

fibo.setnum(); // 출력할 피보나치의 범위지정

fibo.accessfibo();// 비재귀 피보나치 수행

fibo.showfibo();// 피보나치 결과 출력

 

fibonacci recur;// 재귀함수 객체생성

 

int fibonaccinumber = 0;// 피보나치 범위저장 변수

 

cout << endl << endl << "Now start recursive fibonacci" << endl;

fibonaccinumber = recur.recurnum(fibonaccinumber);// 피보나치 범위값 입력

 

for(int i=0; i < fibonaccinumber; i++){

// 재귀 피보나치 실행

cout << "f[" << i+1 << "] : " << recur.resursive(i) << endl;

}

recur.count();// 재귀와 비재귀 실행횟수 출력

return 0;

}

▷ 헤더부

#ifndef _FIBO_H_// 재정의 오류방지

#define _FOBO_H_

 

class fibonacci{// 피보나치 클래스

 

public:

fibonacci();// 생성자

~fibonacci();// 소멸자

void accessfibo();// 피보나치 수행 함수

void showfibo();// 피보나치 출력함수

void setnum();// 피보나치 범위 입력함수

unsigned int resursive(int); // 재귀 피보나치 함수

int recurnum(int); // 자귀 피보나치 범위저장 함수

void count(); // 재귀 비재귀 횟수 출력 함수

private:

unsigned int *fibonum;// 피보나치값이 저장될 변수

int setfibo;// 피보나치 범위가 저장될 변수

};

#endif

 

▷ 실행부

#include <iostream> // 기본 입출력

using std::cout;

using std::cin;

using std::endl;

#include <iomanip>// 정렬

using std::setw;

 

#include "fibonacci.h" // 피보나치

 

static unsigned int countrecursive = 0; // 재귀 카운트 정적변수

static int nonrecurcount=0; // 비재귀 카운트 정적변수

 

fibonacci::fibonacci(){ // 생성자 부분

fibonum = new unsigned int [setfibo];

// 입렫받은 크기만큼 동적할당

}

 

void fibonacci::setnum(){ // 피보나치 범위 입력

while(int i=1){

cout << "pleas input fibonacci range(1~47)" << endl;

// 범위를 1~47로 제한

cout << "Input : ";

cin >> setfibo; // 범위 입력

 

if(setfibo >= 1 && setfibo < 48 ){

cout << "you input correct range" << endl;

// 제대로 된 입력범위일때

break;

}

else if(cin.fail())

{

//1~47값이 아닐 때에 범위를 다시 알려주고 재입력

cin.clear();

cin.ignore(1,'\n');

cout << endl << "You input only 1~47" << endl;

}

}

}

 

void fibonacci::accessfibo(){ // 피보나치연산

 

nonrecurcount++; // 비재귀 카운트 증가

cout << "Start non-recursive" << endl;

for(int i=0; i<setfibo; i++){

if(i == 0 || i == 1){ // 첫번째 두번쨰 피보나치

fibonum[i] = 1;// 1로 정의

}

else if(i >= 2 && i < setfibo){ // 2 이상일때

fibonum[i] = fibonum[i-2] + fibonum[i-1];

// 피보나치 연산 수행

}

}

}

 

void fibonacci::showfibo() //피보나치 출력

{

cout << "fibonacci value is(1~" << setfibo << ")" << endl;

// 출력할 피보나치 범위를 알려줌

for(int i=0; i<setfibo; i++)

{

if(i%3==0) cout << endl; // 3번째 열이 출력될때마다 줄바꿈

 

//출력부 시작//

if(i>=0 && i <35){

cout << "f[" << i+1 << "]" << setw(3) << " : " << fibonum[i] << "\t\t";

// 정렬을 위하여 끝부분에 Tab 공간 2번출력

}

 

else{

cout << "f[" << i+1 << "]" << setw(3) << " : " << fibonum[i] << "\t";

// 정렬을 위하여 끝부분에 Tab 공간 1번출력

}

}

cout << endl;

delete [] fibonum;// 동적할당 해제

}

unsigned int fibonacci::resursive(int Rfibo){ // 재귀피보나치 수행

countrecursive++; // 재귀 카운트 증가

if(Rfibo<2)return 1; // 전송된 배열이 0번째 1번째면 1리턴

else

return fibonacci::resursive(Rfibo-2)+fibonacci::resursive(Rfibo-1);

// 0 또는 1이 아니면 재귀를 이용한 피보나치연산 수행

}

int fibonacci::recurnum(int fibonaccinumber){ //재귀함수 피보나치수열 개수 입력

while(int i=1){

cout << "pleas input fibonacci range(1~47)" << endl;

// 범위를 1~47로 제한

cout << "Input : ";

cin >> fibonaccinumber; // 범위 입력

 

if(fibonaccinumber >= 1 && fibonaccinumber < 48 ){

cout << "you input correct range" << endl;

// 제대로 된 입력범위일때

break;

}

else if(cin.fail()){

//1~47값이 아닐 때에 범위를 다시 알려주고 재입력

cin.clear();

cin.ignore(1,'\n');

cout << endl << "You input only 1~47" << endl;

}

}

return fibonaccinumber; // 입력받은 값 리턴

}

 

void fibonacci::count(){

cout << endl;

cout << "Non recursive function called : " << nonrecurcount << endl;

//비재귀 카운트 출력

cout << "Recusive function called : " << countrecursive << endl;

//재귀 카운트 출력

}

fibonacci::~fibonacci(){} // 소멸자

 

- 스크린샷

4. 느 낀 점

이번 자료구조 과제는 재귀함수와 비재귀함수를 사용하여서 피보나치수열을 프로그래밍 해보는 과제였습니다. 처음

과제를 하려고 보았을 때는 피보나치수열과 자료구조가 무슨 연관이 있을까 하는 의문이 들었습니다. 그냥 교수님께서

방학동안 굳은 머리를 한번 풀어보라고 내주신 과제였습니다. 피보나치수열은 C로도 몇 번 프로그래밍을 해본

경험이 있었기 때문에 별다른 어려움이 없었습니다. 클래스의 함수들을 호출해오는 메인부와 그 함수들을 정의해

놓은 클래스헤더파일 그리고 실질적으로 동작하는 실행파일로 나누어서 최대한 객체지향 기반으로 완성 하였습니다.

하지만 처음 완성하였을 때 발생했었던 문제가 있었습니다. 적은 개수의 피보나치수열은 문제가 없었지만 개수가

많아지면 엉뚱한 값이 출력되는 경우가 발생했습니다. 곰곰이 생각한 결과 32비트기반의 CPU 와 OS를 사용하므로

2^32 만큼만 표현이 되는 것이라는 생각이 들었습니다. 하지만 계산상으로는 표현 가능한 숫자도 이상한 값이

나오는 경우가 있었습니다. 다시 생각해본 결과 보수화(Complement) 때문에 그렇다는 것을 알게 되었고, int 형으로

선언한 변수를 unsigned 변수로 선언하여 문제를 해결할 수 있었습니다. 그리고 비트상의 표현 한계 때문에 입력

제한을 47까지로 제한을 두었습니다. 그렇게 비재귀함수를 완벽히 완성한 후에 재귀함수를 사용하는 부분을 추가한 후

프로그램을 실행하였을 때 비로소 왜 이과제가 제출되었는지 짐작 할 수 있었습니다. 비재귀함수의 경우에는 어떠한

수를 입력하더라도 피보나치수열을 수행하는 함수를 한번만 호출하기에 시스템상의 자원을 크게 차지하지 않았습니다.

하지만 재귀함수의 경우에는 입력받은 숫자가 크면 클수록 시스템상의 자원을 많이 차지하고 실행 속도 또한 비재귀함수와

비교하여 눈에 띄게 느렸습니다. 프로그래밍을 마친 후 실행을 시켜보고 나서야 프로그래머가 프로그램을 작성할

경우에 시스템의 차지비율과 입력된 자료에 의하여 어떻게 작동할지 미리 생각을 하고 방식을 정한 후에 프로그래밍을

시작하여야 한다는 것을 알 수 있었습니다.