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 solvableFor this part of the book, the word “trivial” is a technical term; see Designing Algorithms. 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 non-trivial 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
data-driven 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—
The rest of this chapter is under development. Use HtDP/1e in the meantime.