In Scheme, it is not only possible, but commonplace, for a list to be an element of another list. One can have a list within a list within a list within a list, and so on -- there is no fixed upper bound on levels of nesting.

For instance, the list (((a b) c) d (e (f))) -- considered simply as a datum -- has three elements: ((a b) c), d, and (e (f)). The first of these elements is a list that has two elements: (a b) and c. The list (a b) has two elements, a and b. And so on.

If one were to count the symbols in the list (((a b) c) d (e (f))) using a flat recursion, one would find that only one of the elements of that list is a symbol:

(define count-top-level-symbols
  (lambda (ls)
    (cond ((null? ls) 0)
          ((symbol? (car ls)) (+ 1 (count-top-level-symbols (cdr ls))))
          (else (count-top-level-symbols (cdr ls))))))

> (count-top-level-symbols '(((a b) c) d (e (f))))
1

The flat recursion does not attempt to unpack the contents of any of the elements of ls as it examines them. Since ((a b) c) is not itself a symbol, it contributes nothing to the total computed by count-top-level-symbols.

Suppose, however, that we want to write a procedure that is able to determine that there are six symbols altogether within the datum (((a b) c) d (e (f))) -- a, b, c, d, e, and f. This is a job for deep recursion:

(define count-all-symbols
  (lambda (ls)
    (cond ((null? ls) 0)
          ((symbol? (car ls)) (+ 1 (count-all-symbols (cdr ls))))
          ((list? (car ls))
           (+ (count-all-symbols (car ls)) (count-all-symbols (cdr ls))))
          (else (count-all-symbols (cdr ls))))))

> (count-all-symbols '(((a b) c) d (e (f))))
6

Exercise 1

Define a procedure count-this-symbol that takes two arguments, the first a list and the second a symbol, and computes and returns the number of occurrences of the specified symbol anywhere inside the given list (including nested lists). (Hint: use count-all-symbols as a pattern.)

Exercise 2

Let's use the term ``tree of symbols'' for a datum like the one used in the preceding examples -- specifically, a non-empty list in which each element is either a symbol or another tree of symbols. Define a predicate tree-of-symbols? that takes one argument and returns #t if the argument is a tree of symbols, #f if it is not. (Such a predicate would be useful in adding a precondition test to count-this-symbol.)

Exercise 3

Define a procedure sum-all that takes a tree of numbers -- a non-empty list in which each element is either a number or another tree of numbers -- and determines the sum of all the numbers in the tree.

On page 101 of the textbook, the authors introduce the term nesting level for the number of nested lists within which a datum is enclosed. The depth of a tree of symbols is the maximum nesting level of any of the symbols that occur in it. Here is a procedure that computes the depth of a tree of symbols:

(define depth
  (lambda (tr)
    (cond ((null? tr) 0)
          ((symbol? (car tr)) (max 1 (depth (cdr tr))))
          ((list? (car tr)) (max (+ 1 (depth (car tr)))
                                 (depth (cdr tr))))
          (else 0))))

Exercise 4

What is the depth of the datum (((a b) c) d (e (f)))? Why?

Exercise 5

Give an example of a tree of symbols of depth 7. Have Scheme check your answer.

Exercise 6

Define a procedure depth-tally that takes two arguments, a tree of symbols tr and a positive integer level, and counts how many symbols occur inside tr at nesting level level exactly. (For example, in the tree of symbols (((a b) c) d (e (f))), the nesting level of the symbols c and e is 2, and the rest of the symbols have other nesting levels; so (depth-tally '(((a b) c) d (e (f))) 2) should yield 2.)

This document is available on the World Wide Web as

http://www.math.grin.edu/courses/Scheme/spring-1998/deep-recursion.html

created February 13, 1997
last revised June 21, 1998

Henry Walker (walker@math.grin.edu) and John David Stone (stone@math.grin.edu)