Mercurial > repo
view interps/c-intercal/pit/change.doc @ 8381:056b8b7ad856
<Moon__> rm bin/`i
author | HackBot |
---|---|
date | Mon, 06 Jun 2016 05:28:24 +0000 |
parents | 859f9b4339e6 |
children |
line wrap: on
line source
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.)