using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace ForProgCS
{
    class Program
    {
        static int fib_rec(int n)
        {
            if (n == 0) return 0;
            if (n > 0 && n < 3) return 1;
            else return fib_rec(n - 1) + fib_rec(n - 2);
        }

        static int fib_iter(int n)
        {
            int a = 0;
            int b = 1;
            for (int i = 0; i < n; i++)
            {
                b += a;
                a = b - a;
            }
            return a;
        }

        static void Main(string[] args)
        {
            var stoper = new Stopwatch();
            Console.WriteLine("Recursive start: {0}", stoper.ElapsedMilliseconds);
            stoper.Start();
            Console.WriteLine("Result: {0}", fib_rec(40));
            stoper.Stop();
            Console.WriteLine("Recursive stop: {0}", stoper.ElapsedMilliseconds);

            stoper.Reset();
            Console.WriteLine("\nIternation start: {0}", stoper.ElapsedMilliseconds);
            stoper.Start();
            Console.WriteLine("Result: {0}", fib_iter(40));
            stoper.Stop();
            Console.WriteLine("Iteration stop: {0}", stoper.ElapsedMilliseconds);
        }
    }
}