Skip to main content

Recursion with helper procedures

Due
Friday, 15 March 2019
Summary
You’ve now seen a bit of the basics of recursion as a program design strategy. We now consider an alternate technique for writing recursive procedures, one in which we build helpers that carry along a partial result at each step. We also see how such helpers can be used to create tail recursive solutions, which are often more efficient than more basic recursive procedures.

Introduction

There are a few basic principles to writing recursive functions. As you may recall from the first reading on recursion, a recursive procedure is one that calls itself. To successfully write a recursive procedure, you need

  • a base case, in which you compute the result without a recursive call;
  • a recursive case, in which you simplify the problem, compute a partial result recursively, and then combine that partial result with another value to yield the complete result; and
  • a base-case guard, in which you decide whether to use the base case or the recursive case.

A disadvantage of traditional recursion is that it is difficult to tell what is happening along the way. In the particular case of list recursion, we typically work all the way down to the end of the list, and then work our way back to the front of the list to compute a final result. When they encounter this issue, many students ask, Why not just compute the result as we go? We consider that approach in this reading.

Review: Scheme’s evaluation strategy

Before we go much further, let’s take a quick detour into an important concept that we’ve discussed before: When Scheme has a nested expression to evaluate, how does it evaluate that expression? The technique it uses is pretty straightforward: In order to apply a procedure to parameters, those parameters must be in simple form (that is, values, rather than expressions to compute values). Hence, given (proc exp1 exp2 exp3), Scheme first evaluates exp1, exp2, and exp3, looks up proc in the environment, and then applies the procedure it finds to the three resulting values.

In what order does it evaluate exp1, exp2, and exp3? It turns out that it depends on the implementation of Scheme. In our sample code, we’ll always assume that the Scheme interpreter evaluates the parameters from left to right.

Of course, for some operations (which we call “keywords” or “syntax”), the Scheme interpreter uses a different evaluation strategy. For example, when evaluating an if expression, the interpreter does not evaluate all three parameters. Instead, it evaluates them in a specified order (first the test, then only one of the consequent and alternate). Similarly, when evaluating an and or an or, the interpreter evaluates the parameters one at a time, stopping as soon as it knows an answer (in the case of and, when it hits a #f; in the case of or, when it hits a #t).

But there’s more. To understand how Scheme evaluates expressions, we must also understand how it applies the procedures you define and how it processes definitions in general.

The naming scheme that Scheme uses is relatively straightforward. Scheme keeps a table of correspondences between names and values. For each name, it stores a reference to the value, which means that two names can refer to the same value. (This is important to know, because if you change a value with a side-effecting function, then all references to that value seem to change.) If you write another definition using the same name, it changes the reference, but not the underlying value. When Scheme sees a name while evaluating an expression, it looks up the name in the table, and uses the value the name refers to.

The way procedures work takes advantage of this naming scheme. When you call a procedure on some arguments, the Scheme interpreter first updates the name table, mapping each name in the lambda to the corresponding argument. For example, if you apply (lambda (a b c) ...) to 3, 1, and 6, the table will now have a refer to 3, b refer to 1, and c refer to 6. After updating the table, the interpreter evaluates the body of the procedure. When it finishes evaluating the body, it cleans up the name table, removing any new entries it had added.

Why is the way Scheme evaluates and understands expressions important for recursion? First, it may help you understand how recursion works. Because if (or cond), delays the evaluation of the consequent and alternate, we can safely have a procedure call itself without worrying about it calling itself again and again and again, ad infinitum. Second, it clarifies how we can have the same names (the parameters) mean different things at different times.

Recursive sum, re-examined

In case you’ve forgotten the example from the prior reading, let’s consider the first version of sum computes the sum of the list with elements 38, 12, 93. (To keep the example concise, we leave out the computations involving car and cdr.)

   (sum (list 38 12 83))
=> (if (null? (list 38 ...)) 0 (+ 38 (sum (list 12 83))))
=> (+ 38 (sum (list 12 83)))
=> (+ 38 (if (null? (list 12 ..)) 0 (+ 12 (sum (list 83)))))
=> (+ 38 (+ 12 (sum (list 83))))
=> (+ 38 (+ 12 (if (null? (list 83)) 0 (+ 83 (sum null)))))
=> (+ 38 (+ 12 (+ 83 (sum null))))
=> (+ 38 (+ 12 (+ 83 (if (null? null) 0 (+ (car null) (sum (cdr null)))))))
=> (+ 38 (+ 12 (+ 83 0)))
=> (+ 38 (+ 12 83))
=> (+ 38 95)
=> 133

If we pull out the tests (which are fairly straightforward), we can think of the computation as follows.

   (sum (cons 38 (cons 12 (cons 83 null)))) 
=> (+ 38 (sum (cons 12 (cons 83 null)))))
=> (+ 38 (+ 12 (sum (cons 83 null))))
=> (+ 38 (+ 12 (+ 83 (sum null))))
=> (+ 38 (+ 12 (+ 83 0)))
=> (+ 38 (+ 12 83))
=> (+ 38 95)
=> 133

