Previous: No Deferment, Up: Recursion [Contents][Index]

The solution to the problem of deferred operations is to write in a
manner that does not defer operations^{12}. 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.^{13}

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.

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.

Previous: No Deferment, Up: Recursion [Contents][Index]