The Beer Money Problem - Improvements with Recursion (#2)

This is Part 2 of the beer money problem, see intro and Simple Nested Loops Solution (#1).

Recursion - yay. Having a VI that calls itself that calls itself that calls itself... then finally breaks out. 

This solution is just like the nested loops solution, but each loop is a VI with 'Shared clone reentrant execution'. You need to keep track of the 'depth', so you know to do the comparison when you are on the smallest denomination VI. Other than that, no real difference.

My code is available here - open up the project and look at 'Recursion Solution.vi' You'll see that the VI has an awful lot of inputs. 


The many inputs of Recurse.vi

A quick note on comparisons: I actually got the wrong number of answers in my initial attempt, for a really dumb reason. Do you notice how I've converted the amounts such as £10.00 into 1000p? That's not just me being weird: if you're multiplying together an array with one that contains doubles, you can end up with tiny precision/rounding errors which will trip you up when comparing to your goal amount. Is 11.990001 == 11.99? Nope. So it's much safer (and faster?) to use integers.

If I was to spend more time on this, I would put in some options not to store the combinations or results and see how fast I could get it. But there are plenty of pies to be baked and runs to be ran - life is too short.  

Let me know if you come up with more performance enhancements for this solution, I've only really scratched the surface here! Turning off debugging, I find I can get it to find the answers in 0.3-0.4 seconds, keeping all arrays in memory too.

Next up in Part 3, I talk about another couple of approaches that I tried.

Comments