The problem is to determine how many different ways there are to make
change for a given amount using five denominations of US coins
(including the 50-cent piece). One version -- taken directly from
section 1.2.2 of Abelson and Sussman (1st edition, 1985) -- recurses
both towards lower amounts and fewer kinds of coins.  The space
required by this tree recursion grows rapidly with the size of the
problem. The other version is a minor modification which makes the
long ``amount'' direction tail-recursive. The ``kinds'' direction is
still recursive, but with only five kinds of coins there need be only
five stack frames for the routine allocated at a time.

In case it isn't obvious, the routine starting at (100) is the
function ``first-denomination'' (one of the few things INTERCAL can do
easily), the one at (200) is the recursive version ``cc'', and (300)
starts the tail-recursive routine ``cc-tail''. The first few lines are
the main program, which you can change to run the recursive version by
calling (200) instead of (300). The (2000) routine at the end
decrements .1, and I make calls to the addition and subtraction
routines in the standard library.

Two stacks are involved: the variable stack accessed by STASH and
RETRIEVE, and the call stack accessed by NEXT and RESUME. The former
is limited only by memory, but the latter is supposed to have a
built-in limit of 80 pending returns. The tail-recursive routine has
no problem with this. However, in order to permit the recursive
routine (200) to run with amounts greater than 70, I had to remake the
INTERCAL compiler with a larger limit.


(To see this program compared with similar programs in other languages,
visit http://www.webcom.com/nazgul/change.html.)