Recursive coin change c++

Question

My program seems to be crashing every time it recursive calling in the minimum function. Can anyone tell me why it is crashing. It would instantly freeze after i call the minimum function. Is it because im using a vector?

#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>

using namespace std;

int minimum(vector<int> denom, int s, int N) //take in denomination , sizeofcoin, and value of N
{
    if(N == 0)
    {
        return 1;
    }
    else if(N < 0 || (N > 0 && s <=0))
    {
        return 0;
    }
    else
    {
        return min(minimum(denom,s - 1, N), 1 + minimum(denom, s,N-denom[s-1]));
    }
}
int main()
{
    int N;
    unsigned int sizeofcoin;
    cout << "Enter the value N to produce: " << endl;
    cin >> N;
    cout << "Enter the number of different denominations: " << endl;
    cin >> sizeofcoin;

    vector<int> denom(sizeofcoin);
    for(unsigned int i= 0; i < sizeofcoin; i++)
    {
        cout << "Enter denomination #" << (i+1) << endl;          //save all the denominations in an array
        cin >> denom[i];
    }

    sort(denom.begin() , denom.end(),greater<int>());    //sort the array from largest to smallest
    if(denom.back() != 1)                                 //check the end of the array (since the back is smallest now) if it has 1
    {
        denom.push_back(1);                             //Will include 1 if the user does not input a 1 (doesn't have to be used)
    }
    minimum(denom,sizeofcoin,N);
    return 0;
}

can any1 help me i tried almost everything for recursive but i don't seem to understand what is is suppose to be doing ? — Darkflame
– Darkflame, Commented May 13, 2016 at 22:23

Sam Varshavchik · Accepted Answer · 2016-05-09 02:02:17Z

I tried to explain your minimum() function to your rubber duck, and your rubber duck has a question for you. Here's how our conversation went:

int minimum(vector<int> denom, int s, int N) //take in denomination , sizeofcoin, and value of N
{
    if(N <= 0)
    {
        return 0;
    }

Me: this minimum() recursive function immediately returns if its third parameter, N, is 0, or negative.

Your Rubber Duck: Ok.

    return (minimum(denom,s - 1, N)...

(Here, I tried explaining your first recursion call here, to your rubber duck):

Me: So, this makes a recursive call, with the same parameters, except that the 2nd parameter is decremented. The third parameter is N.

Your Rubber Duck: So, if the third parameter's value, N, is unchanged, and the recursive function returns without recursing only when N is 0 or negative, and the initial call to minimum() passes a value greater than 0 for N, then when exactly do you expect this recursion to stop?

I couldn't answer this question myself, maybe you can explain this to your rubber duck, by yourself. When does recursion stop, here?

Some programmer dude · Accepted Answer · 2016-05-09 01:06:26Z

1

You have the recursive call minimum(denom,s - 1, N) so N will never be less than or equal to 0, and the recursion will never end.

This would have been very easy to find out if you learned how to use a debugger, and stepped through the code line by line, and stepped into the recursive calls.

answered May 9, 2016 at 1:06

Some programmer dude

411k36 gold badges420 silver badges655 bronze badges

Comments

AmanRaj · Accepted Answer · 2016-05-09 01:11:56Z

1

Another thing that I want to point out is that you are trying to return the sum of two values:

(minimum(denom,s - 1, N) + minimum(denom, s,N-denom[s-1])

instead what you should do is:

min(minimum(denom,s - 1, N), 1 + minimum(denom, s,N-denom[s-1]))

The idea is that in first call you've not used any coin but in second call you have used one, so adding 1 for the same.

Look for a Dynamic Programming solution for the same. https://people.cs.clemson.edu/~bcdean/dp_practice/

answered May 9, 2016 at 1:11

AmanRaj

3292 silver badges6 bronze badges

Collectives™ on Stack Overflow

Recursive coin change c++

3 Answers 3

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related