Как это сделать через рекурсию?

using System;
 
class Program
{
    public int[,] a = new int[37, 50];
    public int n;
    public int k;
    public int rec(int i, int t)
    {
        if (i == 0)
        {
            if (t == k)
            {
                return 1;
            }
            else
            {
                return 0;
            }
        }
        if (t + i <= k)
        {
            if (a[i, t] == 0)
            {
                a[i, t] += rec(i - 1, t + 1);
                a[i, t] += rec(i + 1, t + 1);
            }
        }
        return a[i, t];
    }
    static int Main()
    {
        string str = Console.ReadLine().ToString();
        string[] result = str.Split(' ');
        string n = result[0];
        string k = result[1];
        Program lol = new Program();
        lol.n = int.Parse(n);
        lol.k = int.Parse(k);
        Console.Write(lol.rec(lol.n, 0));
        Console.ReadKey();
        return 0;
    }
}

        /// <summary>Определение количесво вариантов прохождения пути
        /// длинной N за К шагов</summary>
        /// <param name="k">Количество шагов</param>
        /// <param name="n">Длина пути</param>
        public static long CountPaths(int n, int k)
        {
 
            /// Количество шагов и длина пути должны быть
            /// оба чётны или нечётны
            if ((k + n) % 2 != 0)
                return 0;
 
            /// Словарь рачитанных вариантов
            Dictionary<KeyValuePair<int, int>, long> calc = new Dictionary<KeyValuePair<int, int>, long>();
 
            return _сount(k, n);
            long _сount(int step, int length)
            {
                /// Если длина пути отрицательна, значит магазин уже пройден
                /// Если длина пути равна нулю, значит до магазина уже дошли 
                /// В обоих случаях вариантов сделать следующие шаги нет
                if (length <= 0)
                    return 0;
 
                /// Если количество шагов меньше длины пути, то вариантов нет
                if (step < length)
                    return 0;
 
                /// Если количество шагов равно длине пути, то вариант 1
                if (step == length)
                    return 1;
 
                /// Проверка расчитывался ли уже такой вариант
                /// Если не расчитывался, то его расчёт
                KeyValuePair<int, int> pair = new KeyValuePair<int, int>(step, length);
                if (!calc.TryGetValue(pair, out long count))
                {
                    /// Количесво вариантов равно сумме вариантов
                    /// при шаге назад и при шаге вперёд
                    count =
                        _сount(step - 1, length + 1) // Шаг Назад
                        + _сount(step - 1, length - 1); // Шаг вперёд
                    /// Запись варианта в словарь
                    calc[pair] = count;
                }
                /// Если возврат значения
                return count;
            }
        }

using System;
using System.Collections.Generic;
 
class Test
{
    class Program
    { 
        public static long CountPaths(int n, int k)
        {
            if ((k + n) % 2 != 0)
                return 0;
 
            Dictionary<KeyValuePair<int, int>, long> calc = new Dictionary<KeyValuePair<int, int>, long>();
 
            return _сount(k, n);
            long _сount(int step, int length)
            {
 
                if (length <= 0)
                    return 0;
 
                if (step < length)
                    return 0;
 
                if (step == length)
                    return 1;
 
                KeyValuePair<int, int> pair = new KeyValuePair<int, int>(step, length);
                if (!calc.TryGetValue(pair, out long count))
                {
                    count =
                        _сount(step - 1, length + 1) 
                        + _сount(step - 1, length - 1); 
                    calc[pair] = count;
                }
                return count;
            }
        }
 
        static void Main(string[] args)
        {
            string[] inputArr = Console.ReadLine().Split();
            int n = int.Parse(inputArr[0]);
            int k = int.Parse(inputArr[1]);
            Console.WriteLine(CountPaths(k, n));
            Console.ReadKey();
        }
    }
}

 string[] inputArr = Console.ReadLine().Split();
            int n = int.Parse(inputArr[0]);
            int k = int.Parse(inputArr[1]);

string[] inputArr = Console.ReadLine().Split(' ');
            int n = int.Parse(inputArr[0]);
            int k = int.Parse(inputArr[1]);
            Console.WriteLine(CountPaths(k, n));
            Console.ReadKey();

    class Program
    {
        /// <summary>Определение количество вариантов прохождения пути
        /// длинной N за К шагов</summary>
        /// <param name="k">Количество шагов</param>
        /// <param name="n">Длина пути</param>
        public static long CountPaths(int n, int k)
        {
 
            /// Количество шагов и длина пути должны быть
            /// оба чётны или нечётны
            if ((k + n) % 2 != 0)
                return 0;
 
            /// Словарь рассчитанных вариантов
            Dictionary<KeyValuePair<int, int>, long> calc = new Dictionary<KeyValuePair<int, int>, long>();
 
            return _сount(k, n);
            long _сount(int step, int length)
            {
                /// Если длина пути отрицательна, значит магазин уже пройден
                /// Если длина пути равна нулю, значит до магазина уже дошли 
                /// В обоих случаях вариантов сделать следующие шаги нет
                if (length <= 0)
                    return 0;
 
                /// Если количество шагов меньше длины пути, то вариантов нет
                if (step < length)
                    return 0;
 
                /// Если количество шагов равно длине пути, то вариант 1
                if (step == length)
                    return 1;
 
                /// Проверка рассчитывался ли уже такой вариант
                /// Если не рассчитывался, то его расчёт
                KeyValuePair<int, int> pair = new KeyValuePair<int, int>(step, length);
                if (!calc.TryGetValue(pair, out long count))
                {
                    /// Количество вариантов равно сумме вариантов
                    /// при шаге назад и при шаге вперёд
                    count =
                        _сount(step - 1, length + 1) // Шаг Назад
                        + _сount(step - 1, length - 1); // Шаг вперёд
                    /// Запись варианта в словарь
                    calc[pair] = count;
                }
                /// Возврат значения
                return count;
            }
        }
 
        static void Main(string[] args)
        {
 
            string[] inputArr = Console.ReadLine().Split();
            int n = int.Parse(inputArr[0]);
            int k = int.Parse(inputArr[1]);
            Console.WriteLine(CountPaths(n, k));
 
            Console.ReadKey();