The functions we have developed so far fall into two broad categories. On one hand, we have the category of functions that encapsulate domain knowledge. On the other hand, we have functions that consume structured data. These functions typically decompose their arguments into their immediate structural components and then process those components. If one of the immediate components belongs to the same class of data as the input, the function is recursive. For that reason, we refer to these functions as (STRUCTURALLY) RECURSIVE FUNCTIONS. In some cases, however, we also need functions based on a different form of recursion, namely, generative recursion. The study of this form of recursion is as old as mathematics and is often called the study of ALGORITHMS.
The inputs of an algorithm represent a problem. Except for rare occasions, the problem is an instance of a large class of problems and the algorithm works for all of these problems. In general, an algorithm partitions a problem into other, smaller problems and solves those. For example, an algorithm for planning a vacation trip requires arrangements for a trip from our home to a nearby airport, a flight to an airport near our vacation spot, and a trip from that airport to our vacation hotel. The entire problem is solved by combining the solutions for these problems.
Designing an algorithm distinguishes two kinds of problems: those that are TRIVIALLY SOLVABLE^{54} and those that are not. If a given problem is trivially solvable, an algorithm produces the matching solution. For example, the problem of getting from our home to a nearby airport might be trivially solvable. We can drive there, take a cab, or ask a friend to drop us off. If not, the algorithm generates a new problem and solves those new problems. A multistage trip is an example of a problem that is nontrivial and can be solved by generating new, smaller problems. In a computational setting one of the smaller problems often belongs to the same class of problems as the original one, and it is for this reason that we call the approach GENERATIVE RECURSION.
In this part of the book, we study the design of algorithms, that is, functions based on generative recursion. From the description of the idea, we know that this process is much more of an ad hoc activity than the datadriven design of structurally recursive functions. Indeed, it is almost better to call it inventing an algorithm than designing one. Inventing an algorithm requires a new insight  a ``eureka.'' Sometimes very little insight is required. For example, solving a ``problem'' might just require the enumeration of a series of numbers. At other times, however, it may rely on a mathematical theorem concerning numbers. Or, it may exploit a series of mathematical results on systems of equations. To acquire a good understanding of the design process, it is necessary to study examples and to develop a sense for the various classes of examples. In practice, new complex algorithms are often developed by mathematicians and mathematical computer scientists; programmers, though, must throughly understand the underlying ideas so that they can invent the simple algorithms on their own and communicate with scientists about the others.
The two subsections illustrate two vastly different algorithms. The first one is an example of something programmers invent on a daily basis. The second one describes a fast sorting algorithm, one of the first applications of generative recursion in computing.
Terminology: Mathematical computer scientists often do not distinguish between structural recursion and generative recursion and refer to both kinds of functions as algorithms. Instead they use the terminology of RECURSIVE and ITERATIVE methods. The latter refers to a subclass of function definitions whose recursive function applications are in a particular position in the definition. We will strictly adhere to the terminology of algorithm and generative recursion when we work with this class of functions because this classification matches our thinking of design recipes better than the purely syntactic classification of applied mathematicians.
Let's consider the simplelooking problem of modeling the moves of a ball across a table. Assume the ball rolls at a constant speed until it drops off the table. We can model the table with a canvas of some fixed width and height. The ball is a disk that moves across the canvas, which we express with drawing the disk, waiting, and clearing it, until it is out of bounds.
Figure 66 collects the function, structure, data, and variable definitions that model the ball:
A ball is a structure with four fields: the current position and the
velocity in each direction. That is, the first two numbers in a
ball
structure are the current position on the canvas, and the
next two numbers describe how far the ball moves in the two directions per
step.
The function moveball
models the physical movement of the
ball. It consumes a ball and creates a new one, modeling one step.
The function drawandclear
draws the ball at its current
position, then waits for a short time, and clears it again.
The variable definitions specify the dimensions of the canvas and the delay time.
To move the ball a few times we can write
(define theball (makeball 10 20 5 +17)) (and (drawandclear theball) (and (drawandclear (moveball theball)) ...))
though this gets tedious after a while. We should instead develop a function that moves the ball until it is out of bounds.
The easy part is to define outofbounds?
, a function that
determines whether a given ball is still visible on the canvas:
;;outofbounds? : aball > boolean
;; to determine whetheraball
is outside of the bounds ;; domain knowledge, geometry (define (outofbounds? aball) (not (and (<= 0 (ballx aball) WIDTH) (<= 0 (bally aball) HEIGHT))))
We have defined numerous functions like outofbounds?
in the
first few sections of the book.
In contrast, writing a function that draws the ball on the canvas until it is out of bounds belongs to a group of programs that we haven't encountered thus far. Let's start with the basics of the function:
;; moveuntilout : aball > true
;; to model the movement of a ball until it goes out of bounds
(define (moveuntilout aball) ...)
Because the function consumes a ball and draws its movement on a canvas, it
produces true
like all other functions that draw onto a canvas.
Designing it with the recipe for structures makes no sense, however. After
all, it is already clear how to drawandclear
the ball and how to
move it, too. What is needed instead is a case distinction that checks
whether the ball is out of bounds or not.
Let us refine the function header with an appropriate condexpression:
(define (moveuntilout aball) (cond [(outofbounds? aball) ...] [else ...]))
We have already defined the function outofbounds?
because it was
clear from the problem description that ``being out of bounds'' was a
separate concept.
If the ball consumed by moveuntilout
is outside of the canvas's
boundaries, the function can produce true
, following the
contract. If the ball is still inside the boundaries, two things must
happen. First, the ball must be drawn and cleared from the canvas. Second,
the ball must be moved, and then we must do things all over again. This
implies that after moving the ball, we apply moveuntilout
again,
which means the function is recursive:
;; moveuntilout : aball > true
;; to model the movement of a ball until it goes out of bounds
(define (moveuntilout aball)
(cond
[(outofbounds? aball) true]
[else (and (drawandclear aball)
(moveuntilout (moveball aball)))]))
Both (drawandclear aball)
and (moveuntilout
(moveball aball))
produce true, and both expressions must be
evaluated. So we combine them with an andexpression.
We can now test the function as follows:
(start WIDTH HEIGHT) (moveuntilout (makeball 10 20 5 +17)) (stop)
This creates a canvas of proper size and a ball that moves left and down.
A close look at the function definition reveals two peculiarities. First,
although the function is recursive, its body consists of a
condexpression whose conditions have nothing to do with the input
data. Second, the recursive application in the body does not consume a part
of the input. Instead, moveuntilout
generates an entirely new
and different ball
structure, which represents the original ball
after one step, and uses it for the recursion. Clearly, none of our design
recipes could possibly produce such a definition. We have encountered a new
way of programming.
Exercise 25.1.1. What happens if we place the following three expressions
(start WIDTH HEIGHT) (moveuntilout (makeball 10 20 0 0)) (stop)
at the bottom of the Definitions window and click Execute? Does the second expression ever produce a value so that the third expression is evaluated and the canvas disappears? Could this happen with any of the functions designed according to our old recipes? Solution
Exercise 25.1.2.
Develop moveballs
. The function consumes a list of balls and
moves each one until all of them have moved out of bounds.
Hint: It is best to write this function using filter
,
andmap
, and similar abstract functions from
part IV.
Solution
Hoare's quicksort algorithm is the classic example of generative recursion
in computing. Like sort
in section 12.2,
qsort
is a function that consumes a list of numbers and
produces a version that contains the same numbers in ascending order. The
difference between the two functions is that sort
is based on
structural recursion
and qsort
is based on generative
recursion.
The underlying idea of the generative step is a timehonored strategy:
divide and conquer.
That is, we divide the nontrivial instances of the
problem into two smaller, related problems, solve those smaller problems,
and combine their solutions into a solution for the original problem. In
the case of qsort
, the intermediate goal is to divide the list
of numbers into two lists: one that contains all the items that are
strictly smaller than the first item, and another one with all those items
that are strictly larger than the first item. Then the two smaller lists
are sorted using the same procedure. Once the two lists are sorted, we
simply juxtapose the pieces. Owing to its special role, the first item on
the list is often called the pivot item.

