More Recursion

While the recursive procedures we've written so far have used lists as arguments, we can also write recursive procedures with numbers as arguments. Like lists, natural numbers have a recursive structure of which we can take advantage when we write direct-recursion procedures. A natural number is either (a) zero, or (b) the successor of a smaller natural number, which we can obtain by subtracting 1.

Standard Scheme provides the predicate zero? to distinguish between the (a) and (b) cases, so we can again use an if-expression to ensure that only the expression for the appropriate case is evaluated. So we can write a procedure that applies to any natural number if we know (a) what value it should return when the argument is 0 and (b) how to convert the value that the procedure would return for the next smaller natural number into the appropriate return value for a given non-zero natural number.

For instance, here is a procedure that computes the termial of any natural number number, that is, the result of adding together all of the natural numbers up to and including number:

;;; termial: compute the sum of natural numbers not greater than a given
;;; natural number 

;;; Given:
;;;   NUMBER, a natural number.

;;; Result:
;;;   SUM, a natural number.

;;; Preconditions:
;;;   None.

;;; Postcondition:
;;;   SUM is the sum of the natural numbers not greater than NUMBER.

(define termial
  (lambda (number)
    (if (zero? number)
        0
        (+ number (termial (- number 1))))))

Whereas in a list recursion, we called the cdr procedure to reduce the length of the list in making the recursive call, the operation that we apply in recursion with natural numbers is reducing the number by 1. Here's a summary of what actually happens during the evaluation of a call to the termial procedure -- say, (termial 5):

    (termial 5)
--> (+ 5 (termial 4))
--> (+ 5 (+ 4 (termial 3)))
--> (+ 5 (+ 4 (+ 3 (termial 2))))
--> (+ 5 (+ 4 (+ 3 (+ 2 (termial 1)))))
--> (+ 5 (+ 4 (+ 3 (+ 2 (+ 1 (termial 0))))))
--> (+ 5 (+ 4 (+ 3 (+ 2 (+ 1 0)))))
--> (+ 5 (+ 4 (+ 3 (+ 2 1))))
--> (+ 5 (+ 4 (+ 3 3)))
--> (+ 5 (+ 4 6))
--> (+ 5 10)
--> 15

The restriction that termial takes only natural numbers as arguments is an important one: If we gave it a negative number or a non-integer, we'd have a runaway recursion, because we cannot get to zero by subtracting 1 repeatedly from a negative number or from a non-integer, and so the base case would never be reached. If we gave the termial procedure an approximation rather than an exact number, we might or might not be able to reach zero, depending on how accurate the approximation is and how much of that accuracy is preserved by the subtraction procedure.

The important part of getting recursion to work is making sure that the base case is inevitably reached by performing the simplification operation enough times. For instance, we can use direct recursion on exact positive integers with 1, rather than 0, as the base case.

;;; factorial: compute the product of positive integers not
;;; greater than a given positive integer

;;; Given:
;;;   NUMBER, an integer.

;;; Result:
;;;   PRODUCT, an integer.

;;; Precondition:
;;;   NUMBER is positive and exact.

;;; Postcondition:
;;;   PRODUCT is the product of the positive integers not
;;;   greater than NUMBER.

(define factorial
  (lambda (number)
    (if (= number 1)
        1
        (* number (factorial (- number 1))))))

We require the invoker of this factorial procedure to provide an exact, strictly positive integer. (Zero won't work in this case, because we can't reach the base case, 1, by repeated subtractions if we start from 0.)

Similarly, we can use direct recursion to approach the base case from below by repeated additions of 1, if we know that our starting point is less than or equal to that base case. Here's an example:

;;; count-from: given two natural numbers, construct a list of the
;;; natural numbers from the first to the second, inclusive, in ascending
;;; order

;;; Given:
;;;   LOWER and UPPER, both integers

;;; Result:
;;;   LS, a list.

;;; Precondition:
;;;   LOWER is less than or equal to UPPER.

;;; Postconditions:
;;;   (1) The length of LS is UPPER - LOWER + 1.
;;;   (2) For every natural number k less than or equal to the length of
;;;       LS, the element in position k of LS is LOWER + k.

(define count-from
  (lambda (lower upper)
    (if (= lower upper)
        (list upper)
        (cons lower (count-from (+ lower 1) upper)))))