fib 함수 교체 귀속

fib 함수 반복 구현:

        long Fib(long n) 
        {
            if (n <= 1)
            {
                return n;
            }
            else
            {
                var t1 = Fib(n - 1);
                var t2 = Fib(n - 2);

                return  t1+ t2;
            }

        }

fib 함수를 반복으로 변경합니다.

    class Class1
    {
        class Node
        {
            public Node(long n, int pos)
            {
                this.n = n;
                this.retStatus = pos;
            }

            public long n;         // 
            public int retStatus;
            //0， temp 
            //1,  temp t1 。
            //2， temp t2 。

            public long ret;      // 
            public long t1;      // Fib 
            public long t2;      // Fib 
        }

        long Fib(int n)
        {
            long temp = 0;

            var s = new Stack<Node>();
            s.Push(new Node(n, 0));

            while (s.Count > 0)
            {
                Node top = s.Peek();

                switch (top.retStatus)
                {
                    case 0:
                        if (n <= 1)
                        {
                            top.ret = n;
                            temp = top.ret;
                            s.Pop();
                        }
                        else
                        {
                            top.retStatus = 1;
                            s.Push(new Node(n - 1, 0));
                        }
                        break;
                    case 1:
                        top.t1 = temp;

                        top.retStatus = 2;
                        s.Push(new Node(n - 2, 0));
                        break;
                    case 2:
                        top.t2 = temp;

                        top.ret = top.t1 + top.t2;
                        temp = top.ret;
                        s.Pop();
                        break;
                }

            }
            return temp;

        }

    }