To develop a better understanding of the process, let's walk through one step of the evaluation by hand. Suppose the input is
(list 11 8 14 7)
The pivot item is 11
. Partioning the list into items larger and
smaller than 11
produces two lists:
(list 8 7)
and
(list 14)
The second one is already sorted in ascending order; sorting the first one
produces (list 7 8)
. This leaves us with three pieces from the
original list:
(list 7 8)
, the sorted version of the list with the smaller numbers;
11
;
and
(list 14)
, the sorted version of the list with the larger
numbers.
To produce a sorted version of the original list, we concatenate the three
pieces, which yields the desired result: (list 7 8 11 14)
.
Our illustration leaves open how qsort
knows when to
stop. Since it is a function based on generative recursion, the general
answer is that it stops when the sorting problem has become
trivial. Clearly, empty
is one trivial input for
qsort
, because the only sorted version of it is
empty
. For now, this answer suffices; we will return to this
question in the next section.
Figure 67 provides a tabular overview of the entire sorting
process for (list 11 8 14 7)
. Each box has three compartments:
 
 

The top compartment shows the list that we wish to sort, and the bottommost contains the result. The three columns in the middle display the sorting process for the two partitions and the pivot item.
Exercise 25.2.1.
Simulate all qsort
steps for (list 11 9 2 18 12 14 4 1)
.
Solution
Now that we have a good understanding of the generative step, we can
translate the process description into Scheme. The description suggests that
qsort
distinguishes two cases. If the input is empty
,
it produces empty
. Otherwise, it performs a generative recursion.
This casesplit suggests a condexpression:
;;quicksort : (listof number) > (listof number)
;; to create a list of numbers with the same numbers as ;;alon
sorted in ascending order (define (quicksort alon) (cond [(empty? alon) empty] [else ...]))
The answer for the first case is given. For the second case, when
qsort
's input is nonempty
, the algorithm uses the
first item to partition the rest of the list into two sublists: a list with
all items smaller than the pivot item and another one with those larger
than the pivot item.
Since the rest of the list is of unknown size, we leave the task of
partitioning the list to two auxiliary functions: smalleritems
and largeritems
. They process the list and filter out those items
that are smaller and larger, respectively, than the first one. Hence each
auxiliary function accepts two arguments, namely, a list of numbers and a
number. Developing these functions is, of course, an exercise in structural
recursion;
their definitions are shown in figure 68.

