using System;

using System.Collections;

using System.Collections.Generic;

using System.Diagnostics;

using System.IO;

using System.Linq;

namespace ConsoleApp

{

    public class Program

    {

        static int FibRec(int p1, int p2, int n)

        {

            return n == 0 ? p1 : FibRec(p2, p1 + p2, n - 1);

        }

        static int Fib(int n) { return FibRec(0, 1, n); }

​

        static int Fibonachi(int n, int p1 = 0, int p2 = 1)

        {

            if (n <= 1) return p1;

            int p;

            for (int j = 2; j < n; j++)

            {

                p = p1;

                p1 = p2;

                p2 = p2 + p;

            }

            return p2;

        }

​

        class FibonacciEnumerable : IEnumerable<int>

        {

            public IEnumerator<int> GetEnumerator()

            {

                int first = 0;

                yield return first;

                int second = 1;

                yield return second;

                while (true)

                {

                    int k = first + second;

                    first = second;

                    second = k;

                    yield return second;

                }

            }

​

            IEnumerator IEnumerable.GetEnumerator()

            {

                return GetEnumerator();

            }

        }

​

        public static void Main(string[] args)

        {

            var sp = new Stopwatch();

            sp.Start();

            int x = 0;

            for (int i = 0; i < 1000; i++) x += Fib(10000);

            sp.Stop();

            Console.WriteLine("recurse    : {0} {1}", sp.Elapsed, x);

            sp = new Stopwatch();

            sp.Start();

            x = 0;

            for (int i = 0; i < 1000; i++) x += Fibonachi(10000);

            sp.Stop();

            Console.WriteLine("loop       : {0} {1}", sp.Elapsed, x);

            sp = new Stopwatch();

            sp.Start();

            var fe = new FibonacciEnumerable();

            x = 0;

            for (int i = 0; i < 1000; i++) x += fe.Take(10000).Last();

            sp.Stop();

            Console.WriteLine("enumerable : {0} {1}", sp.Elapsed, x);

            for (int i = 0; i < 10; i++) Console.Write(" " + Fib(i).ToString());

            Console.WriteLine();

            for (int i = 0; i < 10; i++) Console.Write(" " + Fibonachi(i).ToString());

            Console.WriteLine();

            for (int i = 1; i < 10; i++) Console.Write(" " + (new FibonacciEnumerable()).Take(i).Last().ToString());

            Console.WriteLine();

        }

​

    }

​

}