Node:No deferment solution, Previous:No Deferment, Up:Recursion
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.
The phrase tail recursive is used to describe such a process, one that uses `constant space'.
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.