Заменить цикл на рекурсию — возможно ли в этом случае?

Question

[alexeidilos]

Возможно ли вместо цикла использовать рекурсию? Если да, то как?

P.S. Спасибо за внимание

public class task {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("Сколько вы хотите заплатить?");
        int S = scanner.nextInt(); //сумма к оплате
        int[] nominals = new int[]{500, 100, 50, 10, 5, 2, 1}; //какие купюры имеются
        ArrayList<Integer> paidNominalsArrayList = new ArrayList<Integer>(); // какие номиналы внесли
        //перебор числа S по убывающей ↓
        for (int s = S; s >= 1; s--) {
            // перебор номиналов по убывающей ↓
            for (int z = 0; z < nominals.length; z++) {
                //Если номинал входит в сумму хоть один раз ↓
                if ((s / nominals[z]) >= 1) {
                    System.out.println("Нужно заплатить: "+s);
                    int enters = s/nominals[z]; //сколько раз помещается купюра в числе
                    System.out.println("В сумме "+s+" помещается " +
                            enters+" купюр номиналом: " + nominals[z]+" р.");
                    for(int i=0; i<enters; i++){
                        //добавляем потраченный номинал в массив столько раз, сколько раз он входит в число
                        //System.out.println("Отправляем купюру: "+nominals[z]+" в массив");
                        paidNominalsArrayList.add(nominals[z]);
                    }
                    s = s%(nominals[z]*enters); //сколько останется заплатить
                    s++;
                    break;
                }
            }
        }
        // Сколько было потрачено РАЗНЫХ купюр? Чтобы узнать
        // помещаем нашу коллекцию в сет (в нём не бывает дубликатов)
        Set<Integer> set = new HashSet<>(paidNominalsArrayList);

        System.out.println("Было потрачено: "+ set.size()+" купюр разного достоинства");
    }
}

Comments

[mayton2019]

Я когда-то решал похожую задачу толи на leetcode, толи на codewars. Вот мой вариант на Haskell с рекурсией.
Смысл ответа - немножко другой. Но его легко переделать на нужный с группировкой и подсчетом.

payment' :: Int -> [Int] -> [(Int,Int)] -> [(Int,Int)]
payment' sum nom res
 | sum > 0   = if sum - h >= 0
               then payment' (sum - h) nom $ (h,1) : res
               else payment' sum (tail nom) res
 | otherwise = res
 where h = head nom

payment :: Int -> [(Int,Int)]
payment sum = payment' sum (reverse [1,2,5,10,50,100,500]) []

Prelude> payment 951
[(1,1),(50,1),(100,1),(100,1),(100,1),(100,1),(500,1)]

По поводу переписывания циклов на рекурсии. Иногда - это не очень удобно. Лучше переосмыслить
задачу и реализовать с нуля по новому.

Answer 1

[jcmvbkbc]

Возможно ли вместо цикла использовать рекурсию? Если да, то как?

С таким распределением номиналов банкнот -- можно, типа того:

static int foo(int s, const int *nom)
{
    if (! s)
        return 0;
    else
        return foo(s % nom[0], nom + 1) + s / nom[0];
}
...
static const int nom[] = {500, 100, 50, 10, 5, 2, 1};
printf("%d\n", foo(s, nom));