recursion method keeps crashing (change algorithm)

Question

//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
      {
           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 < 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?

How does it crash? Do you get an error when it does? And what language is this? — Blender
– Blender, Commented Apr 27, 2011 at 22:43
Whenever, I compile and run i get "change.exe has stopped working" so I assume a seg fault or something? — Ted Stevens
– Ted Stevens, Commented Apr 27, 2011 at 22:47
Tag changed to c++ for consistency with the language and compiler used by the OP — pmg
– pmg, Commented Apr 27, 2011 at 23:09

btilly · Accepted Answer · 2011-04-27 22:52:59Z

1

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.

answered Apr 27, 2011 at 22:52

btilly

47.8k3 gold badges69 silver badges101 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

btilly Over a year ago

@ted-stevens: Your algorithm assumes that i starts off at 0. If you've called makechange already, it is no longer 0, and you'll never look at your first denomination.

hsmiths · Accepted Answer · 2011-04-28 03:08:58Z

0

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
}

edited Apr 28, 2011 at 3:08

answered Apr 27, 2011 at 22:47

hsmiths

1,32714 silver badges17 bronze badges

7 Comments

Ted Stevens Over a year ago

^ thanks, but even after that it still crashes. Can anyone copy and paste my code and try it please?

hsmiths Over a year ago

Try adding print statements at entry and exit of makechange. You might realize what is wrong when you can see the context of the crash.

hsmiths Over a year ago

also you are not checking for i>= ndenoms as an exit condition. You can get subscript out of range after the last i++ if you are not careful.

Ted Stevens Over a year ago

^ How come the algorithm loops forever?

Ted Stevens Over a year ago

I don't need an exit statement, do I? The function will not call itself anymore once (amt == 0) and complete the rest of main. So isn't this enough?

|

Purnima · Accepted Answer · 2011-04-28 07:00:09Z

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.

Collectives™ on Stack Overflow

recursion method keeps crashing (change algorithm)

3 Answers 3

1 Comment

7 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

7 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related