피보나치 수열 재귀함수 이용하지 않고

비재귀로 하는방법 좀 알려주세요~~


일단 재귀함수 이용하는건 했는데

비재귀는 어떻게 해야되는지 모르겠네요.. 더쉬울줄알았는데..

// 제가 작성한 피보나치 재귀함수 이용 버전입니다.



 

 Stack을 사용하면 됩니다 

 

○ 재귀함수를 없애는 가장 기본적인 방법은 Stack을 사용하는 것입니다. 재귀함수 자체가 실제로는 함수 Stack에 차곡차곡 결과값을 쌓고 있는 것입니다. 실제 Stack을 이용해서 값을 저장하면 그만입니다. 


○ 특히 피보나치수열의 경우는 진짜 Stack을 쓸 필요도 없고, Stack 처럼 동작하는 Array면 됩니다. 제 코드에서도 Pop() 함수는 작성을 했지만, 막상 부르는 곳이 없습니다. 지우기도 귀찮아서 일단 남겨둡니다. 


○ 참고로, 이 피보나치 수열은 0부터 시작하는 피보나치 수열입니다. 즉, 0, 1, 1, 2, 3, 5  순서로 진행됩니다. Wikipedia에 이것이 현대적인 형태라고 하더군요

https://en.wikipedia.org/wiki/Fibonacci_number



   코드 예제  
 

#include 
using namespace std;

/* stack */
int stack[100];
int top = -1;
int loop;
int push(int inputV);
int pop(void);

int fibonacciOne(int x);

int main()
{
    //피보나치 수열 재귀
    int n;
    cout << "몇번째 항의 값을 원합니까?";
    cin >> n;
    cout << "\n" << n << "번째 항은 " << fibonacciOne(n) << "입니다.";
    cin >> n;

    return 0;
}

int push(int inputV)
{
    if (top >= 99) //stack is full
    {
        return -1;	//Error
    }
    else
    {
        stack[++top] = inputV;
    }
}

int pop(void)
{
    if (top < 0)
    {
        return -1;	//Error
    }
    else
        return stack[top--];
}


int fibonacciOne(int x)
{
    /* init stack */
    for (loop = 0; loop < 100; loop++)
    {
        stack[loop] = 0;
    }
    top = -1;

    /* Set first two number of fibonacci array*/
    stack[0] = 0;
    stack[1] = 1;

    /* calculate Nth number */
    if (x <= 0)
    {
        return -1;	//Error
    }
    else if ((x == 1) && (x == 2))
    {
        return stack[x - 1];
    }
    else if (x >= 100) //too big for demo
    {
        cout << "Error\n";
        return -1;
    }
    else   //Normal case
    {
        for (loop = 2; loop < x; loop++)
        {
            stack[loop] = stack[loop - 2] + stack[loop - 1];
        }

        /* show all array */
        for (int loop = 0; loop < x; loop++)
        {
            cout << stack[loop] << " ";
        }

        return stack[x - 1];
    }
}



   실행 결과 
 





Posted by 지그프리드 지그프리드

댓글을 달아주세요:: 네티켓은 기본, 스팸은 사절


BLOG main image
일상, 프로그래밍, IT 그리고 직장생활, Dive, 여행 by 지그프리드

카테고리

Class List (402)
Studies (30)
Exercise & Quizz (10)
Term Project (0)
ECIM list (Help!) (10)
Issues & News (0)
Gossip about IT & Job (22)
Tools (2)
Think about the Justice (23)
Book Review (170)
조엘 온 소프트웨어(번역) (28)
Diary (87)
Vacations (9)
Clash of clans 클래시 오브.. (11)

글 보관함

달력

«   2019/12   »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31        
Total : 315,600
Today : 2 Yesterday : 22