using System;

​

public abstract class Transform

{

    public class Identity : Transform 

    {

    }

    public class V1 : Transform

    {

        public readonly int n;

        public readonly Transform t;

        public V1(int n, Transform t)

        {

            this.n = n;

            this.t = t;

        }

    }

    public class V2 : Transform

    {

        public readonly int n;

        public readonly Transform t;

        public V2(int n, Transform t)

        {

            this.n = n;

            this.t = t;

        }

    }

​

}

public class Program

{

    public static int fibRec(int n)

    {

        if (n == 0 || n == 1) return n;

        return fibRec(n - 1) + fibRec(n - 2);

    }

    public static int fibIter(int nOuter)

    {

        Transform k = new Transform.Identity();

        var nIter = nOuter;

        while(true)

        {

            bool restart = false;

            if (nIter == 0 || nIter == 1)

            {

                while (true)

                {

                    if (k is Transform.Identity)

                    {

                        return nIter;

                    }

                    if (k is Transform.V1)

                    {

                        var v1 = k as Transform.V1;

                        nIter = nIter + v1.n;

                        k = v1.t;

                        continue;

                    }

                    if (k is Transform.V2)

                    {

                        var v2 = k as Transform.V2;

                        k = new Transform.V1(nIter, v2.t);

                        nIter = v2.n - 2;

                        restart = true;                     

                    }

                    break;

                }

            }       

            if (restart){ continue; }

            k = new Transform.V2(nIter, k);

            nIter = nIter - 1;

        }

    }

    public static void Main()

    {

        Console.WriteLine("fibRec(0): " + fibRec(0));

        Console.WriteLine("fibRec(1): " + fibRec(1));

        Console.WriteLine("fibRec(2): " + fibRec(2));

        Console.WriteLine("fibRec(3): " + fibRec(3));

        Console.WriteLine("fibRec(4): " + fibRec(4));

        Console.WriteLine("fibRec(5): " + fibRec(5));

        Console.WriteLine("fibIter(0): " + fibIter(0));

        Console.WriteLine("fibIter(1): " + fibIter(1));

        Console.WriteLine("fibIter(2): " + fibIter(2));

        Console.WriteLine("fibIter(3): " + fibIter(3));

        Console.WriteLine("fibIter(4): " + fibIter(4));

        Console.WriteLine("fibIter(5): " + fibIter(5));

    }

}