Adding a counter?-CodePudding

I currently have a problem that I am working on that entails a recursive coin counter that does not include global variables or loops. I have gotten most of it down, however it seems that I need to add a single coin that is being counted, plus the result from the coins(sum-10), and I am failing to understand how to do that, as I have attempted to put a counter in for returning it.. Any help would be appreciated.

#include <iostream>
#include <vector>
using namespace std;

int coins(int sum)
{
    int count = 0;
    if (sum < 0)
        return 0;
    
    if (sum == 0)
        return 0;
    
    if (sum >= 25)
    {
        return sum   coins(sum - 25);
        return count  ;
    }
    else if (sum >= 10)
    {
        return sum   coins(sum - 10);
        return count  ;
    }
    else if (sum >= 5)
    {
        return sum   coins(sum - 5);
        return count  ;
    }
    else if (sum >= 1)
    {
        return sum   coins(sum - 1);
        return count  ;
    }
}

void main()
{
    int cents, n;
    
    // Get user input
    
    cout << "Enter an amount in cents: ";
    cin >> cents;
    
    // Call recursive function
    
    n = coins(cents);
    cout << endl;
    
    // Output results
    
    cout << n << " coins" << endl;
}

Here is an example of expected output

Enter an amount in cents: 16
10 5 1
3 coins

and here is what I am currently getting

Enter an amount in cents: 37

0 coins

CodePudding user response：

You are confusing the value you want to divide into coins and the amount of coins. This:

 return sum   coins(sum - 25);

Does not make sense. You are adding unrelated quantities. sum is the amount of money while coins returns the number of coins. You need no additional counter, the return value accumualated during the recursion is the counter:

int coins(int sum)
{
    if (sum < 0)
        return 0;
    
    if (sum == 0)
        return 0;
    
    if (sum >= 25)
    {
        return 1   coins(sum - 25);
    }
    else if (sum >= 10)
    {
        return 1   coins(sum - 10);
    }
    else if (sum >= 5)
    {
        return 1   coins(sum - 5);
    }
    else //(sum >= 1)
    {
        return 1   coins(sum - 1);
    }
}

Each time you decrement the sum one coin is added.

This:

return sum   coins(sum - 25);
return count  ;

Cannot be correct. Code after the first return is never executed. Also note that main must return int.

CodePudding user response：

As is often the case, recursion here makes the code more complicated. Unless you're required to write this recursively, it should be done with a small series of loops:

int coins(int sum) {
    int count = 0;
    while (sum >= 25) {
          count;
        sum -= 25;
    }
    while (sum >= 10) {
          count;
        sum -= 10;
    }
    while (sum >= 5) {
          count;
        sum -= 5;
    }
    while (sum >= 1) {
          count;
        sum -= 1;
    }
    return count;
}

Or, even better:

int coins(int sum) {
    int count = 0;
    count  = sum % 25;
    sum /= 25;
    count  = sum % 10;
    sum /= 10;
    count  = sum % 5;
    sum /= 5;
    count  = sum;
    return count;
}

CodePudding user response：

It sounds like you're trying to count the number of coins it takes to make up the sum provided, and to do it recursively.

Every time you use recursion you need a base case which does not recursively call the function. In this case it's if your sum is zero or less.

int coins(int sum) {
    if (sum <= 0) {
        return 0;
    }
}

Now, we just need to handle the other cases, where we'll use the recursive call to update the data so we converge on the base case. I'm going to write code for quarters and let you fill in the rest of the logic.

int coins(int sum) {
    if (sum <= 0) {
        return 0;
    }
    else if (sum >= 25) {
        return 1   coins(sum - 25);
    }
    else if (sum >= 10) {
        ...
    }
    else if (sum >= 5) {
        ...
    }
    else {
        ...
    }
}

One more thing

If we step through this for an initial value of 97, let's look at what happens.

coins(97)
1   coins(72)
1   1   coins(47)
1   1   1   coins(22)
1   1   1   1   coins(12)
1   1   1   1   1   coins(2)
1   1   1   1   1   1   coins(1)
1   1   1   1   1   1   1   coins(0)
1   1   1   1   1   1   1   0
7

We can use integer division to reduce the number of recursive calls.

int coins(int sum) {
    if (sum <= 0) {
        return 0;
    }
    else if (sum >= 25) {
        int quarters = sum / 25;
        return quarters   coins(sum - 25 * quarters);
    }
    else if (sum >= 10) {
        ...
    }
    else if (sum >= 5) {
        ...
    }
    else {
        ...
    }
}

Now, if we start with 97 we get:

coins(97)
3   coins(22)
3   2   coins(2)
3   2   2   0
7

Use a much larger number, and this has a significant impact on your stack usage. And integer division doesn't seem to be prohibited by your requirements.

Just for fun

For fun let's rewrite this using the ternary operator:

int coins(int sum) {
    return sum <= 0 ? 0 :
           sum >= 25 ? sum / 25   coins(sum - sum / 25 * 25) :
           sum >= 10 ? sum / 10   coins(sum - sum / 10 * 10) :
           sum >=  5 ? sum /  5   coins(sum - sum /  5 *  5) :
                       sum;
}