Homework III

Due Tuesday, May 3

In this problem, you will write a recursive function that makes change. Your function wll be in assembly language, and your test program will be in C, so you'll have C calling assembly language. (I will say C throughout these specs, but you are welcome to use C++ if you prefer.) Here are the details:

• The signature of the function--from the point of view of your calling it from C, but the function itself is in assembly language--will be

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

  where

  • Here, we will assemble the proper coins to add to the total amt.
  • The available coins are given in the array onhand, and their denominations are in the array denoms. For example, if these arrays were (3,6,1,8) and (25,10,5,1), it would mean that we have 3 quarters, 6 dimes and so on. (Of course, the code will be general, not just for American money.)
  • Each of the above two arrays is of length ndenoms. But note that they may be subarrays of larger arrays, e.g. you might be calling the function on only dimes, nickels and pennies, excluding quarters from the analysis.
  • The result is returned in the array thechange, again of length ndenoms. In for instance the example above (3 quarters, etc.), amt is 86, then thechange would be (3,1,0,1). If it turns out that change cannot be made, then the function will place a -1 at the beginning of thechange.

• It is the caller's responsibility to set up space for the arrays. When initially calling from C, you can do this with malloc() or whatever, but note that in your recursive calls I will require that any storage you make in memory (you might need none) be done on the stack, not in the .data section or by calling malloc().
• Your test program will be in C. Be sure to test several cases.
• Your function must be recursive, and the recursion will be motivated by the following scenario. Say amt is 80. You code notices that there are 3 quarters available, and thus starts out tentatively by using 3 quarters, leaving 5 cents left to cover. But your code then discovers that you have no nickels or pennies. So, your code then tries, tentatively again, using only 2 quarters. It then finds it has 3 dimes, and so the process is complete.