Background: Have you ever seen a picture of a person looking into a mirror, when there is also a mirror on the other side? The mirrors reflect one another and there appears to be an infinite hallway of mirrors. This happens because a mirror is reflecting a mirror, which is reflecting a mirror, which is, ... well, you get the idea.
Recursion is the process of defining an element in a succession based on the prior elements in the sequence. In other words, something is defined recursively when it is defined in terms of itself. In the mirror example, the reflection of one mirror includes the reflection of the second mirror, which includes the reflection of the first. It is easy to see how recursion and infinity are related. If something is defined in terms of itself, the definition forms a kind of circle that could go on forever, as in the mirror example.
In computer science, we speak of recursive algorithms and infinite data structures. There are times when a process or data structure includes the same thing, on a smaller scale. Perhaps the most common example is the factorial function, in which x factorial is defined as x times (x-1) factorial. In order for such algorithms to work, however, there must be some stopping point. For example, when computing factorial, we define 1 factorial as 1, and there is no need to recurse further. Without this base case, the process would go on until the computer ran out of memory and returned an error. In order to be sure that the algorithm ends, we must be sure that the recursive part of the algorithm approaches the base case.
Tasks: In this lab, you will write some recursive algorithms. You will experiment with infinite data structures and see how recursion can make a long, difficult algorithm easy.
Objectives:
Legend has it that in an ancient city in India, monks in a temple have to move a pile of 64 sacred disks from one location to another. The disks are fragile; only one can be carried at a time. A disk may not be placed on top of a smaller, less valuable disk. And, there is only one other location in the temple (besides the original and destination locations) sacred enough that a pile of disks can be placed there.
So, the monks start moving disks back and forth, between the original pile, the pile at the new location, and the intermediate location, always keeping the piles in order (largest on the bottom, smallest on the top). The legend is that, before the monks make the final move to complete the new pile in the new location, the temple will turn to dust and the world will end. Is there any truth to this legend?
There's a game based on this legend. You have a small collection of disks and three piles into which you can put them (in the physical version of this game, you have three posts onto which you can put the disks, which have holes in the center). The disks all start on the leftmost pile, and you want to move them to the rightmost pile, never putting a disk on top of a smaller one. The middle pile for intermediate storage.
Multiple-Choice Programming:
Actions:
move_disk(integer, integer) Removes one disk from whose number is the first argument, and put on the tower whose number is the second argument. For example, move_disk(1,3) moves a disk from tower 1 and puts it on tower 3.
Checks:
is_odd(integer) -> true/false
Problem 1: Move 3 disks from tower 1 to tower 3.
Problem 2: Move 4 disks from tower 1 to tower 3.
Problem 3: Move x disks from tower 1 to tower 3.
Problem 4: Move x disks from tower 1 to tower y.
Problem 5: If not done already, solve problem 4 recursively.
Questions:
Technical:
Technically, any recursive algorithm can be written using a loop. The
following algorithm takes a String and reverses it. The String function
substring(1) returns the String without the first letter. The function
charAt(0) returns the first letter in the String. For example, if the
String str is "example", str.substring(1) returns "xample",
and str.charAt(0) returns "e".
reverse(String s){
if (s.equals(""))
return "";
return reverse(s.substring(1)) + s.charAt(0);
}
First, assume that the algorithm works and explain how the algorithm works. Then, rewrite the algorithm using a loop and no recursion.
Theoretical:
The following is a definition of the function half(x). It takes a real
number and returns the real number divided by two.
half(real x){
return half(x-1) + .5;
}
Is this algorithm theoretically correct? (That is, is x/2 = (x-1)/2 + .5?) Is it practically correct? (That is, can it run on the computer?) Explain your answers. If the algorithm is not practically correct, rewrite it to be correct.
Virtual:
If every recursive algorithm can be written using loops, why learn or use
recursion? (Hint: the correct answer is one that argues that recursion is
useful!)
Social:
Many of our relationships are defined recursively. For example, one could
say that my enemy is my friend's enemy. Can you define these relationships
recursively? If not, provide a different example.
Philo-ethical:
Artists sometimes use infinite or recursive pictures to evoke certain
emotions. The following are pictures done by M.C. Escher, known for such a
technique. Do you have any emotional response to any of these
pictures?
