The same answer, two ways

The twelve charges for round down add up to 4. In order they are 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0 and 1: eight rows cost nothing, four cost one, and the total is the numerator of the score 4/12 from the previous section. Two programs compute that total, and you would write either of them without hesitating.

The first program states what the total is. The total from a row onward equals the charge for that row plus the total from the next row onward, and the total past the final row equals nothing. The second program states how to obtain the total: carry a running sum and a counter, add one charge at each step, and stop when the counter passes the final row. Both return 4, both add the same twelve numbers, and as answers to the question you asked they are indistinguishable. !Two processes total the first four stopwatch readings, 20, 40, 55 and 62. Left: the delegating run builds 20 + (40 + (55 + (62 + 0))) and contracts backwards; the partial sums run 62, 117, 157 and 177, and at the innermost addition three further additions wait outside any variable. Right: the looping run carries the pair (counter, running total) through (1, 0), (2, 20), (3, 60), (4, 115) and (5, 177). Both return 177, and only the right-hand state fits on a card that can resume the run. Status: re-simulated.

One of them can be interrupted halfway, summarised by two numbers written on a card, and resumed tomorrow from that card alone. The other cannot, because stopping it leaves work in the air that no variable of the program holds. The state of a process is the information that decides what happens next, namely the values the next step reads. The looping form is cheap to repeat when that state fits in a fixed handful of values and the implementation reuses the space of a finished call; fixed state is necessary for the saving and not sufficient. That condition is the subject of this section, and naming it takes two definitions. !The delegation tree for three disks. The largest disk moves once, and the two stacks above it each solve the same problem with two disks, so T(3) = 2T(2) + 1 and the tree carries seven moves: one disk 3, two disk 2 and four disk 1. Each hand-over passes a smaller instance to a delegate, and the measure n falls by one until the vacuous base case T(0) = 0. Status: schematic.

Worked example. Total the first four stopwatch readings, which are 20, 40, 55 and 62, in both ways.

The delegating program expands before it contracts. Substitution gives 20 + (40 + (55 + (62 + 0))), and the additions then run backwards: 62, then 117, then 157, then 177. Four additions are performed, one per row. At the moment the innermost addition happens, three further additions are waiting, and none of those three sits in a variable of the program.

The looping program never expands. Its states are pairs holding the counter and the running sum: (1, 0), then (2, 20), then (3, 60), then (4, 115), then (5, 177). It performs the same four additions on the same numbers in the opposite order, and nothing is ever pending. To resume it from a pause you need two numbers and the table.

Both runs return 177, and their partial sums differ at every step except the last. In the delegating run the additions waited in a chain three deep, and no variable of the program held that chain. A process that builds such a chain is a recursive process [S:13:72].

In the looping run two variables held everything, and a fixed rule updated them. A process whose state is a fixed number of variables, with a fixed update rule and an optional end test, is an iterative process [S:13:72].

The information holding the chain of a recursive process is not contained in the program's variables, and the interpreter, the program that carries out the text, maintains it instead [S:13:73]. In the iterative case the program variables provide a complete description of the state at any point [S:13:73].

Both programs above can be written as procedures that name themselves, and that fact is about the text rather than about the run. A recursive procedure is one whose definition refers, directly or indirectly, to itself [S:13:73]. A procedure may refer to itself and still generate an iterative process. A procedure that does not refer to itself defers work only by calling another procedure that builds the chain, and the chain belongs to that other procedure.

The delegating move generalises far beyond arithmetic. Reducing one problem to another means writing an algorithm for the first problem that uses an algorithm for the second as a black box. An algorithm here is a recipe stated precisely enough that somebody else can carry it out without asking a question. The correctness of the first cannot depend in any way on how the second works [S:1:39]. When the second problem is a smaller instance of the first, the black box deserves a name: the delegate receives a smaller instance together with the same promise, and you do not watch what it does.

One condition makes delegation stop, and the source states it plainly: there must be no infinite sequence of reductions to simpler and simpler instances [S:1:41]. A measure turns that condition into something you can check. Attach a whole number to each instance, require it to decrease strictly at every hand-over, and require it never to fall below zero; such a number can decrease only so many times.

The tower of Hanoi makes the move visible, because nobody can see the whole solution at once. Three pegs hold n disks of distinct sizes, and the task is to move the stack without ever placing a disk on a smaller one. The largest disk cannot move while anything rests on it, so the stack above it must go elsewhere and come back.

Write T(n) for the number of moves the task needs with n disks. The largest disk needs one move, and the stack above it must travel to the spare peg and later onward, which gives two smaller instances of the same task. So T(0) = 0 and T(n) = 2T(n-1) + 1 for every n at least one [S:1:44].

The first values are 0, 1, 3, 7, 15 and 31. The base case is the smallest instance, the one the rule answers without calling itself, and here it is vacuous. The source says why with some affection: moving zero disks takes no time at all, by doing nothing [S:1:43].

The distinction describes processes, not implementations, and it costs memory either way. Most implementations of common languages consume an amount of memory that grows with the number of procedure calls, even when the process described is iterative [S:13:74]. An iterative process written as a procedure that calls itself can therefore exhaust memory, and the shape on the page is not the shape at runtime.

