using System;

using System.Collections.Generic;

using System.Linq;

public class Program

{

    public static void Main()

    {

        Console.WriteLine("recursive sum");

        Console.WriteLine(RecursiveSum(new int[] {}));      // 0

        Console.WriteLine(RecursiveSum(new int[] { 7 }));   // 7

        Console.WriteLine(RecursiveSum(new int[] { 1, 2, 3, 4, 5 }));   // 15

        Console.WriteLine(RecursiveSum(new int[] { -1, 2 }));   // 1

        Console.WriteLine("\r\n");

        Console.WriteLine("quick sort");

        foreach (var number in QuickSort(new int[] { 3, -5, 2, -9, 2 }))

        {

            Console.WriteLine(number);

        }

        Console.WriteLine("\r\n");

        Console.WriteLine("factorial");

        Console.WriteLine(FactorialRecursive(5));

        Console.WriteLine("\r\n");

        Console.WriteLine("fibonacci");

        Console.WriteLine(Fibonacci(8));

        Console.WriteLine("\r\n");

        Console.WriteLine("find max recursive");

        Console.WriteLine(FindMaxRecursive(new int[] { 2, 5, 11, 0 }, -1));

        Console.WriteLine("\r\n");

        Console.WriteLine("find min");

        Console.WriteLine(FindMin(new int[] { 2, 5, 11, 0, -6 }));

        Console.WriteLine("\r\n");

        Console.WriteLine("find array length recursive");

        Console.WriteLine(FindArrayLengthRecursive(new int[] { }, 0));

        Console.WriteLine(FindArrayLengthRecursive(new int[] { 2 }, 0));

        Console.WriteLine(FindArrayLengthRecursive(new int[] { 2, 5, 11, 0 }, 0));

        Console.WriteLine("\r\n");

        Console.WriteLine("find array length");

        Console.WriteLine(FindArrayLength(new int[] { }));

        Console.WriteLine(FindArrayLength(new int[] { 2 }));

        Console.WriteLine(FindArrayLength(new int[] { 2, 5, 11, 0 }));

        Console.WriteLine("\r\n");

        Console.WriteLine("test");

        Test();

        Console.WriteLine("\r\n");

        Console.WriteLine("find index binary search recursive");

        Console.WriteLine(FindNameByTelephoneNumberBinarySearch(

            new Dictionary<string, int>

            {

                { "anna", 123 }

            },

            123));

        Console.WriteLine(FindNameByTelephoneNumberBinarySearch(

            new Dictionary<string, int>

            {

                { "anna", 123 },

                { "beata", 456 },

                { "claire", 789 },

                { "diana", 333 },

                { "elsa", 444 }

            },

            444));

        Console.WriteLine("\r\n");

    }

    private static int FindArrayLengthRecursive(int[] array, int length)

    {

        if (array.Length == 0)

            return length;

        else

        {

            var list = new List<int>(array);

            length++;

            list.RemoveAt(0);

            return FindArrayLengthRecursive(list.ToArray(), length);

        }

    }

    private static int FindArrayLength(int[] array)

    {

        var length = 0;

        foreach (var number in array)

        {

            length++;

        }

        return length;

    }

    private static int FindMaxRecursive(int[] array, int max)

    {

        if (array.Length == 0)

            return max;

        else

        {

            var list = new List<int>(array);

            if (list[0] > max)

            {

                max = list[0];

            }

            list.RemoveAt(0);

            return FindMaxRecursive(list.ToArray(), max);

        }

    }

    private static int FindMin(int[] array)

    {

        var list = new List<int>(array);

        var min = list[0];

        foreach (var number in list.Skip(0))

        {

            if (number < min)

                min = number;

        }

        return min;

    }

    private static int FactorialRecursive(int number)

    {

        if (number == 1)

            return 1;

        else return number * FactorialRecursive(number - 1);

    }

    private static int Fibonacci(int number)

    {

        if (number == 0 || number == 1)

            return number;

        else return Fibonacci(number - 1) + Fibonacci(number - 2);

    }

    private static int RecursiveSum(int[] array)

    {

        if (array.Length == 0)

            return 0;

        if (array.Length == 1)

            return array[0];

        else

        {

            var list = new List<int>(array);

            return list[0] + RecursiveSum(list.Skip(1).ToArray());

        }

    }

    private static string FindNameByTelephoneNumberBinarySearch(Dictionary<string, int> dictSorted, int number)

    {

        // base case

        if (dictSorted.Count == 1)

            if (dictSorted.ElementAt(0).Value == number)

                return dictSorted.ElementAt(0).Key;

            else

                return "not found";

        // recursive case

        else

        {

            var pivotIndex = dictSorted.Count / 2;

            // check pivot index

            if (dictSorted.ElementAt(pivotIndex).Value == number)

                return dictSorted.ElementAt(pivotIndex).Key;

            var newDict = new Dictionary<string, int>();

            var less = dictSorted.Where(kvp => kvp.Key[0] < dictSorted.ElementAt(pivotIndex).Key[0]).ToDictionary();

            var more = dictSorted.Where(kvp => kvp.Key[0] > dictSorted.ElementAt(pivotIndex).Key[0]).ToDictionary();

            if (less.Values.Contains(number))

                newDict = less;

            if (more.Values.Contains(number))

                newDict = more;

            return FindNameByTelephoneNumberBinarySearch(newDict, number);

        }

    }

    private static int[] QuickSort(int[] array)

    {

        if (array.Length < 2)

            return array;

        else

        {

            var lessList = new List<int>();

            var moreList = new List<int>();

            var sortedList = new List<int>();

            var listFromArray = new List<int>(array);

            var pivotIndex = array.Length / 2;

            var pivot = listFromArray[pivotIndex];

            listFromArray.RemoveAt(pivotIndex);

            listFromArray.ForEach(number =>

            {

                if (number <= pivot)

                    lessList.Add(number);

                else

                    moreList.Add(number);

            });

            sortedList.AddRange(QuickSort(lessList.ToArray()));

            sortedList.Add(pivot);

            sortedList.AddRange(QuickSort(moreList.ToArray()));

            return sortedList.ToArray();

        }

    }

    private static void Test()

    {

        var dict = new Dictionary<string, int>

        {

            { "anna", 123 },

            { "beata", 456 },

            { "claire", 789 },

            { "diana", 333 },

            { "elsa", 444 }

        };

        var pivot = dict.Count / 2;

        var less = dict.Where(kvp => kvp.Key[0] < dict.ElementAt(pivot).Key[0]).ToDictionary();

        var more = dict.Where(kvp => kvp.Key[0] > dict.ElementAt(pivot).Key[0]).ToDictionary();

        foreach (var key in less.Keys)

        {

            Console.WriteLine(key);

        }

        Console.WriteLine("///");

        foreach (var key in more.Keys)

        {

            Console.WriteLine(key);

        }

    }

}