20

### Reading Assignment and Discussion Topics

Computer Science 111

*for class on Thursday April 13, 2000*

Please read section section 7.8 of the Schneider and Gersting text; it is relevant to today's class and to next week's lab. Be prepared to discuss the following:

In class one week ago (class 18) we talked about sorting
*recursively*. The idea was to define a sorting procedure in
terms of itself: to sort an array, just return immediately if the
array has size 1, otherwise sort the two halves of the array, merge
them together, and then return. All recursive programs have this
structure: they first check to see if their input is so small that
the answer is obvious, in which case they return immediately;
if not, then they call themselves on
smaller parts of the input and (usually) do some computation
(e.g., merge) when those calls return. This process can't go on
forever because each successive call has a smaller input, so
eventually you'll get to the tiny input with the obvious
answer. Recursion is the key concept in next week's lab.

If this is a hard idea for you, please try to write a recursive version of the *factorial* function. You remember that the definition of **fact(n)** is the product of all the integers from **1** to **n**. So the trivially small case is clearly **fact(1)**.

If this is not such a hard concept for you, please try to use the idea of recursion to describe the picture on the back of this sheet (or in this postscript file if you're reading this on-line).