1. Flat recursion.

;; The SUBSTITUTE procedure takes three arguments -- TEMPLATE (which must
;; be a list), OLD, and NEW -- and returns a list just like TEMPLATE
;; except that NEW has been substituted for every element of TEMPLATE
;; that is equal to OLD.

;; In this implementation, SUBSTITUTE itself is a husk; it confirms that
;; TEMPLATE is a list, then invokes SUBSTITUTE-KERNEL to carry out the
;; substitution recursively.

(define substitute
  (lambda (template old new)
    (if (not (list? template))
        (error 'substitute "the template must be a list"))
    (substitute-kernel template old new)))

;; SUBSTITUTE-KERNEL returns an empty list for an empty list; given a
;; non-empty list as the value of TEMPLATE, it examines the first element,
;; substituting NEW for it if it is equal to OLD, but otherwise leaving
;; it unchanged.  In either case, it prepends the selected value to the
;; result of the recursive call that performs the substitution on the
;; rest of TEMPLATE.

(define substitute-kernel
  (lambda (template old new)
    (cond ((null? template) '())
          ((equal? old (car template))
           (cons new (substitute-kernel (cdr template) old new)))
          (else
           (cons (car template)
                 (substitute-kernel (cdr template) old new))))))

2. Recursion on two lists.

;; The MAXIMIZE procedure takes two lists of real numbers as arguments,
;; compares the numbers that are in corresponding positions on the two
;; lists, and returns a single list containing, at each position, the
;; larger of the numbers compared for that position.  If the given lists
;; are of different lengths, the result is always be as long as the longer
;; of them, and the longer list provides the result value for any position
;; after the end of the shorter list.

;; In this implementation, MAXIMIZE is a husk; it confirms that its
;; arguments are both lists of real numbers, then invokes MAXIMIZE-KERNEL
;; to carry out the actual construction of the result list.

(define maximize
  (lambda (ls-1 ls-2)
    (if (or (not (list-of-reals? ls-1))
            (not (list-of-reals? ls-2)))
        (error 'maximize "both arguments must be lists of real numbers"))
    (maximize-kernel ls-1 ls-2)))

;; If either of the arguments to MAXIMIZE-KERNEL is an empty list, the
;; other argument is returned unchanged.  Otherwise, MAXIMIZE-KERNEL
;; compares the first element of one list to the first element of the
;; other.  Whichever is larger is prepended to the result of the recursive
;; call that compares elements in subsequent corresponding positions of the
;; lists.

(define maximize-kernel
  (lambda (ls-1 ls-2)
    (cond ((null? ls-1) ls-2)
          ((null? ls-2) ls-1)
          ((< (car ls-1) (car ls-2))
           (cons (car ls-2) (maximize-kernel (cdr ls-1) (cdr ls-2))))
          (else
           (cons (car ls-1) (maximize-kernel (cdr ls-1) (cdr ls-2)))))))

;; The LIST-OF-REALS? procedure takes any Scheme value and determines
;; whether it is a list of real numbers.  The empty list qualifies as a
;; list of real numbers; so does any pair in which the first element is
;; a real number and the rest of the list is itself a list of real numbers.

(define list-of-reals?
  (lambda (arg)
    (or (null? arg)
        (and (pair? arg)
             (real? (car arg))
             (list-of-reals? (cdr arg))))))

3. Mutual recursion.

;; The UP-SUM procedure takes a list of numbers as its argument.  If the
;; list is empty, it returns 0; otherwise, it adds the first element to the
;; ``down-sum'' (see below) of all of the other elements of the list.

;; The value that UP-SUM computes and returns is sometimes called the
;; ``alternating sum'' of the list.  Elements in the odd-numbered positions
;; in the list -- the first, the third, the fifth, and so on -- are added
;; into the alternating sum; elements in the even-numbered positions are
;; subtracted from it.  The DOWN-SUM procedure computes the negative of the
;; alternating sum of its argument.

;; In this implementation, UP-SUM is a husk; it confirms that its argument
;; is a list of numbers, then invokes UP-SUM-KERNEL to handle the actual
;; computation.

(define up-sum
  (lambda (ls)
    (if (not (list-of-numbers? ls))
        (error 'up-sum "the argument must be a list of numbers"))
    (up-sum-kernel ls)))

(define up-sum-kernel
  (lambda (ls)
    (if (null? ls)
        0
        (+ (down-sum-kernel (cdr ls)) (car ls)))))

;; The DOWN-SUM procedure also takes a list of numbers as its argument.
;; If the list is empty, it returns 0; otherwise, it subtracts the first
;; element from the ``up-sum'' (see above) of all of the other elements of
;; the list.

;; Like UP-SUM, DOWN-SUM is implemented as a husk that tests the
;; precondition and then invokes the appropriate kernel to carry out the
;; computation. 

(define down-sum
  (lambda (ls)
    (if (not (list-of-numbers? ls))
        (error 'down-sum "the argument must be a list of numbers"))
    (down-sum-kernel ls)))

(define down-sum-kernel
  (lambda (ls)
    (if (null? ls)
        0
        (- (up-sum-kernel (cdr ls)) (car ls)))))

;; The UP-SUM-KERNEL and DOWN-SUM-KERNEL procedures are mutually recursive;
;; each invokes the other to complete a recursive call.

;; The LIST-OF-NUMBERS? procedure takes any Scheme value and determines
;; whether it is a list of numbers.  The empty list qualifies as a list of
;; numbers; so does any pair in which the first element is a number and
;; the rest of the list is itself a list of numbers. 

(define list-of-numbers?
  (lambda (arg)
    (or (null? arg)
        (and (pair? arg)
             (number? (car arg))
             (list-of-numbers? (cdr arg))))))

This document is available on the World Wide Web as

http://www.math.grin.edu/courses/Scheme/spring-1997/solutions-1.html