recursion method keeps crashing (change algorithm)

//amt = amount of cents to get change for
//onhand = array of available coins . Ex: {3, 0, 1, 0} = 3 quart, 0 dime, 1 nickel, 0 pennies

//denoms = {25, 10, 5, 1}

//ndenoms = 4 ; i.e the number of different denominations

// thechange = array of change. Ex: if amt = 80, then one possible thechange = {3, 0, 1, 0} b/c 3*25 + 1*5 = 80 cents



int i = 0;

void makechange(int amt, int *onhand, int *denoms, int ndenoms, int *thechange)
   {            

      if ( (denoms[i] * onhand[i]) > amt)
         {
                    onhand[i]--;    // # of coins is too much, decrement and try again
                    makechange(amt, onhand, denoms, ndenoms, thechange); // try agan
         }

      thechange[i] = onhand[i]; //found #of coins

      amt = amt - denoms[i]*onhand[i]; // get remaining amount from change
      i++;

      if (amt != 0) // we're not done with change so move on to next denomination
      {
           makechang开发者_如何学运维e(amt, onhand, denoms, ndenoms, thechange);
      }   


      else if (amt == 0) // we're done with the change so all the other # coins = 0
      {
           for (int j = i; j < amt; j++)
             {
              thechange[j] = 0;
             }
      }




   }   






Now, down in main when I actually call the function prototype and print out the result

//


makechange(amt, onhand, denoms, ndenoms, thechange);

  for (int k = 0; k < ndenoms; k++)
  {
      cout << thechange[i] << " ";
  }


//

I get an error.

This algorithm seems seems sensible to me, does anyone know why it keeps crashing, though?

Have I properly used recursion here?

If you call makechange twice, the second time it won't work because the global variable i will be wrong.

Also what should happen if you try to makechange and don't have enough change on hand to make it?

Similarly what happens if you have 3 quarters and 3 dimes, and are asked to make 80 cents in change? Your algorithm will use all 3 quarters and then get stuck.

did you mean

for (int k = 0; k < ndenoms; k++) { cout << thechange[k] << " "; }

a little typo made possible by the use of global variable i.

also

      for (int j = i; j < amt; j++) { thechange[j] = 0; }

I think you meant

for (int j = i; j < ndenoms; j++)

depending on the final value of amt, this will cause you to run off the end of the array, resulting in a crash.

you can solve this more easily without recursion. are you required to use recursion for an assignment? if not, try this:

int makechange(int amt, int *onhand, int *denoms, int ndenoms, int *thechange)
{

    for (int i=0; i < ndenoms && amt > 0; i++)
    {
        while (onhand[i] > 0 && denoms[i] <= amt)
        {
            onhand[i]--; // use one coin
            thechange[i]++;
            amt -= denoms[i];
        }
    }
    return amt; // this is the amount you owe if you dont have enough on hand
} 

I made the changes as mentioned by shsmith and here is the modified and complete c++ program.

#include <iostream> 

using namespace std;

int i = 0;

void makechange(int amt, int *onhand, int *denoms, int ndenoms, int *thechange)
{
    if ( (denoms[i] * onhand[i]) > amt)
    {
            onhand[i]--;    // # of coins is too much, decrement and try again
            makechange(amt, onhand, denoms, ndenoms, thechange); // try agan
    }

    thechange[i] = onhand[i]; //found #of coins
    amt = amt - denoms[i]*onhand[i]; // get remaining amount from change
    i++;
    if (amt != 0) // we're not done with change so move on to next denomination
    {
            makechange(amt, onhand, denoms, ndenoms, thechange);
    }
    else if (amt == 0) // we're done with the change so all the other # coins = 0
    {
            for (int j = i; j < ndenoms; j++)
            {
                    thechange[j] = 0;
            }
    }}

int main(){

    //Now, down in main when I actually call the function prototype and print out the result
    int amt = 80, onhand[] = {3, 0, 1, 0}, denoms[] = {25, 10, 5, 1}, ndenoms = 4, thechange[4];
    makechange(amt, onhand, denoms, ndenoms, thechange);
    for (int k = 0; k < ndenoms; k++)
    {
            cout << thechange[k] << " ";
    }
    cout << "\n";
    return 0;}

This code is running perfectly on my machine. I compiled it using Cygwin.

Note: This algorithm would work only if you have the denomination coins more or correctly onhand. If there are insufficient number of coins onhand, then there is no exit for the recursive method because 'amt' would never become zero. At the same time, you never check for the 'i' value whether it is in bounds of the 'ndenoms'. This could also result in out of boundary errors which could cause ur program to exit incorrectly.