Здравей. При рекурсия, много е важно да определиш точката в която матодът ще спре да извиква себе си, т.е. дъно на рекурсията. Можеш да си представиш рекурсията като цикъл. Ето един пример за фибоначи с рекурсия

static long FibonachiRecursion(int n)
{
   if (n <= 2)
   {
      return 1;
   }
   return FibonachiRecursion(n - 1) + FibonachiRecursion(n - 2);
}

Здравей,

добре е че си чул за мемоизацията, тя е наложителна при езици които нямат оптимизация при tail recursion (рекурсия при която функцията връща резултат от извикване на самата себе си). Мемоизацията е просто речник (асоциативен масив, мап, обект..) който пази (като кеш) вече пресметнати от функцията резултати, за да не се изчисляват едни и същи неща много пъти. Случая е точно такъв, ето решение:
 

using System;
using System.Collections.Generic;

class MainClass
{
    public static void Main()
    {       
        int n = int.Parse(Console.ReadLine());
        Console.WriteLine(SolveMemoization(n));
    }

    public static double SolveMemoization(int n)
    {
        double result;
        if (memo.ContainsKey(n))
        {
            result = memo[n];
        }
        else
        {
            result = SolveMemoization(n - 1) + SolveMemoization(n - 2);
            memo[n] = result;
        }
        return result;

    }

    static Dictionary<int, double> memo = new Dictionary<int, double>() {
            {1, 1},
            {2, 1}
        };
}