Recursively shrinking an array and passing it on as a new parameter

Question

Is it possible to keep eliminating elements of an array (i.e. shrinking it as you deal with the first, second, etc...) and passing it as a new parameter to the same function (i.e. recursively)?

I am trying to come up with a simple method of calculating the number of each coin required for a customer's change (e.g. in a vending machine) but since I am confused by all the Google search results that use nested loops, etc... (I mean I find them difficult to understand) I decided to see if I could translate my thinking into a simple recursive call for solving this problem.

What I have so far is as follows. Let's say the machine should return 80 cents in change, given a denomination list of 10, 20, 50, 100 and 200 coins. A human would think: The first coin that is "less" than 80 is 50 cents, so I need one 50 cents, and now the remaining is 30 cents.

The first coin that is less than 30 is 20 cents, so I need one 20 cents, and now the remaining is only 10 cents. The first coin that is less than (or in this case equal to) the remaining is 10 cents which completes the process.

So, at each step, after taking care of the biggest coin denomination that helps me, I am "disregarding" the other big coins that were too much; i.e. I am removing the useless coin denominations that are of no help to me.

Now, having coded my simplistic way of thinking, I have come up with the following, and now I am wondering how I can map this "coin denomination array shrinking" to code? This is highlighted where I have put my temp array...

What I mean is that when I started off, I checked the 2 euro coin (200) which was coins[1] and it was too big. So was coins[2] which was 1 euro. And then the 50 cent coin helped (coins[3]) so that is sorted, but now I would like to run the same method Calculate on the coins[4] and coins[5] which could be thought of as a new axed array that now contains only index 4 and 5 which could continue to solve the problem.

Is this even possible?

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;


namespace CoinsConsole
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] coins = new int[5] { 200, 100, 50, 20, 10 };

            Calculate(coins, 80); // 50 + 20 + 10

            Console.ReadLine();
        }


        static []int Calculate(int[] coins, int change)
        {
            int[] counts = new int[5] { 0, 0, 0, 0, 0 };
            int remaining;

            for (int i = 1; i <= coins.Length; i++)
            {
                if (coins[i] <= change)
                {
                    remaining = change - coins[i];
                    ++counts[i];
                    []int temp = coins.Skip(i);
                    Calculate(temp, remaining);
                }
            }

            return counts;
        }
    }
}

EDIT 1: This is not just a duplicate of array.Skip(n).Take(n). I am trying to understand how to pass the modified array for recursion; e.g. whether I should use array.Copy or the same axed array, etc...

EDIT 2: I have incorporated the way I think I should pass on the new shortened array, but coins.Skip(i) and Calculate(temp, remaining) are all underlined red. What am I doing wrong?

Answer 1

The way this is usually done is not by extracting a sub-array for each recursive invocation. Instead, it is done by always passing the exact same array, along with the starting index and the number of elements to consider.

This way, you do not have to engage in the messy business of extracting a sub-array, and your code will perform much, much better.

If you don't want to change the public interface of the method, then have it invoke an internal (private) method which does all the job, (including the recursion,) passing it 0 for start index and array.length for length.

If you insist on extracting a sub-array, you must allocate it yourself and then use Array.Copy to copy a range of elements from the old array to the new one. See https://msdn.microsoft.com/en-us/library/system.array.copy(v=vs.110).aspx

Answer 2

This doesn't answer your question, but it might open your eyes on other possible and simpler approaches.

Why don't you have a classified container of stacks of coins? Consider the following structure: Dictionary<int, Stack<Coin>>. This container will have stacks of coins classified by value (in cents).

coins[10] will give you a stack of all 10 cent coins available in the machine. coins[25] will give you quarters, etc.

And when a customer adds a coin, you just place in its appropriate stack: coins[enteredCoin.Value].Push(enteredCoin).

This also makes it easy to configure your vending machine for different currency. On start up register in the dictionary the coins (keys) you'll be accepting and precharge the vending machine (newing up stacks and pushing coins).

Checking if any entered coin is acceptable is also easy, simply check if the value is a valid key of the dictionary, if it isn't, return it to the customer.

Things become much easier with this approach.

Answer 3

Im posting the answer to your problem since im afraid the other answers might be a bit too complicated for you to follow or give you a wrong idea.

static void CalculateChange(int change, int[] coins)
{
    Console.Write(change + " = ");

    int j = 0;
    while (change > 0)
    {
        for (int i = j; i < coins.Length; i++)
        {
            int coin = coins[i];
            if (coin <= change)
            {
                change = change - coin;
                j = i; // remmeber the position of the biggest possible coin, to start from next loop
                Console.Write(coin + " ");
                break;
            }
        }
    }
}

As you can see, you were quite close.

The variable jhere is to optimize the inner for-loop. It simply rembers the position of the last used coin so it doesnt need to check all the coins that were allready to big again.

The program still works wthout the j. I put it there to fit your idea of reducing the remaining coins.

Two things to note: First,this answer assumes that int[] coins is sorted descending. Second, this is an iteraitve approach, I am sure you will work out the recursive one.