1,105,578 Community Members

C++ Recursive Function

Member Avatar
s11049151
Newbie Poster
3 posts since Oct 2009
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

hey,
I have to write a program that asks the user for an input amount (in cents) and the highest denominations of change (1c,5c,10c,20c & 50c). With these 2 inputs, the program then finds the distinct ways in which the change for the given amount can be made using the denomination as an upper bound, i.e. given 50cents, there are 57 ways in which the change can be given using 50 cents as the highest denomination, 56 ways using 20 cents as the highest denominations, 36 ways using 10 cents, 11 ways using 5 cents and only 1 way using 1cents.

This is part of my code:

int one_c() //one cent
{
return 1;
}

int five_c(int amount) //five cents
{
if (amount >= 0)
return five_c(amount-5) + one_c();
return 0;
}

int ten_c(int amount) //ten cents
{
if (amount >= 0)
return ten_c(amount-10) + five_c(amount);
return 0;
}

int twenty_c(int amount) //twenty cents
{
if (amount >= 0)
return twenty_c(amount-20) + ten_c(amount);
return 0;
}

int fifty_c(int amount) //fifty cents
{
if (amount >= 0)
return fifty_c(amount-50) + twenty_c(amount);
return 0;
}

Using these separate functions, I use the input denomination to call on the corresponding function (matching denomination).

What I want to do is to combine these functions into a recursive function so that my program can become more efficient.

Will be very grateful for any guidance.

Thanx.

Member Avatar
daviddoria
Posting Virtuoso
1,968 posts since Feb 2008
Reputation Points: 334 [?]
Q&As Helped to Solve: 204 [?]
Skill Endorsements: 8 [?]
Featured
 
0
 

The key to recursion is defining a base case. Here the base case should be "making change for a penny?".

Take a look at this:
http://programmingexamples.net/index.php?title=CPP/recursion

and see if it points you in the right direction.

You'll probably need to define an array with the possible values of a coin:

int coins[5] = {50,25,10,5,1};

and then make the recursive function

MakeChange(unsigned int coinId)

David

Member Avatar
s11049151
Newbie Poster
3 posts since Oct 2009
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

than you

Member Avatar
daviddoria
Posting Virtuoso
1,968 posts since Feb 2008
Reputation Points: 334 [?]
Q&As Helped to Solve: 204 [?]
Skill Endorsements: 8 [?]
Featured
 
0
 

Sure thing. It would be great if you could post your working code and then mark the thread as solved.

You
This article has been dead for over three months: Start a new discussion instead
Post:
Start New Discussion
View similar articles that have also been tagged: