text: <SUBSECTION>
    <NAME>
      Using a Stack to Implement Recursion
    </NAME>
  
    <LABEL NAME="sec:stack-recursion"/>
    <INDEX>stack
    <SUBINDEX>recursion@for recursion in register machine|(</SUBINDEX></INDEX>
    <INDEX>register machine<SUBINDEX>stack|(</SUBINDEX></INDEX>
    <INDEX>recursive process<SUBINDEX>register machine for|(</SUBINDEX></INDEX>
  
    <TEXT>
      <INDEX>iterative process<SUBINDEX>register machine for</SUBINDEX></INDEX>
      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).
    </TEXT>
  
    <TEXT>
      <INDEX>recursive process<SUBINDEX>iterative process vs.</SUBINDEX></INDEX>
      <INDEX>iterative process<SUBINDEX>recursive process vs.</SUBINDEX></INDEX>
      <!--  \indcode{factorial}[register machine for (recursive)|(] -->
      Implementing recursive processes, however, requires an additional
      mechanism.  Consider the following recursive method for computing
      factorials, which we first examined in
      section<SPACE/><REF NAME="sec:recursion-and-iteration"/>:
      <SNIPPET>
        <NAME>factorial_5_1_4</NAME>
        <EXAMPLE>factorial_example</EXAMPLE>
        <EXPECTED>120</EXPECTED>
        <SCHEME>
  (define (factorial n)
    (if (= n 1)
        1
        (* (factorial (- n 1)) n)))
        </SCHEME>
        <JAVASCRIPT>
  function factorial(n) {
      return n === 1 
             ? 1
             : n * factorial(n - 1);
  }      
        </JAVASCRIPT>
      </SNIPPET>
    </TEXT>
  
    <TEXT>
      As we see from the
      <SPLITINLINE>
        <SCHEME>procedure,</SCHEME>
        <JAVASCRIPT>function,</JAVASCRIPT>
      </SPLITINLINE>
      computing <LATEXINLINE>$n!$</LATEXINLINE> requires computing
      <LATEXINLINE>$(n-1)!$</LATEXINLINE>.  Our GCD machine, modeled on the
      <SPLITINLINE>
        <SCHEME>procedure</SCHEME>
        <JAVASCRIPT>function</JAVASCRIPT>
      </SPLITINLINE>
      <SNIPPET PAGE="49" HIDE="yes">
        <NAME>gcd_5_1_4_example</NAME>
        <SCHEME>
  (gcd 20 12)
        </SCHEME>
        <JAVASCRIPT>
  gcd(20, 12);
        </JAVASCRIPT>
      </SNIPPET>
      <SNIPPET>
        <NAME>gcd_5_1_4</NAME>
        <EXAMPLE>gcd_5_1_4_example</EXAMPLE>
        <EXPECTED>4</EXPECTED>
        <SCHEME>
  (define (gcd a b)
    (if (= b 0)
        a
        (gcd b (remainder a b))))
        </SCHEME>
        <JAVASCRIPT>
  function gcd(a, b) {
      return b === 0 ? a : gcd(b, a % b);
  }
        </JAVASCRIPT>
      </SNIPPET>
  
      similarly had to compute another GCD.  But there is an important
      difference between the <SCHEMEINLINE>gcd</SCHEMEINLINE>
      <SPLITINLINE>
        <SCHEME>procedure,</SCHEME>
        <JAVASCRIPT>function,</JAVASCRIPT>
      </SPLITINLINE>
      which reduces the original computation to a new GCD computation, and
      <SCHEMEINLINE>factorial</SCHEMEINLINE>, which requires computing another
      factorial as a subproblem.  In GCD, the answer to the new GCD computation is
      the answer to the original problem.  To compute the next GCD, we simply
      place the new arguments in the input registers of the GCD machine and reuse
      the machine<APOS/>s data paths by executing the same controller sequence.
      When the machine is finished solving the final GCD problem, it has completed
      the entire computation.
    </TEXT>
  
    <TEXT>
      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 <LATEXINLINE>$(n-1)!$</LATEXINLINE> must be
      multiplied by <LATEXINLINE>$n$</LATEXINLINE> to get the final answer.  If
      we try to imitate the GCD design, and solve the factorial subproblem by
      decrementing the <SCHEMEINLINE>n</SCHEMEINLINE> register and rerunning the
      factorial machine, we will no longer have available the old value of
      <SCHEMEINLINE>n</SCHEMEINLINE> 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.
    </TEXT>
  
    <TEXT>
      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
      <LATEXINLINE>$n!$</LATEXINLINE>
      should use the same components to work on the subproblem of computing
      <LATEXINLINE>$(n-1)!$</LATEXINLINE>, on the subproblem for
      <LATEXINLINE>$(n-2)!$</LATEXINLINE>, 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.
    </TEXT>
  
    <TEXT>
      In the subproblem, the contents of the registers will be different
      than they were in the main problem. (In this case the
      <SCHEMEINLINE>n</SCHEMEINLINE> 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
      <SCHEMEINLINE>n</SCHEMEINLINE>, to be restored when we are finished
      computing the factorial of the decremented <SCHEMEINLINE>n</SCHEMEINLINE>
      register.<FOOTNOTE>One might argue that we don<APOS/>t need to save the old
      <SCHEMEINLINE>n</SCHEMEINLINE>; after we decrement it and solve the
      subproblem, we could simply increment it to recover the old value.  Although
      this strategy works for factorial, it cannot work in general, since the old
      value of a register cannot always be computed from the new one.</FOOTNOTE>
    </TEXT>
  
    <TEXT>
      Since there is no <EM>a priori</EM> 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 <EM>stack</EM>, or <QUOTE>last in, first out</QUOTE> 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
      <INDEX>register-machine language
      <SUBINDEX>save@<SCHEMEINLINE>save</SCHEMEINLINE></SUBINDEX></INDEX>
      <!-- \indcodeplus{save}{(in register machine)}-->
      <INDEX>register-machine language
      <SUBINDEX>restore@<SCHEMEINLINE>restore</SCHEMEINLINE></SUBINDEX></INDEX>
      <!-- \indcodeplus{restore}{(in register machine)}-->
      on the stack using a <SCHEMEINLINE>save</SCHEMEINLINE> instruction and
      restored from the stack using a <SCHEMEINLINE>restore</SCHEMEINLINE>
      instruction.  After a sequence of values has been
      <SCHEMEINLINE>save</SCHEMEINLINE>d on the stack, a sequence of
      <SCHEMEINLINE>restore</SCHEMEINLINE>s will retrieve these values in reverse
      order.<FOOTNOTE>In section<SPACE/><REF NAME="sec:storage-allocation"/> we
      will see how to implement a stack in terms of more primitive
      operations.</FOOTNOTE>
    </TEXT>
  
    <TEXT>
      With the aid of the stack, we can reuse a single copy of the factorial
      machine<APOS/>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
      <LATEXINLINE>$(n-1)!$</LATEXINLINE> subproblem
      the machine must still multiply the result by
      <LATEXINLINE>$n$</LATEXINLINE>.  The controller
      must suspend its computation of <LATEXINLINE>$n!$</LATEXINLINE>, solve the
      <LATEXINLINE>$(n-1)!$</LATEXINLINE> subproblem,
      then continue its computation of <LATEXINLINE>$n!$</LATEXINLINE>.  This
      view of the factorial computation suggests the use of the subroutine
      mechanism described in section<SPACE/><REF NAME="sec:subroutines"/>, which
      has the controller use a
      <!-- \indcodeplus{continue}{register}[recursion and]-->
      <SCHEMEINLINE>continue</SCHEMEINLINE> 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 <SCHEMEINLINE>continue</SCHEMEINLINE>
      register.  Around each subroutine call, register, since each
      <QUOTE>level</QUOTE> of the factorial computation will use the same
      <SCHEMEINLINE>continue</SCHEMEINLINE> register.  That is, the factorial
      subroutine must put a new value in <SCHEMEINLINE>continue</SCHEMEINLINE>
      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.
    </TEXT>
  
    <TEXT>
      <SPLITINLINE>
        <SCHEME>
  	Figure<SPACE/><REF NAME="fig:fact-machine_scheme"/>
        </SCHEME>
        <JAVASCRIPT>
  	Figure<SPACE/><REF NAME="fig:fact-machine"/>
        </JAVASCRIPT>
      </SPLITINLINE>
      shows the data paths and controller for
      a machine that implements the recursive
      <SCHEMEINLINE>factorial</SCHEMEINLINE>
      <SPLITINLINE>
        <SCHEME>procedure.</SCHEME>
        <JAVASCRIPT>function.</JAVASCRIPT>
      </SPLITINLINE>
      The machine has a stack and three registers, called
      <SCHEMEINLINE>n</SCHEMEINLINE>, <SCHEMEINLINE>val</SCHEMEINLINE>, and
      <SCHEMEINLINE>continue</SCHEMEINLINE>.  To simplify the data-path diagram,
      we have not named the register-assignment buttons, only the stack-operation
      buttons (<SCHEMEINLINE>sc</SCHEMEINLINE> and <SCHEMEINLINE>sn</SCHEMEINLINE>
      to save registers, <SCHEMEINLINE>rc</SCHEMEINLINE> and
      <SCHEMEINLINE>rn</SCHEMEINLINE> to restore registers).  To operate the
      machine, we put in register <SCHEMEINLINE>n</SCHEMEINLINE> the number whose
      factorial we wish to compute and start the machine.  When the machine
      reaches <SPLITINLINE><SCHEME><SCHEMEINLINE>fact-done</SCHEMEINLINE></SCHEME><JAVASCRIPT><JAVASCRIPTINLINE>fact_done</JAVASCRIPTINLINE></JAVASCRIPT></SPLITINLINE>, the computation is finished
      and the answer will be found in the <SCHEMEINLINE>val</SCHEMEINLINE>
      register.  In the controller sequence, <SCHEMEINLINE>n</SCHEMEINLINE> and
      <SCHEMEINLINE>continue</SCHEMEINLINE> 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
      <SCHEMEINLINE>continue</SCHEMEINLINE>. 
      <SPLITINLINE>
        <SCHEME><SCHEMEINLINE>Continue</SCHEMEINLINE></SCHEME>
        <JAVASCRIPT>
  	The register
  	<SCHEMEINLINE>continue</SCHEMEINLINE>
        </JAVASCRIPT>
      </SPLITINLINE>
      is initialized when the machine starts so that the last return will go to
      <SPLITINLINE><SCHEME><SCHEMEINLINE>fact-done</SCHEMEINLINE></SCHEME><JAVASCRIPT><JAVASCRIPTINLINE>fact_done</JAVASCRIPTINLINE></JAVASCRIPT></SPLITINLINE>.  The
      <SCHEMEINLINE>val</SCHEMEINLINE>
      register, which holds the result of the factorial computation, is not
      saved before the recursive call, because the old contents of
      <SCHEMEINLINE>val</SCHEMEINLINE> is not useful after the subroutine returns.
      Only the new value, which is the value produced by the subcomputation, is
      needed.
      <!--  \indcode{factorial}[register machine for (recursive)|)] -->
    </TEXT>
  
    <TEXT>
      Although in principle the factorial computation requires an infinite
      machine, the machine in
      <SPLITINLINE>
        <SCHEME>
  	figure<SPACE/><REF NAME="fig:fact-machine_scheme"/>
        </SCHEME>
        <JAVASCRIPT>
  	figure<SPACE/><REF NAME="fig:fact-machine"/>
        </JAVASCRIPT>
      </SPLITINLINE>
      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
      <SCHEMEINLINE>continue</SCHEMEINLINE> 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<SPACE/><REF NAME="ex:design-reg-machines"/>).
    </TEXT>
  
    <SUBHEADING>
      <NAME>A double recursion</NAME>
    </SUBHEADING>
  
    <TEXT>
      <!--  \indcode{fib}[register machine for (tree-recursive)] -->
      Let us examine a more complex recursive process, the tree-recursive
      computation of the Fibonacci numbers, which we introduced in
      section<SPACE/><REF NAME="sec:tree-recursion"/>:
      <SNIPPET PAGE="37" HIDE="yes">
        <NAME>fib_5_1_4_example</NAME>
        <SCHEME>
  (fib 6)
        </SCHEME>
        <JAVASCRIPT>
  fib(6);
        </JAVASCRIPT>
      </SNIPPET>
      <SNIPPET>
        <NAME>fib_5_1_4</NAME>
        <EXAMPLE>fib_5_1_4_example</EXAMPLE>
        <EXPECTED>8</EXPECTED>
        <SCHEME>
  (define (fib n)
    (if (&lt; n 2)
        n
        (+ (fib (- n 1)) (fib (- n 2)))))
        </SCHEME>
        <JAVASCRIPT>
  function fib(n) {
      return n === 0
             ? 0
             : n === 1
               ? 1
               : fib(n - 1) + fib(n - 2);
  }
        </JAVASCRIPT>
      </SNIPPET>
    </TEXT>
  
    <TEXT>
      Just as with factorial, we can implement the recursive Fibonacci
      computation as a register machine with registers
      <SCHEMEINLINE>n</SCHEMEINLINE>, <SCHEMEINLINE>val</SCHEMEINLINE>,
      and <SCHEMEINLINE>continue</SCHEMEINLINE>.  The machine is more complex than
      the one for factorial, because there are two places in the controller
      sequence where we need to perform recursive calls<EMDASH/>once to compute
      Fib<LATEXINLINE>$(n-1)$</LATEXINLINE> and once to compute
      Fib<LATEXINLINE>$(n-2)$</LATEXINLINE>.  To set up for each of these calls,
      we save the registers whose values will be needed later, set the
      <SCHEMEINLINE>n</SCHEMEINLINE>
      register to the number whose Fib we need to compute recursively
      (<LATEXINLINE>$n-1$</LATEXINLINE> or <LATEXINLINE>$n-2$</LATEXINLINE>), and
      assign to <SCHEMEINLINE>continue</SCHEMEINLINE> the entry point in the main
      sequence to which to return (<SPLITINLINE><SCHEME><SCHEMEINLINE>afterfib-n-1</SCHEMEINLINE></SCHEME><JAVASCRIPT><JAVASCRIPTINLINE>afterfib_n_1</JAVASCRIPTINLINE></JAVASCRIPT></SPLITINLINE> or
      <SPLITINLINE><SCHEME><SCHEMEINLINE>afterfib-n-2</SCHEMEINLINE></SCHEME><JAVASCRIPT><JAVASCRIPTINLINE>afterfib_n_2</JAVASCRIPTINLINE></JAVASCRIPT></SPLITINLINE>, respectively).  We then go to
      <SPLITINLINE><SCHEME><SCHEMEINLINE>fib-loop</SCHEMEINLINE></SCHEME><JAVASCRIPT><JAVASCRIPTINLINE>fib_loop</JAVASCRIPTINLINE></JAVASCRIPT></SPLITINLINE>.  When we return from the
      recursive call, the answer is in <SCHEMEINLINE>val</SCHEMEINLINE>.
      Figure<SPACE/><REF NAME="fig:fib-machine"/> shows the controller sequence
      for this machine.
      <SPLIT>
        <SCHEME>
  	<!-- 
               %(registers n val continue)
               %(operations * - =)
  	-->
  	<FIGURE src="img_original/Fig5.11b.std.svg">
            <SNIPPET>
              <SCHEME>
  (controller
     (assign continue (label fact-done))     ; set up final return address
   fact-loop
     (test (op =) (reg n) (const 1))
     (branch (label base-case))
     ;; Set up for the recursive call by saving n and continue.
     ;; Set up continue so that the computation will continue
     ;; at after-fact when the subroutine returns.
     (save continue)
     (save n)
     (assign n (op -) (reg n) (const 1))
     (assign continue (label after-fact))
     (goto (label fact-loop))
   after-fact
     (restore n)
     (restore continue)
     (assign val (op *) (reg n) (reg val))   ; val ^now contains $n(n-1)!$^
     (goto (reg continue))                   ; ^return to caller^
   base-case
     (assign val (const 1))                  ; ^base case: $1!=1$^
     (goto (reg continue))                   ; ^return to caller^
   fact-done)
              </SCHEME>
            </SNIPPET>
            <CAPTION>A recursive factorial machine.</CAPTION>
            <!--  \indcode{factorial}[register machine for (recursive)] -->
            <LABEL NAME="fig:fact-machine_scheme"/>
  	</FIGURE>
        </SCHEME>
        <JAVASCRIPT>
  	<FIGURE> 
  	  <FIGURE src="img_javascript/Fig5.11b.std.svg"/> 
            <SNIPPET>
  	    <NAME>factorial_recursive_controller</NAME>
  	    <EXAMPLE>factorial_recursive_example</EXAMPLE>
  	    <EXPECTED>24</EXPECTED>
              <JAVASCRIPT>
  controller(
    list(      
        assign("continue", label("fact_done")), // set up final 
      "fact_loop",                              // rtrn address
        test(list(op("="), reg("n"), constant(1))),
        branch(label("base_case")),
        // Set up for recursive call by saving "n" and "continue".
        // Set up "continue" so that the computation will continue
        // at "after_fact" when the subroutine returns.
        save("continue"),
        save("n"),
        assign("n", list(op("-"), reg("n"), constant(1))),
        assign("continue", label("after_fact")),
        go_to(label("fact_loop")),
      "after_fact",
        restore("n"),
        restore("continue"),
        assign("val", list(op("*"), reg("n"), reg("val"))),
        // "val" now contains n(n-1)!
        go_to(reg("continue")),         // return to caller
      "base_case",
        assign("val", constant(1)),     // base case: val = 1
        go_to(reg("continue")),         // return to caller
      "fact_done"))
              </JAVASCRIPT>
            </SNIPPET>
  	  <SNIPPET HIDE="yes">
  	    <NAME>factorial_recursive_example</NAME>
  	    <REQUIRES>controller</REQUIRES>
  	    <REQUIRES>make_machine</REQUIRES>
  	    <REQUIRES>start</REQUIRES>
  	    <REQUIRES>factorial_recursive_declaration</REQUIRES>
  	    <JAVASCRIPT>
  ;
  	  
  const factorial_recursive_machine =
      make_machine(
          list("n", "val", "continue"),
          list(list("=", (a, b) => a === b),
               list("*", (a, b) => a * b),
               list("-", (a, b) => a - b)),
          controller_sequence(factorial_recursive_controller));
  
  set_register_contents(factorial_recursive_machine, "n", 4);
  start(factorial_recursive_machine);
  get_register_contents(factorial_recursive_machine, "val");
  	</JAVASCRIPT>
        </SNIPPET>
        <SNIPPET HIDE="yes">
  	<NAME>factorial_recursive_declaration</NAME>
  	<JAVASCRIPT>
  const factorial_recursive_controller =
  	</JAVASCRIPT>
        </SNIPPET>
  	  
        <CAPTION>A recursive factorial machine.</CAPTION>
        <!--  \indcode{factorial}[register machine for (recursive)] -->
        <LABEL NAME="fig:fact-machine"/>
  	</FIGURE>
        </JAVASCRIPT>
      </SPLIT>
      <!--  %(registers n val continue) %(operations &lt; - +) -->
      <FIGURE>
        <SNIPPET>
  	<NAME>fib_recursive_controller</NAME>
  	<EXAMPLE>fib_recursive_example</EXAMPLE>
  	<EXPECTED>8</EXPECTED>
  	<SCHEME>
  (controller
     (assign continue (label fib-done))
   fib-loop
     (test (op &lt;) (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)
  	</SCHEME>
  	<JAVASCRIPT>
  controller(
    list(      
      assign("continue", label("fib_done")),
    "fib_loop",
      test(list(op("&lt;"), reg("n"), constant(2))),
      branch(label("immediate_answer")),
      // set up to compute Fib(n-1)
      save("continue"),
      assign("continue", label("afterfib_n_1")),
      save("n"),                     // save old value of n
      // clobber n to n - 1       
      assign("n", list(op("-"), reg("n"), constant(1))), 
      go_to(label("fib_loop")),      // perform recursive call
    "afterfib_n_1",                                
      // upon return, "val" contains Fib(n-1)
      restore("n"),
      restore("continue"),           // set up to compute Fib(n-2)
      assign("n", list(op("-"), reg("n"), constant(2))),
      save("continue"),
      assign("continue", label("afterfib_n_2")),
      save("val"),                   // save Fib(n-1)
      go_to(label("fib_loop")),
    "afterfib_n_2",                  // upon rtrn, val is Fib(n-2)
      assign("n", reg("val")),       // n now contains Fib(n-2)
      restore("val"),                // val now contains Fib(n-1)
      restore("continue"),
      assign("val",                  // Fib(n-1) + Fib(n-2)
        list(op("+"), reg("val"), reg("n"))),
      go_to(reg("continue")),        // back to caller, ans in val
    "immediate_answer",
      assign("val", reg("n")),       // base case: Fib(n) = n
      go_to(reg("continue")),
    "fib_done"))
  	</JAVASCRIPT>
        </SNIPPET>
  
        <SNIPPET HIDE="yes">
  	<NAME>fib_recursive_example</NAME>
  	<REQUIRES>controller</REQUIRES>
  	<REQUIRES>make_machine</REQUIRES>
  	<REQUIRES>start</REQUIRES>
  	<REQUIRES>fib_recursive_declaration</REQUIRES>
  	<JAVASCRIPT>
  ;
  	  
  const fib_recursive_machine =
      make_machine(
          list("n", "val", "continue"),
          list(list("&lt;", (a, b) => a &lt; b),
               list("-", (a, b) => a - b),
               list("+", (a, b) => a + b)),
          controller_sequence(fib_recursive_controller));
  
  set_register_contents(fib_recursive_machine, "n", 6);
  start(fib_recursive_machine);
  get_register_contents(fib_recursive_machine, "val");
  	</JAVASCRIPT>
        </SNIPPET>
  	  <SNIPPET HIDE="yes">
  	    <NAME>fib_recursive_declaration</NAME>
  	    <JAVASCRIPT>
  const fib_recursive_controller =
  	    </JAVASCRIPT>
  	  </SNIPPET>
        
        <CAPTION>Controller for a machine to compute Fibonacci numbers.</CAPTION>
        <LABEL NAME="fig:fib-machine"/>
      </FIGURE>
    </TEXT>
  
    <EXERCISE>
      <LABEL NAME="ex:design-reg-machines"/>
      Specify register machines that implement each of the following
      <SPLITINLINE>
        <SCHEME>procedures.</SCHEME>
        <JAVASCRIPT>functions.</JAVASCRIPT>
      </SPLITINLINE>
      For each machine, write a controller instruction sequence
      and draw a diagram showing the data paths.
      <OL>
        <LI>
  	Recursive exponentiation:
  	<!--  \indcode{expt}[register machine for] -->
  	<SNIPPET>
  	  <NAME>expt_5_1_4</NAME>
  	  <EXAMPLE>expt_5_1_4_example</EXAMPLE>
  	  <EXPECTED>81</EXPECTED>
            <SCHEME>
  (define (expt b n)
    (if (= n 0)
        1
        (* b (expt b (- n 1)))))
            </SCHEME>
  	  <JAVASCRIPT>
  function expt(b, n) {
      return n === 0
          ? 1
          : b * expt(b, n - 1);
  }
  	  </JAVASCRIPT>
  	</SNIPPET>
        </LI>
        <LI>
  	Iterative exponentiation:
  	<SNIPPET PAGE="44" HIDE="yes">
  	  <NAME>expt_5_1_4_example</NAME>
  	  <SCHEME>
  (expt 3 4)
  	  </SCHEME>
  	  <JAVASCRIPT>
  expt(3, 4);
  	  </JAVASCRIPT>
  	</SNIPPET>
  	<SNIPPET>
  	  <NAME>expt_iterative_5_1_4</NAME>
  	  <EXAMPLE>expt_5_1_4_example</EXAMPLE>
  	  <EXPECTED>81</EXPECTED>
            <SCHEME>
  (define (expt b n)
    (define (expt-iter counter product)
      (if (= counter 0)
          product
          (expt-iter (- counter 1) (* b product))))
    (expt-iter n 1))
            </SCHEME>
  	  <JAVASCRIPT>
  function expt(b, n) {	  
      function expt_iter(counter, product) {
          return counter === 0
              ? product
              : expt_iter(counter - 1, b * product);
      }
      return expt_iter(n, 1);
  }
  	  </JAVASCRIPT>
  	</SNIPPET>
        </LI>
      </OL>
    </EXERCISE>
  
    <EXERCISE>
      Hand-simulate the factorial and Fibonacci machines, using some
      nontrivial input (requiring execution of at least one recursive call).
      Show the contents of the stack at each significant point in the
      execution.
      <LABEL NAME="ex:hand-sim"/>
    </EXERCISE>
  
    <EXERCISE>
      Ben Bitdiddle observes that the Fibonacci machine<APOS/>s controller sequence
      has an extra <SCHEMEINLINE>save</SCHEMEINLINE> and an extra
      <SCHEMEINLINE>restore</SCHEMEINLINE>, which can be removed to make a faster
      machine.  Where are these instructions?
    </EXERCISE>
    <INDEX>stack
    <SUBINDEX>recursion@for recursion in register machine|)</SUBINDEX></INDEX>
    <INDEX>register machine<SUBINDEX>stack|)</SUBINDEX></INDEX>
    <INDEX>recursive process<SUBINDEX>register machine for|)</SUBINDEX></INDEX>
  </SUBSECTION>
  