### Recursively counting combinations

So in my current assignment (one of the last few for the semester) I have to create a recursive function. What it does is it counts how many different ways you can enter a coin worth 3 cents or a coin worth 5 cents into the machine to buy a candy bar of price n....

For example: if the candy bar costs 11 cents. There are 3 ways to enter these coins: (3,3,5) (3,5,3) (5,3,3)

I'm having alittle trouble getting started; I thought abit about the base cases but I still don't know how to recursively count the ways you can combo:

 ``1234567891011121314`` ``````int coinCombos(int n, int k, int cnt){ //k starts 3 and cnt starts 0 if (n - k == 0) //pretty sure about this return cnt; else if (n == 0) //pretty sure about this return 0; else if ( (n - k) < 3 ) // case to handle change left over return 0; //this is supposed to happen according to the sheet. else return coinCombos(n, k + k, cnt++) //most definitely wrong.... }``````

I start k to be 3 in main because i figured it shouldn't matter to start 3 or 5, both are needed anyway, my function doesnt reflect that and I dont know where to begin implementing that either....I already have a case to handle if the candy bar IS 0 cents in main aswell.

I know it isn't right but some assistance would be greatly appreciated! I got the main down correctly. Spent an unproductive ~2 hours after getting this far
Last edited on
I don't get your approach. Are you trying to calculate C(n, k)? If so, you can't use that, unless I'm missing something - how many coins you have to insert depends on which ones you use (e.g. n=15).

Edit: assuming k is the current coin value, it makes sense - except for the last line. In particular, there's a lack of the numbers 3 and 5. Why k+k? What is cnt supposed to be for? You don't need it if you're returning the number of valid combinations.

Basically, the last line should be something similar to this:
`return coinCombos(n - k, 3) + coinCombos(n - k, 5);`
Last edited on
Thank you so much for replying! Sorry I had to run an errand...
Umm.... The goal of this program is to recursively count how many ways you can insert a combination of 3s and 5s up to n, given no remainder. Such as having 13, if you insert (3,3,3,3) you have a remainder of 1 coin, hence, it does not count as a combination.

Edit: The reason i have cnt (or count) is to count the number of times you can put in a combination of coins so there will be no remainder.

Edit2: I guess i had k+k because i wanted to increment so that n - k would eventually be 0 to increase count
Last edited on
 The reason i have cnt (or count) is to count the number of times you can put in a combination of coins so there will be no remainder.

Then cnt should be a reference, so the changes you make to it aren't lost when the function exists. If you return the number of valid combinations you found as you already do, cnt is completely superfluous.

 I guess i had k+k because i wanted to increment so that n - k would eventually be 0 to increase count

Then you'll end up with coin values like 6, 12, 24, 48... even though you only have 3 and 5 to choose from.
oooh I get it now, i was just trying to do too much within the function then...
So...then this would change my parameters i guess to only 2 values: n and k

Also, would it still be valid to call the function like this still in main? :
`coinCombos(n,3);`
Last edited on
 Also, would it still be valid to call the function like this still in main?

That will get you the number of possible combinations when you insert 3 as the first coin. You need to add coinCombos(n,5) to that.

Alternatively, you can call coinCombos(n,0) - however, since that's not obvious when you don't know the implementation of the function, I don't recommend it. I'd provide an overload that only takes n as a parameter.
I had 0 originally in main because I figured that the function will replace it with 3 and/or 5 when implementing the recursion but when i came back i was like "wait, this cant be right anymore" hahaha.

If you have the time do you mind helping me debug this program? I identified the error but I'm unsure how to fix it.

 ``123456`` ``````int coinCombos(int n, int k){ int cnt = 0; if ((n - k) == 0) //we've reached our destination. return cnt++;``````

just a sliver of the code, but the program always returns 0, if i put in that n = 3 it returns 0, etc. shouldn't it be incrementing count because of the return statement?
No, you're using postfix increment, meaning first the current value is taken and then cnt is incremented.
Just do `return 1;`
So when i made the variable cnt, it was completely unnecessary? Good to know how much I like to let a function do more than what is asked....

Edit: Thank you so much, Athar, for your help! It finally works!!!!! I'm so happy! Thank you, thank you!
Last edited on
Topic archived. No new replies allowed.