An alternative sum

Now, let’s return to our goal: Looking at other ways to do recursion. We’ll consider the question of computing results as we go with the summation example from the previous reading. As you may have noted, an odd thing about the sum procedure is that it works from right to left. Traditionally, we sum from left to right. Can we rewrite sum to work from left to right? Certainly, but we may need a helper procedure (another procedure whose primary purpose is to assist our current procedure) to do so.

If you think about it, when you’re summing a list of numbers from left to right, you need to keep track of two different things:

  • The sum of the values seen so far.
  • The remaining values to sum.

Hence, we’ll build our helper procedure with two parameters, sum-so-far and remaining. We’ll start the body with a template for recursive procedures (a guard to determine whether to use the base case or recursive case, the base case, and the recursive case). We’ll then fill in each part.

(define new-sum-helper
  (lambda (sum-so-far remaining)
     (if (guard)
         base-case
         recursive-case)))

The recursive case is fairly easy. Recall that since remaining is a list, we can split it into two parts, the first element (that is, the car), and the remaining elements (that is, the cdr). Each part contributes to one of the parameters of the recursive call. We update sum-so-far by adding the first element of remaining to sum-so-far. We update remaining by removing the first element. To “continue”, we simply call new-sum-helper again with those updated parameters.

(define new-sum-helper
  (lambda (sum-so-far remaining)
     (if (guard)
         base-case
         (new-sum-helper (+ sum-so-far (car remaining))
                         (cdr remaining)))))

The recursive case then gives us a clue as to what to use for the guard. We need to stop when there are no elements left in the list. (Otherwise, taking the car and the cdr would create errors.)

(define new-sum-helper
  (lambda (sum-so-far remaining)
     (if (null? remaining)
         base-case
         (new-sum-helper (+ sum-so-far (car remaining))
                         (cdr remaining)))))

We’re almost done. What should the base case be? In the previous version, it was 0. However, in this case, we’ve been keeping a running sum. When we run out of things to add, the value of the complete sum is the value of the running sum.

(define new-sum-helper
  (lambda (sum-so-far remaining)
     (if (null? remaining)
         sum-so-far
         (new-sum-helper (+ sum-so-far (car remaining))
                         (cdr remaining)))))

Now we’re ready to write the primary procedure whose responsibility it is to call new-sum-helper. Like sum, new-sum will take a list as a parameter. That list will become remaining. What value should sum-so-far begin with? Since we have not yet added anything when we start, it begins at 0.

(define new-sum
  (lambda (numbers)
    (new-sum-helper 0 numbers)))

Putting it all together, we get the following.

;;; Procedure:
;;;   new-sum
;;; Parameters:
;;;   numbers, a list of numbers.
;;; Purpose:
;;;   Find the sum of the elements of a given list of numbers
;;; Produces:
;;;   total, a number.
;;; Preconditions:
;;;   All the elements of numbers must be numbers.
;;; Postcondition:
;;;   total is the result of adding together all of the elements of numbers.
;;;   If all the values in numbers are exact, total is exact.
;;;   If any values in numbers are inexact, total is inexact.
(define new-sum
  (lambda (numbers)
    (new-sum-helper 0 numbers)))

