20
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).