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

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;
    }
}

    class Program
    {
        /// <summary>Определение количесво вариантов прохождения пути
        /// длинной N за К шагов</summary>
        /// <param name="k">Количество шагов</param>
        /// <param name="n">Длина пути</param>
        public static long CountPaths(int k, int n)
        {
            /// Если длина пути отрицательна, значит магазин уже пройден
            /// Если длина пути равна нулю, значит до магазина уже дошли 
            /// В обоих случаях вариантов сделать следующие шаги нет
            if (n <= 0)
                return 0;
 
            /// Если количество шагов меньше длины пути, то вариантов нет
            if (k < n)
                return 0;
 
            /// Количесвто шагов и длина пути должны быть
            /// оба чётны или нечётны
            ///
            if ((k + n) % 2 != 0)
                return 0;
 
            /// Если количество шагов равно длине пути, то вариант 1
            if (k == n)
                return 1;
 
            /// В остальных случаях количесво вариантов равно сумме вариантов
            /// при шаге назад и при шаге вперёд
            return
                CountPaths(k - 1, n + 1) // Шаг Назад
                + CountPaths(k - 1, n - 1); // Шаг вперёд
 
        }
 
        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();

    class Program
    {
        public static long CountPaths(int n, int k)
        {
            long[,] a = new long[37, 51];
            return _count(n, 0);
 
            long _count(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] += _count(i - 1, t + 1);
                        a[i, t] += _count(i + 1, t + 1);
                    }
                }
                return a[i, t];
            }
        }
 
        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();

        /// <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<(int steps, int length), long> calc = new Dictionary<(int steps, int length), 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;
 
                /// Проверка расчитывался ли уже такой вариант
                /// Если не расчитывался, то его расчёт
                if (!calc.TryGetValue((step, length), out long count))
                {
                    /// Количесво вариантов равно сумме вариантов
                    /// при шаге назад и при шаге вперёд
                    count =
                        _сount(step - 1, length + 1) // Шаг Назад
                        + _сount(step - 1, length - 1); // Шаг вперёд
                    /// Запись варианта в словарь
                    calc[(step, length)] = 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));

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace ConsoleApp32
{
    class Program
    {
        public static long CountPaths(int n, int k)
        {
 
            if ((k + n) % 2 != 0)
                return 0;
 
            Dictionary<(int steps, int length), long> calc = new Dictionary<(int steps, int length), 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;
 
                if (!calc.TryGetValue((step, length), out long count))
                {
                    count =
                        _сount(step - 1, length + 1) 
                        + _сount(step - 1, length - 1); 
                                                       
                    calc[(step, length)] = 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));
        }
    }
}

Dictionary<(int steps, int length), long> calc = new Dictionary<(int steps, int length), long>();

if (!calc.TryGetValue((step, length), out long count))
                {
                    count =
                        _сount(step - 1, length + 1) 
                        + _сount(step - 1, length - 1); 
                                                       
                    calc[(step, length)] = count;
                }