## Question

Develop a recursive method to determine the number of distinct ways in which a given amount of money in cents can be changed into quarters, dimes, nickels, and pennies. Each line of input contains an amount. For example, if the amount is 17 cents, then there are six ways to make change:

1 dime, 1 nickel, and 2 pennies

1 dime, and 7 pennies

3 nickels and 2 pennies

2 nickels and 7 pennies

1 nickel and 12 pennies

17 pennies

Here are some input/output pairs. The first number in each pair is the amount, and the second number is the number of ways in which the amount can be changed into quarters, dimes, nickels, and pennies:

17 6

5 2

10 4

25 13

42 31

61 73

99 213

The method specification is

public static int ways(int amount, int denomination)

For the sake of simplifying the ways method, develop a coins method that returns the value of each denomination. Thus, coins (1) returns 1 - penny, coins (2) returns 5 - nickel, coins (3) returns 10 - dime and coins(4) returns 25 - quarter.

Test your methods ways and coins methods with a main method that reads in an integer amount in cents between 1 and 99, inclusive, and outputs the total number of ways that amount can be changed into quarters, dimes, nickels, and pennies, and each way in detail.

Hint: Let us simplify the problem as follows:

Given a positive integer n, how many ways can we make change for n cents using pennies, nickels, dimes and quarters?

Recursively, we could break down the problem as follows:

To make change for n cents we could:

1) Give the customer a quarter. Then we have to make change for n-25 cents

2) Give the customer a dime. Then we have to make change for n-10 cents

3) Give the customer a nickel. Then we have to make change for n-5 cents

4) Give the customer a penny. Then we have to make change for n-1 cents.

## Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

import java.util.Scanner;public class RecursiveMoney {

public static void main(String[] args)

{

Scanner input = new Scanner(System.in);

int amount;

System.out.print("Please enter an amount in cents to check for unique patterns: ");

amount = input.nextInt();

System.out.println("Number of distinct ways to make amount: " + ways(amount, 5));

input.close();

}

public static int ways(int amount, int denomination)

{

int total = 0;

amount = amount - coins(denomination);

if(amount >= 25 && denomination >= 4)

total += ways(amount, 4);

if(amount >= 10 && denomination >= 3)

total += ways(amount, 3);

if(amount >= 5 && denomination >= 2)

total += ways(amount, 2);

if(amount >= 1)

total += ways(amount, 1);

if(amount == 0)

return 1;

return total;

}...