;;; Procedure:
;;;   new-sum-helper
;;; Parameters:
;;;   sum-so-far, a number.
;;;   remaining, a list of numbers.
;;; Purpose:
;;;   Add sum-so-far to the sum of the elements of a given list of numbers
;;; Produces:
;;;   total, a number.
;;; Preconditions:
;;;   All the elements of remaining must be numbers.
;;;   sum-so-far must be a number.
;;; Postcondition:
;;;   total is the result of adding together sum-so-far and all of the
;;;     elements of remaining.
;;;   If both sum-so-far and all the values in remaining are exact,
;;;     total is exact.
;;;   If either sum-so-far or any values in remaining are inexact,
;;;     total is inexact.
(define new-sum-helper
  (lambda (sum-so-far remaining)
     (if (null? remaining)
         sum-so-far
         (new-sum-helper (+ sum-so-far (car remaining))
                         (cdr remaining)))))

Note that it is a bit difficult to write the documentation for the helper procedure, since we have to think about the role of the sum-so-far parameter in the context of the overall goal. At the same time, doing so helps us clarify exactly what we expect the procedure to do. It also helps us verify that the base case is appropriate. In this case, since we’re supposed to add the intermediate sum to the sum of the remaining values, when there are no remaining values, we can just add 0 and stop.

Watching new sum

Does this change make a difference in the way in which the sum is evaluated? Let’s look

   (new-sum (list 38 12 83))
=> (new-sum-helper 0 (list 38 12 83))
=> (if (null? (list 38 ...)) 0 (new-sum-helper (+ 0 38) (cdr (list 38 ...))))
=> (new-sum-helper (+ 0 38) (list 12 83))
=> (new-sum-helper 38 (list 12 83))
=> (if (null? (list 12 ...)) 38 (new-sum-helper (+ 38 12) (cdr (list 12 ...))))
=> (new-sum-helper (+ 38 12) (list 83))
=> (new-sum-helper 50 (list 83))
=> (if (null? (list 83)) 50 (new-sum-helper (+ 50 83) (cdr (list 83))))
=> (new-sum-helper (+ 50 83) null)
=> (new-sum-helper 133 null)
=> (if (null? null) 133 (new-sum-helper (+ 133 (car null)) (cdr null)))
=> 133

If we don’t show the conditional steps, we get the following as the basic structure of the recursion.

   (new-sum (list 38 12 83))
=> (new-sum-helper 0 (list 38 12 83))
=> (new-sum-helper (+ 0 38) (list 12 83))
=> (new-sum-helper 38 (list 12 83))
=> (new-sum-helper (+ 38 12) (list 83))
=> (new-sum-helper 50 (list 83))
=> (new-sum-helper (+ 50 83) null)
=> (new-sum-helper 133 null)
=> 133

Note that the intermediate results for new-sum were different, primarily because new-sum operates from left to right rather than right to left.

Detour: Logging procedure calls

While we will soon learn some systematic ways to explore what happens during recursive calls, there is a simple approach that many students find useful. The display procedure prints out its input and the newline procedure moves on to a new line. Using those together, it is relatively straightforward to print out the basic information on a procedure call.

