With the ideas illustrated so far, we can implement any iterative process by specifying a register machine that has a register corresponding to each state variable of the process. The machine repeatedly executes a controller loop, changing the contents of the registers, until some termination condition is satisfied. At each point in the controller sequence, the state of the machine (representing the state of the iterative process) is completely determined by the contents of the registers (the values of the state variables).
Implementing recursive processes, however, requires an additional mechanism. Consider the following recursive method for computing factorials, which we first examined in section 1.2.1:
Original | JavaScript |
(define (factorial n) (if (= n 1) 1 (* (factorial (- n 1)) n))) | function factorial(n) { return n === 1 ? 1 : n * factorial(n - 1); } |
Original | JavaScript |
(define (gcd a b) (if (= b 0) a (gcd b (remainder a b)))) | function gcd(a, b) { return b === 0 ? a : gcd(b, a % b); } |
In the case of factorial (or any recursive process) the answer to the new factorial subproblem is not the answer to the original problem. The value obtained for $(n-1)!$ must be multiplied by $n$ to get the final answer. If we try to imitate the GCD design, and solve the factorial subproblem by decrementing the n register and rerunning the factorial machine, we will no longer have available the old value of n by which to multiply the result. We thus need a second factorial machine to work on the subproblem. This second factorial computation itself has a factorial subproblem, which requires a third factorial machine, and so on. Since each factorial machine contains another factorial machine within it, the total machine contains an infinite nest of similar machines and hence cannot be constructed from a fixed, finite number of parts.
Nevertheless, we can implement the factorial process as a register machine if we can arrange to use the same components for each nested instance of the machine. Specifically, the machine that computes $n!$ should use the same components to work on the subproblem of computing $(n-1)!$, on the subproblem for $(n-2)!$, and so on. This is plausible because, although the factorial process dictates that an unbounded number of copies of the same machine are needed to perform a computation, only one of these copies needs to be active at any given time. When the machine encounters a recursive subproblem, it can suspend work on the main problem, reuse the same physical parts to work on the subproblem, then continue the suspended computation.
In the subproblem, the contents of the registers will be different than they were in the main problem. (In this case the n register is decremented.) In order to be able to continue the suspended computation, the machine must save the contents of any registers that will be needed after the subproblem is solved so that these can be restored to continue the suspended computation. In the case of factorial, we will save the old value of n, to be restored when we are finished computing the factorial of the decremented n register.[1]
Since there is no a priori limit on the depth of nested
recursive calls, we may need to save an arbitrary number of register
values. These values must be restored in the reverse of the order in
which they were saved, since in a nest of recursions the last
subproblem to be entered is the first to be finished. This dictates
the use of a stack, or last in, first out
data
structure, to save register values. We can extend the register-machine
language to include a stack by adding two kinds of instructions: Values are
placed
on the stack using a
save instruction and
restored from the stack using a
restore
instruction. After a sequence of values has been
saved on the stack, a sequence of
restores will retrieve these values in reverse
order.[2]
With the aid of the stack, we can reuse a single copy of the factorial
machine's data paths for each factorial subproblem. There is a
similar design issue in reusing the controller sequence that operates
the data paths. To reexecute the factorial computation, the
controller cannot simply loop back to the beginning, as with
an iterative process, because after solving the
$(n-1)!$ subproblem
the machine must still multiply the result by
$n$. The controller
must suspend its computation of $n!$, solve the
$(n-1)!$ subproblem,
then continue its computation of $n!$. This
view of the factorial computation suggests the use of the subroutine
mechanism described in section 5.1.3, which
has the controller use a
continue register to transfer to the part of
the sequence that solves a subproblem and then continue where it left off on
the main problem. We can thus make a factorial subroutine that returns to
the entry point stored in the continue
register. Around each subroutine call, we save and restore
continue just as we do the
n register, since each level
of
the factorial computation will use the same
continue register. That is, the factorial
subroutine must put a new value in continue
when it calls itself for a subproblem, but it will need the old value in
order to return to the place that called it to solve a subproblem.
Figure 5.14 Figure 5.13 shows the data paths and controller for a machine that implements the recursive factorial procedure. function. The machine has a stack and three registers, called n, val, and continue. To simplify the data-path diagram, we have not named the register-assignment buttons, only the stack-operation buttons (sc and sn to save registers, rc and rn to restore registers). To operate the machine, we put in register n the number whose factorial we wish to compute and start the machine. When the machine reaches fact-donefact_done, the computation is finished and the answer will be found in the val register. In the controller sequence, n and continue are saved before each recursive call and restored upon return from the call. Returning from a call is accomplished by branching to the location stored in continue. Continue The register continue is initialized when the machine starts so that the last return will go to fact-donefact_done. The val register, which holds the result of the factorial computation, is not saved before the recursive call, because the old contents of val is not useful after the subroutine returns. Only the new value, which is the value produced by the subcomputation, is needed.
Although in principle the factorial computation requires an infinite machine, the machine in figure 5.14 figure 5.13 is actually finite except for the stack, which is potentially unbounded. Any particular physical implementation of a stack, however, will be of finite size, and this will limit the depth of recursive calls that can be handled by the machine. This implementation of factorial illustrates the general strategy for realizing recursive algorithms as ordinary register machines augmented by stacks. When a recursive subproblem is encountered, we save on the stack the registers whose current values will be required after the subproblem is solved, solve the recursive subproblem, then restore the saved registers and continue execution on the main problem. The continue register must always be saved. Whether there are other registers that need to be saved depends on the particular machine, since not all recursive computations need the original values of registers that are modified during solution of the subproblem (see exercise 5.4).
Let us examine a more complex recursive process, the tree-recursive computation of the Fibonacci numbers, which we introduced in section 1.2.2:
Original | JavaScript |
(define (fib n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2))))) | function fib(n) { return n === 0 ? 0 : n === 1 ? 1 : fib(n - 1) + fib(n - 2); } |
Original | JavaScript | |
Original | JavaScript |
(controller (assign continue (label fib-done)) fib-loop (test (op <) (reg n) (const 2)) (branch (label immediate-answer)) ;; set up to compute ${\textrm{Fib}}(n-1)$ (save continue) (assign continue (label afterfib-n-1)) (save n) ; save old value of $n$ (assign n (op -) (reg n) (const 1)) ; clobber $n$ to $n-1$ (goto (label fib-loop)) ; perform recursive call afterfib-n-1 ; upon return, val contains ${\textrm{Fib}}(n-1)$ (restore n) (restore continue) ;; set up to compute ${\textrm{Fib}}(n-2)$ (assign n (op -) (reg n) (const 2)) (save continue) (assign continue (label afterfib-n-2)) (save val) ; save ${\textrm{Fib}}(n-1)$ (goto (label fib-loop)) afterfib-n-2 ; upon return, val contains ${\textrm{Fib}}(n-2)$ (assign n (reg val)) ; $n$ now contains ${\textrm{Fib}}(n-2)$ (restore val) ; val now contains ${\textrm{Fib}}(n-1)$ (restore continue) (assign val ; ${\textrm{Fib}}(n-1)+{\textrm{Fib}}(n-2)$ (op +) (reg val) (reg n)) (goto (reg continue)) ; return to caller, answer is in val immediate-answer (assign val (reg n)) ; base case: ${\textrm{Fib}}(n)=n$ (goto (reg continue)) fib-done) | controller( list( assign("continue", label("fib_done")), "fib_loop", test(list(op("<"), reg("n"), constant(2))), branch(label("immediate_answer")), // set up to compute $\textrm{Fib}(n-1)$ save("continue"), assign("continue", label("afterfib_n_1")), save("n"), // save old value of $\texttt{n}$ assign("n", list(op("-"), reg("n"), constant(1))), // clobber $\texttt{n}$ to $n-1$ go_to(label("fib_loop")), // perform recursive call "afterfib_n_1", // upon return, $\texttt{val}$ contains $\textrm{Fib}(n-1)$ restore("n"), restore("continue"), // set up to compute $\textrm{Fib}(n-2)$ assign("n", list(op("-"), reg("n"), constant(2))), save("continue"), assign("continue", label("afterfib_n_2")), save("val"), // save $\textrm{Fib}(n-1)$ go_to(label("fib_loop")), "afterfib_n_2", // upon return, $\texttt{val}$ contains $\textrm{Fib}(n-2)$ assign("n", reg("val")), // $\texttt{n}$ now contains $\textrm{Fib}(n-2)$ restore("val"), // $\texttt{val}$ now contains $\textrm{Fib}(n-1)$ restore("continue"), assign("val", // $\textrm{Fib}(n-1) + \textrm{Fib}(n-2)$ list(op("+"), reg("val"), reg("n"))), go_to(reg("continue")), // return to caller, answer in $\texttt{val}$ "immediate_answer", assign("val", reg("n")), // base case: $\textrm{Fib}(n) = n$ go_to(reg("continue")), "fib_done")) |
Original | JavaScript |
(define (expt b n) (if (= n 0) 1 (* b (expt b (- n 1))))) | function expt(b, n) { return n === 0 ? 1 : b * expt(b, n - 1); } |
Original | JavaScript |
(define (expt b n) (define (expt-iter counter product) (if (= counter 0) product (expt-iter (- counter 1) (* b product)))) (expt-iter n 1)) | function expt(b, n) { function expt_iter(counter, product) { return counter === 0 ? product : expt_iter(counter - 1, b * product); } return expt_iter(n, 1); } |