Задача про наименьшее количество купюр и рекурсия - C#

Формулировка задачи:

Вот такая классическая задачка есть: В некоторой стране используются денежные купюры достоинством в 1, 2, 4, 8, 16, 32 и 64. Дано натуральное число п. Как наименьшим количеством таких денежных купюр можно выплатить сумму п (указать количество каждой из используемых для выплаты купюр)? Предполагается, что имеется достаточно большое количество купюр всех достоинств. С вечера что то не думалось, а вот с утра написал рекурсию. Ребят мне кажется я тут намудрил, как это упростить, если возможно(только рекурсия).

namespace kupur
{
    class Program
    {
        static void Podschet_kupyur(int sum, int kup)
        {
            if (kup > 0)
            {
                if (sum >= kup)
                {
                    int kolvo = sum / kup;
                    int count = sum % kup;
                    sum = count;
                    if (sum <= kup)
                    {
                        Podschet_kupyur(sum, kup / 2);
                    }
                    Console.WriteLine("Купюр номиналом {0}\t{1} штук", kup, kolvo);
                }
                else
                {
                    Podschet_kupyur(sum, kup / 2);
                }
            }
        }
        
        static void Main(string[] args)
        {
            Console.WriteLine("Введи сумму ");
            int s = Convert.ToInt32(Console.ReadLine());
            int k = 64;
            Podschet_kupyur(s, k);
            Console.ReadKey();
        }
    }
}

Решение задачи: «Задача про наименьшее количество купюр и рекурсия»

textual
                            Листинг программы 
                        

                            using System;
 
/*
 * В некоторой стране используются денежные купюры достоинством в 1, 2, 4, 8, 16, 32 и 64.
 * Дано натуральное число п. Как наименьшим количеством таких денежных купюр можно выплатить
 * сумму п (указать количество каждой из используемых для выплаты купюр)? Предполагается, что
 * имеется достаточно большое количество купюр всех достоинств.
 */
namespace Recursion
{
    class WrongDataException : Exception
    {
        public override string ToString()
        {
            return "Введены неправильные данные";
        }
    }
    class Recursion
    {
        int _n = 1;
        public void Initialization()
        {
            Console.WriteLine("Введите сумму выплаты (целое положительное число)");
            try
            {
                int temp = int.Parse(Console.ReadLine());
                if (temp > 0)
                    _n = temp;
                else throw new WrongDataException();
            }
            catch (WrongDataException exc)
            {
                Console.WriteLine(exc);
            }
            finally {_difference = _n;}
        }
 
        private int _biggestValue=64;
        private int _difference;
        private int DivideBanknoteByTwo()
        {
            int numberOfPapers = _difference/_biggestValue;
            
            if(_difference%_biggestValue==0)
                return numberOfPapers;
 
            _difference -= numberOfPapers * _biggestValue;
            _biggestValue /= 2;
 
            return (DivideBanknoteByTwo() + numberOfPapers);
        }
 
        public void ShowNumberOfBanknotes()
        {
            Console.WriteLine("Наименьшее количество банкнот, " +
                              "которыми можно расплатиться" +
                              " за {0} составляет {1}.",
                              _n, DivideBanknoteByTwo());
            Console.ReadKey();
        }
    }
 
    class Program
    {
        static void Main()
        {
            Recursion _recursion=new Recursion();
            _recursion.Initialization();
            _recursion.ShowNumberOfBanknotes();
        }
    }
}
/*
 * можно проверять сумму по модулю банкноты последовательным делением на 2 до тех пор, пока 
 * остаток равен нулю. Запоминаем последнее правильное решение в аккумуляторе. Вычитаем от введенного
 * п сумму и продолжаем с остатком те же действия. Наверное, всё это можно сделать через рекурсию.
 */
                        