Info Catalog eintr: Recursive Patterns eintr: Recursion eintr: No deferment solution

eintr: No Deferment

 
 11.3.7 Recursion without Deferments
 -----------------------------------
 
 Let’s consider again what happens with the ‘triangle-recursively’
 function.  We will find that the intermediate calculations are deferred
 until all can be done.
 
    Here is the function definition:
 
      (defun triangle-recursively (number)
        "Return the sum of the numbers 1 through NUMBER inclusive.
      Uses recursion."
        (if (= number 1)                    ; do-again-test
            1                               ; then-part
          (+ number                         ; else-part
             (triangle-recursively          ; recursive call
              (1- number)))))               ; next-step-expression
 
    What happens when we call this function with a argument of 7?
 
    The first instance of the ‘triangle-recursively’ function adds the
 number 7 to the value returned by a second instance of
 ‘triangle-recursively’, an instance that has been passed an argument of
 6.  That is to say, the first calculation is:
 
      (+ 7 (triangle-recursively 6))
 
 The first instance of ‘triangle-recursively’—you may want to think of it
 as a little robot—cannot complete its job.  It must hand off the
 calculation for ‘(triangle-recursively 6)’ to a second instance of the
 program, to a second robot.  This second individual is completely
 different from the first one; it is, in the jargon, a “different
 instantiation”.  Or, put another way, it is a different robot.  It is
 the same model as the first; it calculates triangle numbers recursively;
 but it has a different serial number.
 
    And what does ‘(triangle-recursively 6)’ return?  It returns the
 number 6 added to the value returned by evaluating
 ‘triangle-recursively’ with an argument of 5.  Using the robot metaphor,
 it asks yet another robot to help it.
 
    Now the total is:
 
      (+ 7 6 (triangle-recursively 5))
 
    And what happens next?
 
      (+ 7 6 5 (triangle-recursively 4))
 
    Each time ‘triangle-recursively’ is called, except for the last time,
 it creates another instance of the program—another robot—and asks it to
 make a calculation.
 
    Eventually, the full addition is set up and performed:
 
      (+ 7 6 5 4 3 2 1)
 
    This design for the function defers the calculation of the first step
 until the second can be done, and defers that until the third can be
 done, and so on.  Each deferment means the computer must remember what
 is being waited on.  This is not a problem when there are only a few
 steps, as in this example.  But it can be a problem when there are more
 steps.
 

Info Catalog eintr: Recursive Patterns eintr: Recursion eintr: No deferment solution