20
for class on Thursday April 16, 1998
There is no reading for this class! But please 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 and merge them together. All recursive programs have this structure; they first check to see if their input is so small that the answer is obvious, and 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.
If this is a hard concept for you, please 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 write a recursive version of Euclid's algorithm. Your function should, of course, have two (integer) inputs and return one (integer) value.
Finally, if this is an easy and/or intriguing concept for you, try writing a recursive version of binary search. You should search for an integer input in a sorted array of integers. Assume that it's in there somewhere, and only in one spot. Your function will have the following inputs: the array, the number to be searched for, and two indexes indicating the portion of the array to be searched. It will have one output: the index of the number you're searching for. The first call to your function will have the left and right indexes set to 0 and n-1.
During this class we will discuss your programs, and perhaps try to find a recursive solution to the Towers of Hanoi puzzle. Recursion is the key concept in next week's lab.