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

#### 11.3.8 No Deferment Solution

The solution to the problem of deferred operations is to write in a manner that does not defer operations13. 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.14

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

##### (13)

The phrase tail recursive is used to describe such a process, one that uses constant space.

##### (14)

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: Recursion without Deferments, Up: Recursion   [Contents][Index]