피보나치 수열 비재귀방법으로 풀기 - Fibonacci number without recursion

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

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

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

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

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

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];
    }
}

실행 결과