|
996
|
1 The problem is to determine how many different ways there are to make
|
|
|
2 change for a given amount using five denominations of US coins
|
|
|
3 (including the 50-cent piece). One version -- taken directly from
|
|
|
4 section 1.2.2 of Abelson and Sussman (1st edition, 1985) -- recurses
|
|
|
5 both towards lower amounts and fewer kinds of coins. The space
|
|
|
6 required by this tree recursion grows rapidly with the size of the
|
|
|
7 problem. The other version is a minor modification which makes the
|
|
|
8 long ``amount'' direction tail-recursive. The ``kinds'' direction is
|
|
|
9 still recursive, but with only five kinds of coins there need be only
|
|
|
10 five stack frames for the routine allocated at a time.
|
|
|
11
|
|
|
12 In case it isn't obvious, the routine starting at (100) is the
|
|
|
13 function ``first-denomination'' (one of the few things INTERCAL can do
|
|
|
14 easily), the one at (200) is the recursive version ``cc'', and (300)
|
|
|
15 starts the tail-recursive routine ``cc-tail''. The first few lines are
|
|
|
16 the main program, which you can change to run the recursive version by
|
|
|
17 calling (200) instead of (300). The (2000) routine at the end
|
|
|
18 decrements .1, and I make calls to the addition and subtraction
|
|
|
19 routines in the standard library.
|
|
|
20
|
|
|
21 Two stacks are involved: the variable stack accessed by STASH and
|
|
|
22 RETRIEVE, and the call stack accessed by NEXT and RESUME. The former
|
|
|
23 is limited only by memory, but the latter is supposed to have a
|
|
|
24 built-in limit of 80 pending returns. The tail-recursive routine has
|
|
|
25 no problem with this. However, in order to permit the recursive
|
|
|
26 routine (200) to run with amounts greater than 70, I had to remake the
|
|
|
27 INTERCAL compiler with a larger limit.
|
|
|
28
|
|
|
29
|
|
|
30 (To see this program compared with similar programs in other languages,
|
|
|
31 visit http://www.webcom.com/nazgul/change.html.) |
