Ex. 1.9

These two procedures are pretty simple to understand. They perform addition when only the increment or decrement operation is available. This particular approach is of mild historical interest, since that was sometimes how it was done with some primitive circuits, and possibly even some early processors.

To ensure that the substitution steps are being performed correctly, each one is written out as an executable line. When substitution is being used, every line should always evaluate to the final answer. Otherwise something wasn’t substituted correctly. That’s not a guarantee the work is being done right, but it’s a simple and good check.

The second one given illustrates tail recursion, as mentioned in the text. The process is iterative, but it can all fit into one procedure that calls itself. The reason for the name is that the recursive call is the last thing done at that step. Since the procedure will do nothing but return that value once the recursive call is done, it makes sense to make the call without preserving our place. This is what avoids the space penalty.

Ex. 1.10

Ackermann’s function is a well-known way in which truly enormous numbers can be formed from a very short and simple expression. It’s not hard to follow the steps. The simple test of plugging in a few values helps to verify that the mathematical expression is correct. There is some difficulty in that it is not long before the numbers get too massive to display or make any sense of. If you try it, you might find you run out of memory and time before you can get past single digits for function h.

Solutions 1.2.1