Recursively counting combinations

[ThirdAge]

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:

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

[Athar]

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);

[ThirdAge]

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

[Athar]

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.

[ThirdAge]

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);

[Athar]

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.

[ThirdAge]

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.

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?

[Athar]

No, you're using postfix increment, meaning first the current value is taken and then cnt is incremented.
Just do return 1;

[ThirdAge]

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!