GNU Info

(emacs-lisp-intro.info)No deferment solution

---

Prev: No Deferment Up: Recursion

---

Enter node , (file) or (file)node

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 then-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.