(define proc
  (lambda (params)
    (display (list 'proc params)) (newline)
    ...))

Note that we quote the name of the procedure so that it is not evaluated, but we leave the names of the parameters unquoted so that the Scheme interpreter looks up the values associated with those parameters.

Let’s make that change to the helper we introduced above.

(define new-sum-helper
  (lambda (sum-so-far remaining)
     (display (list 'new-sum-helper sum-so-far remaining))
     (if (null? remaining)
         sum-so-far
         (new-sum-helper (+ sum-so-far (car remaining))
                         (cdr remaining)))))

Now, let’s see what happens when we run the program.

> (new-sum-helper 0 (list 38 12 83))
(new-sum-helper 0 (38 12 83))
(new-sum-helper 38 (12 83))
(new-sum-helper 50 (83))
(new-sum-helper 133 ())
133

Not quite as detailed as our example above, but enough to help us see what’s happening.

The technique, generalized

Okay, how does one write one of these procedures that accumulates a result as you go? First, you build a helper procedure that takes as parameters (1) the list you’re recursing over, which we’ve called remaining, (2) a new parameter, ____-so-far, and (3) any other useful parameters. The helper recurses over the list, updating that list to its cdr at each step and updates ____-so-far to be the next partial result. At the end, the procedure typically returns ____-so-far or something computed from that value.

After creating the helper, you build the main procedure, which calls the helper with an appropriate initial ____-so-far and remaining. For example,

(define proc
  (lambda (lst)
    (proc-helper initial-value lst)))
(define proc-helper
  (lambda (so-far remaining)
    (if (null? remaining)
        so-far
        (proc-helper (combine so-far (car remaining))
                     (cdr remaining)))))

However, as we’ll see in the next section, you sometimes need to use different initial values for so-far and remaining.

In designing the helper, many of us find it useful to make a little table to track what is happening. In particular, we think it useful to think about what should happen to the intermediate result as we delete each value from the list.

Another application: Difference

We’ve now seen two strategies for doing recursion: We can combine the result of a recursive call into a final result, or we can pass along intermediate results as we recurse, and stop with the final result. Which should you use? For many applications, it doesn’t matter. However, there are times that one technique is much more appropriate than the other. Consider a procedure that takes a list of numbers, n1, n2, n3, … nk-1, nk, and computes n1 - n2 - n3 - … - nk-1 - nk.

Suppose we use the first technique. We might write:

(define difference
  (lambda (lst)
    (if (null? lst)
        0
        (- (car lst) (difference (cdr lst))))))

Unfortunately, this procedure doesn’t quite work as you might expect. Consider the computation of (difference (list 1 2 3)). As you may recall, subtraction is left associative, so this should be (1-2)-3, or -4. Let’s see what happens.

   (difference (cons 1 (cons 2 (cons 3 null))))
=> (- 1 (difference (cons 2 (cons 3 null))))
=> (- 1 (- 2 (difference (cons 3 null))))
=> (- 1 (- 2 (- 3 (difference null))))
=> (- 1 (- 2 (- 3 0)))
=> (- 1 (- 2 3))
=> (- 1 -1)
=> 2

Hmmm … that’s not quite right. So, let’s try the new technique of using a helper.

(define new-difference
  (lambda (lst)
    (new-difference-helper 0 lst)))

(define new-difference-helper
  (lambda (difference-so-far remaining)
    (if (null? remaining)
        difference-so-far
        (new-difference-helper (- difference-so-far (car remaining))
                               (cdr remaining)))))

Okay, what happens here?

   (new-difference (list 1 2 3))
=> (new-difference-helper 0 (list 1 2 3))
=> (new-difference-helper (- 0 1) (list 2 3))
=> (new-difference-helper -1 (list 2 3))
=> (new-difference-helper (- -1 2) (list3))
=> (new-difference-helper -3 (list3))
=> (new-difference-helper (- -3 3) null)
=> (new-difference-helper -6 null)
=> -6

Nope. Still incorrect. So, what happened? We started with 0, then we subtracted 1, then we subtracted 2, then we subtracted 3. It looks like we did those last two subtractions in order. But wait! Why are we subtracting 1? That’s the value we’re supposed to subtract everything else from. That means we need to choose a better initial difference-so-far and remaining. Why not make the car the difference-so-far and the cdr remaining?

(define newer-difference
  (lambda (lst)
    (new-difference-helper (car lst) (cdr lst))))

Does this work?

   (newer-difference (list 1 2 3))
=> (new-difference-helper 1 (list 2 3))
=> (new-difference-helper (- 1 2) (list 3))
=> (new-difference-helper -1 (list 3))
=> (new-difference-helper (- -1 3) null)
=> (new-difference-helper -4 null)
=> -4

It works! Well, at least it works for this example. In the lab, we’ll explore whether it works for other examples, too.

Note, also, that there is a much more straightforward way to define difference.

(define difference
  (lambda (lst)
    (- (car lst) (sum (cdr lst)))))

Terminology: Tail recursion

You have probably noticed an important difference between the first form of recursion we used and the helper version: In the original form, once we reached the base case, we had to back up and do more computation. In this new form, it seems that once we reach the base case, we’re done. Behind the scenes for the original form, the Scheme interpreter has to spend extra effort to remember the extra work to be done after the base case is reached. In this new form, it does not.

When a recursive procedure has completely finished its computation at the base case, the procedure is called tail recursive. A tail-recursive version of a procedure is often (but not always) more efficient than the non-tail-recursive version. Hence, many Scheme programmers regularly convert their procedures to tail-recursive form. How do you convert to this form? Most frequently, you use the techniques in this reading: You create a recursive helper procedure that accumulates the value to be computed.

Recursion and efficiency

When we write recursive procedures carelessly, we can create very inefficient computation. Let us consider, for a moment, the problem of computing the number furthest from zero in a list of real numbers. (That is, the element of the list with the largest absolute value.)

Before writing any code, we should, of course write the introductory documentation.

;;; Procedure:
;;;   furthest-from-zero
;;; Parameters:
;;;   numbers, a nonempty list of real numbers
;;; Purpose:
;;;   Find the number in the list with the largest absolute value.
;;; Produces:
;;;   furthest, a real number
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   furthest is an element of numbers
;;;   For any number, n, in numbers
;;;     (>= (abs furthest) (abs n))

Now we are ready to write some code. Let us first consider a basic recursive solution. We start with the template of a recursive procedure.

(define furthest-from-zero
  (lambda (numbers)
    (if (check)
        base-case
        recursive-case)))

The guard and base case are straightforward: If there is only one value left in the list, it is clearly the number furthest from zero.

(define furthest-from-zero
  (lambda (numbers)
    (if (null? (cdr numbers))
        (car numbers)
        recursive-case)))

If you’re not sure why we used (null? (cdr numbers)), think about the cost of the alternative, (= (length numbers) 1). To find the length of a list means looking through all the elements. Hence, if we’re finding looking at a list of ten numbers, first we have to spend ten steps finding out that there are ten numbers (not one). In the recursive call, we have to spend nine steps finding out that there are nine numbers remaining. Then eight steps in the next list. And so on and so forth. That’s really inefficient. We should be able to quickly determine whether a list has one element, independent of how many elements are in the list. (null? (cdr numbers)) achieves that goal.

Back to our procedure. What should we do in the recursive case? Suppose we compute the number furthest from zero in the remainder of the list. What does that tell us about the number furthest from zero in the list? Well, the number furthest from zero is either the number furthest from zero number in the remainder or the first number, whichever has the larger absolute value. We can express that choice as a second conditional.

         (if (>= (abs (car numbers)) 
                 (abs (furthest-from-zero (cdr numbers))))
             (car numbers)
             (furthest-from-zero (cdr numbers)))

When we plug that into the rest of the procedure, we get

(define furthest-from-zero
  (lambda (numbers)
    (if (null? (cdr numbers))
        (car numbers)
        (if (>= (abs (car numbers)) 
                (abs (furthest-from-zero (cdr numbers))))
            (car numbers)
            (furthest-from-zero (cdr numbers))))))

Most Scheme programmers, when confronted with these nested if statements, will turn them into a cond statement.

(define furthest-from-zero
  (lambda (numbers)
    (cond
      [(null? (cdr numbers))
       (car numbers)]
      [(>= (abs (car numbers)) 
           (abs (furthest-from-zero (cdr numbers))))
       (car numbers)]
      [else
       (furthest-from-zero (cdr numbers))])))

Both of these solutions are correct. However, both are quite inefficient. What makes them inefficient? The two recursive calls. Normally, you wouldn’t think that two calls would make a huge difference (well, maybe a factor of two). However, for recursive procedures, the expense of the extra call grows exponentially.

Consider the particular case of of a list of five elements in which the last element is the furthest from zero. In the guard, we recurse on the list of four elements in the guard. When that recursive call finishes, we recurse again on the same list in order to compute the alternate. Now, let us consider one of those identical recursive calls. Once again, the guard requires us to recurse on the cdr (the list of three elements). And, once again, we need to recurse on that same list when we compute the alternate. Since we had to find the furthest-from-zero element of the list of four elements twice, we had to find the furthest-from-zero element of the list of three elements four times.

Each of those computations (that is, finding the furthest-from-zero element in a list of three elements), needs to recurse on a list of two elements twice, once for the guard and once for the alternate. Given that we found the furthest-from-zero element of the same list of three elements four times, we find the furthest-from-zero element of the same list of two elements eight times.

We’re almost done with the analysis. For each of those identical computations of the furthest-from-zero element in a list of two elements, we find the furthest-from-zero element in the singleton list twice (once for the guard, once for the alternate). Since there are eight calls involving the list of two elements, there are sixteen calls involving the list of one element.

How many calls to furthest-from-zero did we end up with? Let’s see … one for the list of five elements, two for the sublist of four elements, four for the sublist of three elements, eight for the sublist of two elements, and sixteen for the sublist of one element. 1 + 2 + 4 + 8 + 16 is 31. That’s a lot of calls for a list of five numbers. If we had a list of six numbers, it could take 63 calls. If we had a list of ten numbers, it could take over one thousand calls.

You would hope that we could come up with a solution that does not require many more recursive calls than the elements of the list. And such a solution is possible with a helper. This time, we’ll keep track of the number furthest from zero that we’ve seen so far. We’ll model the solution on difference, which had the following form:

(define procedure
  (lambda (lst)
    (procedure-helper (car lst) (cdr lst))))
(define procedure-helper
  (lambda (so-far remaining)
    (if (null? remaining)
        so-far
        (procedure-helper (combine so-far (car remaining))
                          (cdr remaining)))))

We’ll start by plugging in appropriate names.

(define furthest-from-zero
  (lambda (numbers)
    (furthest-from-zero-helper (car numbers) (cdr numbers))))
(define furthest-from-zero-helper
  (lambda (furthest-so-far numbers-remaining)
    (if (null? numbers-remaining)
        furthest-so-far
        (furthest-from-zero-helper
         (combine furthest-so-far (car numbers-remaining))
         (cdr numbers-remaining)))))

Now, how do we update our estimate of the number furthest from zero, given a previous estimate and one additional number. If the new number is further from zero, we use it. If the original estimate is further from zero, we use it.

(define furthest-from-zero
  (lambda (numbers)
    (furthest-from-zero-helper (car numbers) (cdr numbers))))
(define furthest-from-zero-helper
  (lambda (furthest-so-far numbers-remaining)
    (if (null? numbers-remaining)
        furthest-so-far
        (furthest-from-zero-helper
         (if (>= (abs furthest-so-far) 
                 (abs (car numbers-remaining)))
             furthest-so-far
             (car numbers-remaining))
         (cdr numbers-remaining)))))

This solution is both correct and efficient, but some folks have trouble reading that conditional in the middle. We can clarify the code by writing a procedure, (further-from-zero val1 val2), that, given two real numbers, finds out which is further from zero (that is, which has the larger absolute value). Once we’ve written that procedure, we can rewrite the helper as

(define furthest-from-zero
  (lambda (numbers)
    (furthest-from-zero-helper (car numbers) (cdr numbers))))
(define furthest-from-zero-helper
  (lambda (furthest-so-far numbers-remaining)
    (if (null? numbers-remaining)
        furthest-so-far
        (furthest-from-zero-helper
         (further-from-zero furthest-so-far (car numbers-remaining))
         (cdr numbers-remaining)))))

Now, let’s consider what happens when we try to find the number furthest from zero in the list `(1 -2 -3 4 -5) number in

   (furthest-from-zero (list 1 -2 -3 4 -5)
=> (furthest-from-zero-helper 1 (list -2 -3 4 -5))
=> (furthest-from-zero-helper (further-from-zero 1 -2) (list -3 4 -5))
=> (furthest-from-zero-helper -2 (list -3 4 -5))
=> (furthest-from-zero-helper (further-from-zero -2 -3) (list 4 -5))
=> (furthest-from-zero-helper -3 (list 4 -5))
=> (furthest-from-zero-helper (further-from-zero -3 4) (list -5))
=> (furthest-from-zero-helper 4 (list -5))
=> (furthest-from-zero-helper (further-from-zero 4 -5) (list))
=> (furthest-from-zero-helper -5 (list))
=> -5

Not bad. About five recursive calls (plus four calls to further-from-zero). And, the process looks clear enough that we can be fairly confident that with a list of size ten, this will take only ten recursive calls (plus nine calls to further-from-zero).

Of course, for this new version to work, we need to have further-from-zero defined. But that is straightforward.

;;; Procedure:
;;;   further-from-zero
;;; Parameters:
;;;   val1, a real number
;;;   val2, a real number
;;; Purpose:
;;;   Choose whichever of val1 and val2 is further from zero.
;;; Produces:
;;;   further, a real number
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   further is either val1 or val2
;;;   (abs further) >= (abs val1)
;;;   (abs further) >= (abs val2)
(define further-from-zero
  (lambda (val1 val2)
    (if (>= (abs val1) (abs val2))
        val1
        val2)))

Of course, once we’ve defined further-from-zero, we might want to revisit the design of our first recursive version. You may recall that we’d gotten to this following stage in our design:

(define furthest-from-zero
  (lambda (numbers)
    (if (null? (cdr numbers))
        (car numbers)
        recursive-case)))

Now, what goes in the recursive case? We said “Suppose we compute the number furthest from zero in the remainder of the list … the number furthest from zero is either the number furthest from zero in the remainder or the first number, whichever is further from zero.” We then expressed that decision as a conditional. Now we can express it using further-from-zero.

(define furthest-from-zero
  (lambda (numbers)
    (if (null? (cdr numbers))
        (car numbers)
        (further-from-zero (car numbers)
                           (furthest-from-zero (cdr numbers))))))

Now, let’s trace what this procedure does on the same list.

   (furthest-from-zero (list 1 -2 -3 4 -5)
=> (further-from-zero 1 (furthest-from-zero (list -2 -3 4 -5)))
=> (further-from-zero 1 (further-from-zero -2 (furthest-from-zero (list -3 4 -5))))
=> (further-from-zero 1 (further-from-zero -2 (further-from-zero -3 (furthest-from-zero (list 4 -5)))))
=> (further-from-zero 1 (further-from-zero -2 (further-from-zero -3 (further-from-zero 4 (furthest-from-zero (list -5))))))
=> (further-from-zero 1 (further-from-zero -2 (further-from-zero -3 (further-from-zero 4 -5))))
=> (further-from-zero 1 (further-from-zero -2 (further-from-zero -3 -5)))
=> (further-from-zero 1 (further-from-zero -2 -5))
=> (further-from-zero 1 -5)
=> -5

In terms of computation, this seems about the same as the second helper version: We did five recursive calls and four calls to further-from-zero. However, we see that the calls to further-from-zero get stacked up, which makes it a bit more difficult for the interpreter.

What should you take away from this discussion? A number of things. First, if a recursive procedure has more than one recursive call per datum, it is likely to be absurdly slow. (Later in the semester, we’ll see some times in which multiple recursive calls are okay. However, such situations are rare.) Second, as you’ve likely already learned, there is often more than one way to solve the same problem. We’ve seen five or so different solutions to the same problem. Third, once you’ve written a procedure, it can be useful to step back and think about how you can make it clearer. Finally, standard recursion tends to create a backlog of delayed actions, which are finally performed when the base case is reached. In contrast, tail recursion creates no such backlog.

Self checks

Check 1: Helper recursion forms

Fill in the blanks, using the common form for tail recursive procedures given above with newer-difference:

  • The procedure is ___________________ and procedure-helper is __________________.
  • The initial value of so-far is ______________________.
  • The initial value of remaining is ______________________.
  • The base case check is ________________, which checks whether ________________.
  • The base case value is _________________, which _________________.
  • The simplifying procedure is _____________, which _________________, thereby giving us a “simpler value.”
  • Finally, the combine procedure is ___________________, which _____________________.