#include<stack>
#include<stdlib.h>
#include<iostream>
using namespace std;
typedef struct Node{
    int n = 0;//结点下标
    int tag = 0;//标志信息：1为左，2为右
};
int Fibnacci(int n)
{
    int sum = 0;
    stack<Node> s;
    Node w;
    do
    {
        while (n > 1)//先依次压入栈
        {
            w.n = n;
            w.tag = 1;
            s.push(w);
            n--;
        }
        sum = sum + n;
       while (!s.empty())
        {
            w = s.top();
            s.pop();  
            if (w.tag == 1)//如果是左子树，放到右边，压栈，n-2
            {
                w.tag = 2;
                s.push(w);
                n = w.n - 2;
                break;
            }
        }
    } while (!s.empty());
    return sum;
}
int main()
{
    printf("%d", Fibnacci(4));
    return 0;
}
-----------------------------------
栈和递归---斐波那契数列的非递归实现
https://blog.51cto.com/u_15127542/3722065