Each sublist is sorted separately, using quicksort
. This implies
the use of recursion and, more specifically, the following two expressions:
(quicksort (smalleritems alon (first alon)))
,
which sorts the list of items smaller than the pivot; and
(quicksort (largeritems alon (first alon)))
,
which sorts the list of items larger than the pivot.
Once we get the sorted versions of the two lists, we need a function that
combines the two lists and the pivot item. Scheme's append
function accomplishes this:
(append (quicksort (smalleritems alon (first alon))) (list (first alon)) (quicksort (largeritems alon (first alon))))
Clearly, all items in list 1 are smaller than the pivot and the pivot is
smaller than all items in list 2, so the result is a sorted list.
Figure 68 contains the full function. It includes the
definition of quicksort
, smalleritems
, and
largeritems
.
Let's take a look at the beginning of a sample hand evaluation:
(quicksort (list 11 8 14 7)) = (append (quicksort (list 8 7)) (list 11) (quicksort (list 14)))
= (append (append (quicksort (list 7)) (list 8) (quicksort empty)) (list 11) (quicksort (list 14)))
= (append (append (append (quicksort empty) (list 7) (quicksort empty)) (list 8) (quicksort empty)) (list 11) (quicksort (list 14)))
= (append (append (append empty (list 7) empty) (list 8) empty) (list 11) (quicksort (list 14)))
= (append (append (list 7) (list 8) empty) (list 11) (quicksort (list 14))) = ...
The calculation shows the essential steps of the sorting process, that is,
the partitioning steps, the recursive sorting steps, and the concatenation
of the three parts. From this calculation, we can see that
quicksort
implements the process illustrated in
figure 67.
Exercise 25.2.2. Complete the above handevaluation.
The handevaluation of (quicksort (list 11 8 14 7))
suggests an
additional trivial case for quicksort
. Every time
quicksort
consumes a list of one item, it produces the very same
list. After all, the sorted version of a list of one item is the list
itself.
Modify the definition of quicksort
to take advantage of this
observation.
Handevaluate the same example again. How many steps does the extended algorithm save? Solution
Exercise 25.2.3.
While quicksort
quickly reduces the size of the problem in many
cases, it is inappropriately slow for small problems. Hence people often
use quicksort
to reduce the size of the problem and switch to a
different sort function when the list is small enough.
Develop a version of quicksort
that uses sort
from
section 12.2 if the length of the input is below some
threshold.
Solution
Exercise 25.2.4.
If the input to quicksort
contains the same number several times,
the algorithm returns a list that is strictly shorter than the input. Why?
Fix the problem so that the output is as long as the input.
Solution
Exercise 25.2.5.
Use the filter
function to define smalleritems
and
largeritems
as oneliners.
Solution
Exercise 25.2.6.
Develop a variant of quicksort
that uses only one comparison
function, say, <
. Its partitioning step divides the given list
alon
into a list that contains the items of alon
smaller
than (first alon)
and another one with those that are not smaller.
Use local
to combine the functions into a single function.
Then abstract the new version to consume a list and a comparison function:
;; generalquicksort : (X X > bool) (list X) > (list X)
(define (generalquicksort apredicate alist) ...)