Flat recursion is recursion in which each of the top-level elements of a list is operated on separately, as a unit, without recursive inspection of its internal structure (if any). (Flat recursion stands in contrast with deep recursion, in which the discovery that one of the top-level elements of a list A is itself a list B results in additional recursive calls that operate on the elements of B.)
Flatly recursive procedures tend to have a common structure: The body is
usually an if-expression in which the test determines whether
the base of the recursion has been reached (usually because the list
parameter has been reduced to the empty list or, occasionally, to a
single-element list), the consequent identifies or constructs the value to
be returned in that basic case, and the alternative is a procedure call
in which one of the operands is the car of the current list or
some lightly modified version of it and the other operand is a recursive
call in which the list argument is the cdr of the current
list. For example, here is a flat recursion that computes the sum of the
squares of the elements of a list of numbers:
(define sum-of-squares
(lambda (ls)
(if (null? ls)
0
(+ (square (car ls)) (sum-of-squares (cdr ls))))))
(define square
(lambda (x)
(* x x)))
Use trace-define to trace the workings of flat recursion in
sum-of-squares during the evaluation of the expression
(sum-of-squares '(12 5 17 9 6 10)).
Define an analogous procedure product-of-squares that returns
the product of the squares of the elements of the list.
In some cases, the nature of the car of the current list
determines which of two or more ways of operating on the result of the
recursive call will be used:
(define tally-symbols
(lambda (ls)
(cond ((null? ls) 0)
((symbol? (car ls)) (+ 1 (tally-symbols (cdr ls))))
(else (tally-symbols (cdr ls))))))
(In English: If ls is empty, it contains no symbols;
otherwise, if the car of ls is a symbol, then
ls contains one more symbol than its cdr does;
otherwise, it contains the same number of symbols as its cdr
does.)
Sometimes, recursion works on two or more lists, either taking their
elements up separately one by one (as in the merge procedure,
Program 4.3 on page 98 of the textbook) or traversing the lists in
parallel:
(define zipper
(lambda (first-list second-list)
(if (or (null? first-list)
(null? second-list))
'()
(cons (list (car first-list) (car second-list))
(zipper (cdr first-list) (cdr second-list))))))
Use trace-define to trace the evaluation of the procedure call
(zipper '(1 2 3 4 5) '(a b c d e)).
Describe, in your own words, what zipper does with its
arguments and how it constructs the value it returns.
What will happen if you give zipper two lists of different
lengths? Try the experiment and account for the result.
Add a precondition test to the definition of zipper that
calls error unless its arguments are lists of equal length.
Define a procedure zip3 that does for three lists what
zipper does for two lists.
A flat recursion used to define a predicate often takes the form of an
or-expression or an and-expression:
(define all-even?
(lambda (ls)
(or (null? ls)
(and (even? (car ls))
(all-even? (cdr ls))))))
(In English: A list of integers is ``all even'' if it is empty or if its
car is even and its cdr is all even.)
(define at-least-one-even?
(lambda (ls)
(and (not (null? ls))
(or (even? (car ls))
(at-least-one-even? (cdr ls))))))
(A list of integers contains at least one even number provided that (1) it
is not the empty list and (2) either its car is even or its
cdr contains at least one even number.)
Use trace-define to trace the sequence of recursive calls
during the evaluation of (at-least-one-even? '(3 9 17 1 26 19
5)). Why is the number of recursive calls less than the number of
elements of the list?
Define a predicate all-in-range? that takes a list of numbers
as its argument and returns #t if none of the elements is less
than zero or greater than 100, #f if it finds even one element
outside this range. Can you do this without using if or
cond?
This document is available on the World Wide Web as
http://www.math.grin.edu/courses/Scheme/spring-1998/flat-recursion.html
created September 22, 1997
last revised June 21, 1998