Recursion Patterns

You have seen several generic patterns for recursive procedures. Here is summary of those patterns.

(define recursive-proc
  (lambda (val)
    (if (base-case-test? val)
        (base-case-computation val)
        (combine (partof val)
                 (recursive-proc (simplify val))))))

For list recursion, the typical base case test is (null? val). However, sometimes we want the base case value to be an item from the list. The base case test for the singleton list is (null? (cdr val)), and the base case computation will usually involve (car val).

Note that the combination step uses the recursive solution. Thus, once the recursive call is completely evaluted, the combination must still be done. As a result, there is still some computation to "unwind." This is one major way in which basic recursion differs from tail recursion, and this form gives rise to the "right-to-left" evaluation behavior of basic recursion.

Helper recursion is also called tail recursion. When we write tail-recursive procedures, we simply use the result of the recursive call, and don't combine it with anything. Here's a simple tail recursive pattern.

(define recursive-proc
  (lambda (val)
     (recursive-proc-helper (initial-result val) (initial-remaining val))))

(define recursive-proc-helper
  (lambda (so-far remaining)
    (if (base-case-test? remaining)
        (final-computation so-far)
        (recursive-proc-helper (combine (part-of remaining) so-far)
                               (simplify remaining)))))

Here, the either the base case value (given by final-computation) or the recursive solution is directly the value of the procedure. In basic recursion, we combine the recursive solution with part of the argument. However, in tail recursion, we combine the answer so far with part of the argument. This combination is then passed along to the recursive recursive call.

Since we have been making computations all along with each recursive call, there are no remaining computations to "unwind" and we can simply return some direct, final processing in the base case. This is why tail recursion can be much more efficient than basic recursion.

Recall that a very important consideration when designing tail recursive solutions are what the initial values in the call to the helper procedure should be.

Recall that our base case is an obvious and immediately identifiable solution to the problem at hand. Sometimes, there will be more than one base case, and these cases may have different solutions. When this happens, you may have more than one distinct base case tests and solutions.

Furthermore, you may also want to take different actions for different recursive cases as well. That is, your combination steps may be different. Here is a more complex pattern for handling multiple base and recursive cases.

(define recursive-proc
  (lambda (val)
    (cond
      ((one-base-case-test? val) 
       (one-base-case-computation val))
      ((another-base-case-test? val) 
       (another-base-case-computation val))
      ...
      ((special-recursive-case-test-1? val)
       (combine-1 (partof-1 val)
                  (recursive-proc (simplify-1 val))))
      ((special-recursive-case-test-2? val)
       (combine-2 (partof-2 val)
                  (recursive-proc (simplify-2 val))))
      ...
      (else
       (combine (partof val)
                (recursive-proc (simplify val)))))))

However, in practice you will find that you rarely have more than two base-case tests (mostly one) and rarely more than two recursive cases.

Of course, we can write recursive predicates using conditionals with the patterns above. However, as we've noted, it is more elegant to use and and or to produce a Boolean value.

We can use the following templates as a structure for checking whether a predicate is true of all or any items in a list.

(define all-____?
  (lambda (lst)
    (or (null? lst)
        (and (____? (car lst))
             (all-____? (cdr lst))))))

(define any-____?
  (lambda (lst)
    (and (not (null? lst))
         (or (____? (car lst))
             (any-____? (cdr lst))))))