Info Catalog eintr: No Deferment eintr: Recursion

eintr: No deferment solution

 
 11.3.8 No Deferment Solution
 ----------------------------
 
 The solution to the problem of deferred operations is to write in a
 manner that does not defer operations(1).  This requires writing to a
 different pattern, often one that involves writing two function
 definitions, an initialization function and a helper function.
 
    The initialization function sets up the job; the helper function does
 the work.
 
    Here are the two function definitions for adding up numbers.  They
 are so simple, I find them hard to understand.
 
      (defun triangle-initialization (number)
        "Return the sum of the numbers 1 through NUMBER inclusive.
      This is the initialization component of a two function
      duo that uses recursion."
        (triangle-recursive-helper 0 0 number))
 
      (defun triangle-recursive-helper (sum counter number)
        "Return SUM, using COUNTER, through NUMBER inclusive.
      This is the helper component of a two function duo
      that uses recursion."
        (if (> counter number)
            sum
          (triangle-recursive-helper (+ sum counter)  ; sum
                                     (1+ counter)     ; counter
                                     number)))        ; number
 
    Install both function definitions by evaluating them, then call
 ‘triangle-initialization’ with 2 rows:
 
      (triangle-initialization 2)
          ⇒ 3
 
    The initialization function calls the first instance of the helper
 function with three arguments: zero, zero, and a number which is the
 number of rows in the triangle.
 
    The first two arguments passed to the helper function are
 initialization values.  These values are changed when
 ‘triangle-recursive-helper’ invokes new instances.(2)
 
    Let’s see what happens when we have a triangle that has one row.
 (This triangle will have one pebble in it!)
 
    ‘triangle-initialization’ will call its helper with the arguments
 ‘0 0 1’.  That function will run the conditional test whether ‘(>
 counter number)’:
 
      (> 0 1)
 
 and find that the result is false, so it will invoke the else-part of
 the ‘if’ clause:
 
          (triangle-recursive-helper
           (+ sum counter)  ; sum plus counter ⇒ sum
           (1+ counter)     ; increment counter ⇒ counter
           number)          ; number stays the same
 
 which will first compute:
 
      (triangle-recursive-helper (+ 0 0)  ; sum
                                 (1+ 0)   ; counter
                                 1)       ; number
 which is:
 
      (triangle-recursive-helper 0 1 1)
 
    Again, ‘(> counter number)’ will be false, so again, the Lisp
 interpreter will evaluate ‘triangle-recursive-helper’, creating a new
 instance with new arguments.
 
    This new instance will be;
 
          (triangle-recursive-helper
           (+ sum counter)  ; sum plus counter ⇒ sum
           (1+ counter)     ; increment counter ⇒ counter
           number)          ; number stays the same
 
 which is:
 
      (triangle-recursive-helper 1 2 1)
 
    In this case, the ‘(> counter number)’ test will be true!  So the
 instance will return the value of the sum, which will be 1, as expected.
 
    Now, let’s pass ‘triangle-initialization’ an argument of 2, to find
 out how many pebbles there are in a triangle with two rows.
 
    That function calls ‘(triangle-recursive-helper 0 0 2)’.
 
    In stages, the instances called will be:
 
                                sum counter number
      (triangle-recursive-helper 0    1       2)
 
      (triangle-recursive-helper 1    2       2)
 
      (triangle-recursive-helper 3    3       2)
 
    When the last instance is called, the ‘(> counter number)’ test will
 be true, so the instance will return the value of ‘sum’, which will be
 3.
 
    This kind of pattern helps when you are writing functions that can
 use many resources in a computer.
 
    ---------- Footnotes ----------
 
    (1) The phrase “tail recursive” is used to describe such a process,
 one that uses constant space.
 
    (2) The jargon is mildly confusing: ‘triangle-recursive-helper’ uses
 a process that is iterative in a procedure that is recursive.  The
 process is called iterative because the computer need only record the
 three values, ‘sum’, ‘counter’, and ‘number’; the procedure is recursive
 because the function calls itself.  On the other hand, both the process
 and the procedure used by ‘triangle-recursively’ are called recursive.
 The word “recursive” has different meanings in the two contexts.
 

Info Catalog eintr: No Deferment eintr: Recursion