Scheme For Enlightenment Part Sixteen - Time For Debugging

In Guile, i ran my new example with traces set on addition (+) and on the function, cc. (LispMe supports traces. But Guile's output can be trivially pasted into a text editor for these posts.) For a simple example, i asked for the coins needed for 2 cents.

(trace cc)
(trace +)
(cc 2 coins)

[cc 2 (50 25 10 5 1)]
[cc 2 (25 10 5 1)]
[cc 2 (10 5 1)]
[cc 2 (5 1)]
[cc 2 (1)]
|  [cc 1 (1)]
|  |  [cc 0 (1)]
|  |  [cc 0 ()]
|  |  0
|  [+ 1 0]
|  1
[+ 1 1]
2
2

This says that cc was called with 2 cents, and the list of coins. There were no 50's, so it called itself again without that in the list. And so on until just pennies were represented. It then called itself with one penny subtracted. Then called itself with both pennies subtracted. When nothing is left in the coin list, it returns zero. That caller adds one to that zero and returns it (one). That caller's caller adds one to this one, getting two. Two is returned. Finally, 2 coins is the answer.

Unlike the original script, this one only calls itself once. So, the time is more or less linear with the amount of money one starts with. It will never take much time, even on the Palm, even for largish input. The original script has two calls and exhibits some sort of exponential behavior. Two calls means that it has to branch left and right down some tree at each call level. One call becomes two, which becomes four, which becomes eight, and so on. At twenty calls deep, it's a million branches. Two self referencing calls. That's something to look for.

The trace also shows that the caller has something to do after it calls itself. That means that no tail recursion optimization is available to the language execution system. So, one might expect a stack overflow if one feeds it ten dollars (1000 cents). However, if one adds 100, 500 and 1000 (a dollar, a five dollar, and ten dollar bill) to the list, it turns out that 1000 cents isn't a big deal. The recursion depth has to do with the number of units counted in the answer. As long as that is small, there is no danger. Yet, it might still be worthwhile to write either a tail recursive version, or a straight looping version.

I've no idea how i might write a looping version. It's really handy to do the recursive call with a subset of the coins list. Scheme makes a copy of the list, so the original remains undamaged. I'm sure it can be done, the question is how ugly will it get? This is the kind of enlightenment i'm looking for, by the way.

If we do a trace on the original, we get a longer trace. At first, it subtracts the coins (dollars) until it gets below the amount (2). You can see that cc returns 1 for the first time. That's when it tried the $2 bill. Then it tries a $1 bill, and it needs a second bill to add up to $2. It returns one for the 2 singles, and returns this a bit until it gets to add one for the single $2 bill. It adds zero for other failures, and finally ends up with 2. Traces for larger numbers are much, much longer. But following them shows where it calls itself for the left and right recursive calls. Further, you get a feeling for how the function takes time proportional to maybe n^2, rather than the fully linear function i wrote. More on this idea later.

(trace cc)
(trace +)
(cc 2 coins)

[cc 2 (50 20 10 5 2 1)]
|  [cc -48 (50 20 10 5 2 1)]
|  0
|  [cc 2 (20 10 5 2 1)]
|  |  [cc -18 (20 10 5 2 1)]
|  |  0
|  |  [cc 2 (10 5 2 1)]
|  |  |  [cc -8 (10 5 2 1)]
|  |  |  0
|  |  |  [cc 2 (5 2 1)]
|  |  |  |  [cc -3 (5 2 1)]
|  |  |  |  0
|  |  |  |  [cc 2 (2 1)]
|  |  |  |  |  [cc 0 (2 1)]
|  |  |  |  |  1
|  |  |  |  |  [cc 2 (1)]
|  |  |  |  |  |  [cc 1 (1)]
|  |  |  |  |  |  |  [cc 0 (1)]
|  |  |  |  |  |  |  1
|  |  |  |  |  |  |  [cc 1 ()]
|  |  |  |  |  |  |  0
|  |  |  |  |  |  [+ 1 0]
|  |  |  |  |  |  1
|  |  |  |  |  |  [cc 2 ()]
|  |  |  |  |  |  0
|  |  |  |  |  [+ 1 0]
|  |  |  |  |  1
|  |  |  |  [+ 1 1]
|  |  |  |  2
|  |  |  [+ 0 2]
|  |  |  2
|  |  [+ 0 2]
|  |  2
|  [+ 0 2]
|  2
[+ 0 2]
2
2