Как отсчитать сдачу с использованием рекурсии?

Question

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

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()+" купюр разного достоинства");
    }
}

Answer 1

Да, возможно.

Рекурсивной функции передаёте оставшуюся сумму, список номиналов, индекс, с которого нужно начинать, и список купюр.

Если остаток нулевой - return

Делим остаток на nominals[startindex], получаем количество соотв. купюр, добавляем их в список.

Вызываем функцию, передавая индекс на единицу больший, и остаток (то, что у вас s%(nominals[z]*enters))

Answer 2

Я бы для понимания рекурсии описал два идентичных примера с ней и без нее. Да, это не настолько лаконично, зато более наглядно. Это сделать можно, к примеру, так:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;

public class Task {
                
    public static void main(String[] args) {
        List<Integer> nominals = Arrays.asList(500, 100, 50, 10, 5, 2, 1); 
        int sum = 1348;
        List<Integer> recursion = recursion(nominals.iterator(), sum);
        List<Integer> nonRrecursion = nonRrecursion(nominals.iterator(), sum);
        System.out.println(recursion);
        System.out.println(nonRrecursion);
    }

    public static List<Integer> nonRrecursion(Iterator<Integer> iterator, int sum) {
        List<Integer> result = new ArrayList<>();   
        while(iterator.hasNext()){
            int nominal = iterator.next();
            int rest = sum%nominal;
            if (rest == 0) {
                result.add(nominal);
                break;
            }
            if (sum!=rest) {
                result.add(nominal);
                sum = rest;
            }
        }        
        return result;                
    }
    
    public static List<Integer> recursion(Iterator<Integer> iterator, int sum) {
        if (!iterator.hasNext()) return new ArrayList<>();
        Integer nominal = iterator.next();
        int rest = sum % nominal;
        if (sum != rest) {
            List<Integer> result = recursion(iterator, rest);
            result.add(nominal);
            return result;
        }
        else return recursion(iterator, rest);
    }

}

БЛОГ НА HUSL

Как отсчитать сдачу с использованием рекурсии?

Ответы (2 шт):