A list that may have other lists as elements, which in turn may have still other lists as elements, and so on, is sometimes metaphorically called a tree. (The elements of the list are analogous to the branches of a tree, each of which may have branches of its own, and so on.) One way of thinking about deep recursion is to compare it to the process of climbing up one branch of a tree, or sometimes climbing around in it until one has inspected the leaves at the ends of all of the branches.
Here's a tree in which all of the leaves are strings:
(("The" ("busy" "clerk")) ("took" ("the" "key" ("to" ("the" "safe")))))
The tree structure is more apparent if one breaks out each list into its elements, with connecting lines:
(("The" ("busy" "clerk")) ("took" ("the" "key" ("to" ("the" "safe")))))
|
.----------------' `----------------.
| |
("The" ("busy" "clerk")) ("took" ("the" "key" ("to" ("the" "safe"))))
| |
.---------' `----. .---------------' `----------.
| | | |
"The" ("busy" "clerk") "took" ("the" "key" ("to" ("the" "safe")))
| |
.----' `----. .------.--------' `--.
| | | | |
"busy" "clerk" "the" "key" ("to" ("the" "safe"))
|
.-------' `--.
| |
"to" ("the" "safe")
|
.---' `--.
| |
"the" "safe"
In this case, the nested lists are supposed to indicate the syntactic structure of the sentence by grouping together words and phrases that are syntactically related (e.g., ``busy clerk'' is a syntactic unit, a phrase, while ``took the'' is not).
Here's a procedure that takes a tree with strings as leaves, like the one shown above, and returns a long string constructed by inserting a space between successive leaves. It assumes that the tree is not the empty list.
(define leaf-string
(lambda (tree)
(string-append (if (string? (car tree))
(car tree)
(leaf-string (car tree)))
(if (null? (cdr tree))
""
(string-append " " (leaf-string (cdr tree)))))))
Or in English: Separate tree into its car and its cdr. If the
car is itself a string, put that very string first; otherwise, call
leaf-string recursively to build the string to put first. If
the cdr is empty, put on a zero-character ``null string''; otherwise, add a
space, then call leaf-string recursively to build the rest of
the string. Use string-append to combine the string obtained
from the car with the string obtained from the cdr.
> (leaf-string '(("The" ("busy" "clerk"))
("took" ("the" "key" ("to" ("the" "safe"))))))
"The busy clerk took the key to the safe"
Adapt the leaf-string procedure so that it displays
the strings that occupy the leaves of the tree, separated from one another
by spaces.
Another common kind of operation on trees is leaf transformation -- preserving the structure of nested lists, but replacing each leaf with a transformed version of itself or with some derived datum. For example, one might replace every string in a tree of strings with its length:
> (convert-strings-to-lengths '(("The" ("busy" "clerk"))
("took" ("the" "key" ("to" ("the" "safe"))))))
((3 (4 5)) (4 (3 3 (2 (3 4)))))
Here's the definition of the procedure that performs this leaf transformation:
(define convert-strings-to-lengths
(lambda (tree)
(cons (if (string? (car tree))
(string-length (car tree))
(convert-strings-to-lengths (car tree)))
(if (null? (cdr tree))
'()
(convert-strings-to-lengths (cdr tree))))))
In English: Separate tree into its car and its cdr. If the
car is itself a string, obtain its length; otherwise, call
convert-strings-to-lengths recursively to build the structure
that will become the car of the result. Next, if the cdr is empty, use the
empty list as the cdr of the result; otherwise, otherwise, call
convert-strings-to-lengths recursively to build that
structure. Use cons to combine the value obtained for the car
with the value obtained for the cdr.
The strong similarity between leaf-string and
convert-strings-to-lengths indicates that they are instances
of another pattern, this one specifically for dealing with trees. The
effective definition of trees as a data structure (a non-empty list in
which the car is either a leaf value or a tree and the cdr is either the
empty list or a tree) is reflected in the pattern that these two procedures
share: Look at the car of the tree and operate on it directly if it is a
leaf value, or by a recursive call if it is a tree; then look at the cdr of
the tree and produce a fixed value if it is the empty list, or issue a
recursive call if it is a tree; finally, perform some appropriate operation
on the two results to construct the value to be returned.
Write and test a leaf-transformation procedure
increment-every-leaf that takes a tree of integers as its only
argument and returns a similarly structured tree in which each of the
leaves has been increased by 1:
> (increment-every-leaf '((3 (4 5)) (4 (3 3 (2 (3 4)))))) ((4 (5 6)) (5 (4 4 (3 (4 5))))) > (increment-every-leaf '(7)) '(8) > (increment-every-leaf '(79 -1 86 (-2 -3) 4)) (80 0 87 (-1 -2) 5)
The leaf-string procedure has a precondition: Its argument
must be a list containing at least one element, and each element must be
either a string or a list that meets the same precondition. Write and
test a predicate string-tree? that determines whether a given
object meets this condition.
> (string-tree? '())
#f
> (string-tree? '("This" "one" "is" "OK"))
#t
> (string-tree? '((("This" "one") ("is" "OK")) "too"))
#t
> (string-tree? '(("This" "one") ("is" ("just" (2 "bogus")))))
#f
> (string-tree? '(symbols not strings))
#f
Insert a precondition test in the definition of leaf-string
so that it will report an error if it is called with an argument that does
not meet the precondition. (To do this right, use two procedures -- husk
and kernel -- so that the precondition is checked only once, not on each
recursive call.)
Write and test a procedure to find the longest string in a tree of strings.
This document is available on the World Wide Web as
http://www.math.grin.edu/courses/Scheme/spring-1998/trees.html
created February 26, 1997
last revised June 21, 1998