using System;

using System.Collections.Generic;

using System.Numerics;

​

namespace Training_Project

{

    internal class Program

    {

        static Dictionary<int, BigInteger> _fibonacciOfNumber = new();

        static int _callCountWithCaching = 0;

        static int _callCountWithoutCaching = 0;

​

        static void Main(string[] args)

        {

            var number = 30;

            var fibonacciWithCaching = FibWithCaching(number);

            Console.WriteLine($"With caching:    Fibonacci({number}) = {fibonacciWithCaching}. Method calls: {_callCountWithCaching}");

            var fibonacciWithoutCaching = FibWithoutCaching(number);

            Console.WriteLine($"Without caching: Fibonacci({number}) = {fibonacciWithoutCaching}. Method calls: {_callCountWithoutCaching}");

        }

​

        static BigInteger FibWithCaching(int n)

        {

            _callCountWithCaching++;

            if (n <= 2)

            {

                return 1;

            }

​

            if (!_fibonacciOfNumber.ContainsKey(n))

            {

                _fibonacciOfNumber[n] = FibWithCaching(n - 1) + FibWithCaching(n - 2);

            }

​

            return _fibonacciOfNumber[n];

        }

        static BigInteger FibWithoutCaching(int n)

        {

            _callCountWithoutCaching++;

            if (n <= 2)

                return 1;

​

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

        }

    }

}

​