There is also a debt: the delegation argument states what follows if the delegate keeps its promise. The principle that licenses the step to every instance is induction, the rule that a claim proved for the smallest case and for each case from the one below it holds for every case. Chapter 3 supplies it.

The formal statement. A process is iterative when its state at any point is a fixed tuple of values together with a fixed update rule and an optional end test [S:13:72]. The process is recursive when it builds a chain of deferred operations, and the length of that chain grows with the input [S:13:72]. A procedure is recursive when its definition refers to itself, directly or indirectly [S:13:73]. The two classifications are independent in one direction: a recursive procedure may generate an iterative process. A procedure that does not refer to itself defers work only through another procedure that builds the chain, and the chain belongs to that other procedure. Only the first classification is about memory.

For a process to be resumable from its own variables, the map from step number to state must be recoverable from a bounded set of values. The looping process satisfies this at every step. The delegating process does not, because at depth i the interpreter holds a chain of i pending additions, and no variable of the program names that chain [S:13:73].

The derivation. The two summations add the same twelve charges and both obtain four. The delegating run contracts backwards, so the partial sums on the four-row example are 62, 117, 157 and 177; the looping run accumulates forwards, and its partial sums are 20, 60, 115 and 177. The totals agree because addition does not care about order, not because the runs coincide. SICP makes the same claim for factorial: the two processes compute the same product, and the difference lies in what each must hold while it runs [S:13:72]. Sameness of the result is therefore not the distinction, and no test on outputs can find it.

The Hanoi recurrence gives the price of the deferred chain. Write T(n) for the moves needed. The largest disk needs one move, and the stack above it must travel to the spare peg and later onward, which gives two smaller instances of the same task [S:1:44]. The base case is T(0) = 0. Then T(n) = 2T(n-1) + 1 for n at least one, and induction gives T(n) = 2^n - 1: the claim holds at zero, and substituting 2^(n-1) - 1 into the recurrence gives 2(2^(n-1) - 1) + 1, which is 2^n - 1. I omit the formal dress of the induction, which Chapter 3 supplies.

An edge case. SICP writes an iterative process as a procedure that calls itself, and warns that most implementations of common languages consume memory that grows with the number of calls even when the process is iterative [S:13:74]. So the fixed-state condition is necessary for cheap repetition and not sufficient for it. A language that reserves a frame per call reproduces the memory cost of the recursive process while running the iterative one, and only a tail-recursive implementation avoids it [S:13:74].

Any recursive process can be turned into an iterative one by making the pending chain an explicit stack. The state is then a fixed pair of variables, one of which points at a structure whose size grows with n. L1's criterion counts the stack as state.

What L1 hid, and why that was safe there. L1 said that the looping form is cheap to repeat when its state is fixed. The refinement is that this is a statement about processes, and that the saving is collected only when the implementation cooperates. The twelve-row example fits in memory either way, so the simplification cost the reader nothing at the point where it was made.

Where the analogy breaks. The delegation story says that somebody else solves the smaller instance and you do not watch. That somebody is the induction hypothesis, a proof device [S:1:41], and no work leaves your machine. The pending chain sits in your memory, and the analogy hides the bill.

Where the idea comes from. The distinction between a recursive and an iterative process is drawn in Structure and Interpretation of Computer Programs, section 1.2.1, with factorial as the worked case and the substitution model as the instrument [S:13:72]. The same section separates the process from the procedure, which is the move that makes the distinction precise [S:13:73]. SICP also records the implementation half: most implementations of common languages consume memory that grows with the number of procedure calls, even for an iterative process, and an implementation that does not is called tail-recursive [S:13:74].

The termination condition has a second lineage. Erickson states the technical condition for any recursive method: there must be no infinite sequence of reductions to simpler and simpler instances [S:1:41]. He gives the device that checks it, a smaller instance at every hand-over, and the Hanoi puzzle as the case where the device is visible [S:1:44]. The puzzle itself was published as a physical object by Édouard Lucas in 1883 [S:1:42].

What the field has not settled. Whether iteration is guaranteed cheap is a property of implementations, not of processes, and language standards differ. SICP can say of its Scheme that an iterative process runs in constant space and note that the standard requires it [S:13:74]; a reader of another language cannot assume the same. The open question is which widely used languages promise constant-space iteration, and under which conditions. The evidence that would settle it for one language is a pair of documents: the clause of the standard that requires it, and a measurement of peak memory against input size for an iterative process written as a self-calling procedure.

What depends on it. Termination proofs by decreasing measures rest on the same idea. Mathematics for Computer Science assigns a nonnegative integer to each state and shows that it decreases at every transition, which bounds the length of any execution [S:5:150]. Every termination checker and every recurrence analysis in Chapter 5 is a version of that assignment, and the Hanoi recurrence is the smallest instance in this book.

What to read next. Read SICP section 1.2.1 for the process and procedure distinction and for the tail-recursion remark [S:13:72]. Read sections 1.1 to 1.3 of Erickson for reduction, the termination condition and Hanoi [S:1:41]. Read the state-machine section of Mathematics for Computer Science for the measure argument that turns "it stops" into a theorem [S:5:150]. Then work the tree-recursion exercise that follows, where one procedure makes two calls to itself and the chain of deferred work branches [S:13:75].