Motivation & Examples

Some problems can most naturally be represented recursively. Note that any problem that can be represented recursively can also be done non-recursively. The non-recursive versions will be computationally faster, though often not as easy to understand.

Different types of Examples:

- Looking into a mirror, reflected in a mirror, or hooking up a camera to your monitor and then looking at your monitor through the camera, or recursive screenshots (from Brian Cichoracki)
- Escher's hands drawing each other,
- Bach's music, for instance this segment (1.4MB) from Contrapunctus I, played by Gould (excerpted from the site for a course at Stanford.  Also check out the images on that site.)
- See examples of the layout of an African Ba-ila settlement.
- The segments of the shell of a Chambered Nautilus
- Fractals images, where the image in the large is repeated in the small. The Hilbert Curve is one of many examples at this site (some shown above).
- Chess (if I move and then you move and then I move...)
- Line up people, all blindfolded, in a column, where the front-most person is next to the wall. Have the person at the back ask the person in front of them "How far am I from the wall?" That person in turn asks the next, and so forth. Finally the person who is next to the wall returns the answer "one", and that person returns "two," and so forth back to the original person who asked the question. (See a related YouTube video of the "Algorithm March", then see 967 inmates of (CPDRC) in the Philippines [Thanks to Maurizio Picicco for these.])
- Clapping Game (taken from http://www.can.ibm.com/k12/scitechmatics/recursion.html)
    Regular version: When I clap, I want you to raise your hands once.
    Recursive version: whenever you hear someone clap, raise your hands once then clap.
    What is the base condition? When does it stop? How could we make it stop?

Factorial Example

1. Non-recursive version of factorial:

   // Find the factorial of a non-negative integer x
   private int factorial( int x)
   
   {
   	int answer = 1;
   	for (int i=x; i>0; i--) {
   		answer = answer * i;
   
   	}
   
   	return answer;
   }

2. Recursive version of factorial:
   In an attempt to understand how recursion works, try tracing execution using both of the following:
   
   1. Write as multiple functions with different names, calling each other
   2. Write in outline form (compress the function body to make this easier to write)
   3. These two trace approaches are illustrated in this Word document.
      
3. Other examples, which include:
   1. A non-recursive method printReverse( ) that takes an input number and displays its digits in reverse order. Then the same thing done recursively in method recursivePrintReverse( ), which prints on the way in to the recursion ("head" recursion)
   2. Reversing text in method reverseText() by printing on the way back out of the recursive calls ("tail" recursion).
   3. Misc examples (methods f1( ) through f4( ), some of which implement various mathematical operators. Can you figure out what they do?

The Maze program

Consider the maze problem, where there is a rabbit in a maze. The solution could be developed in stages as follows (See also the MS Word handout used in class):

A representation using a 2-dimensional array, that only works for mazes where the solution can be found by always attempting first to move down, then right.

An attempt at solving the problem for any maze.
A different version where we change the maze representation from a 2-dimensional array to a one-dimensional array.

A version where we keep track of where we've been, so we avoid an infinite loop. A flag variable has also been added to mark when the end of the game has been reached.

A version that will display the solution path. A non-recursive version does this in reverse order, and a recursive version displays the solution in order.

[CS Dept] [UIC] [Prof. Reed]