13. Recursive Fibonacci

3. Recursive Fibonacci
The Fibonacci sequence is quite a famous sequence of numbers. Each member of the sequence is calculated from the sum of the two previous elements. The first two elements are 1, 1. Therefore the sequence goes as 1, 1, 2, 3, 5, 8, 13, 21, 34…
The following sequence can be generated with an array, but that’s easy, so your task is to implement recursively.
So if the function GetFibonacci(n) returns the n’th Fibonacci number we can express it using GetFibonacci(n) = GetFibonacci(n-1) + GetFibonacci(n-2).
However, this will never end and in a few seconds a StackOverflow Exception is thrown. In order for the recursion to stop it has to have a “bottom”. The bottom of the recursion is GetFibonacci(2) should return 1 and GetFibonacci(1) should return 1.
Input Format:
•	On the only line in the input the user should enter the wanted Fibonacci number.
Output Format:
•	The output should be the n’th Fibonacci number counting from 1.


using System;

namespace _03RecursiveFibonacci
{
    class Program
    {
        static void Main(string[] args)
        {
            int num = int.Parse(Console.ReadLine());
            int[] array = new int[] { 1, 1 };
            int sum = 0;

            switch (num)
            {
                case 1:
                    Console.WriteLine("1");
                    return;
                case 2:
                    Console.WriteLine("1");
                    return;
            }

            for (int i = 2; i < num; i++)
            {
                sum = array[0] + array[1];
                int[] newArray = new int[] { array[1], sum };

                array = newArray;
            }
            Console.WriteLine(sum);
        }
    }
}
/*   Решение чрез Мемоизация
 // Top down DP: recursion + memoization
    private static long recursiveFibonacciWithMemoization(int n) {
        if (n <= 1) {
            return 1;
        }

        if (memo[n] != 0) {
            return memo[n];
        }

        memo[n] =
                recursiveFibonacciWithMemoization(n - 1) +
                        recursiveFibonacciWithMemoization(n - 2);
        return memo[n];
    }*/