Java Notes‎ > ‎

Recursion

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:

  1. 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 recursivescreenshots (from Brian Cichoracki)
  2. Escher's hands drawing each other, 
  3. 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.)
  4. See examples of the layout of an African Ba-ila settlement.
  5. Recursive smile video
  6. Nested Matryoshka dolls
  7. The segments of the shell of a Chambered Nautilus
  8. Stephen Hawking's 1988 book A Brief History of Time starts: "A well-known scientist (some say it was Bertrand Russell)... turtles...
  9. Fractals images, where the image in the large is repeated in the small. The Hilbert Curve can also be seen in 3D.
  10. Chess (if I move and then you move and then I move...)
  11. 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.
  12. See the "Algorithm March", then see 967 inmates of (CPDRC) in the Philippines [Thanks to Maurizio Picicco])
  13. Typing in a search for the word recursion in Google asks "Did you mean recursion?" [Thanks to Zach Quinn]
  14. See the YouTube video of "Dueling Carls" [Thanks to Brent Sonin]
  15.  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? 
  16. Consider a possible dictionary definition (from Wikipedia)
         Recursion - 
                If you still don't get it, see: "Recursion".

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):

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.

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.

Other Recursion Examples


[Several examples below modified from this site]

We can use recursion to generate all the anagrams of a word of any length.  See the program Anagrams.java.  Running this program would give something like:
Provide a word to anagram: cat
cat
cta
act
atc
tca
tac
On the first iteration we take the first character ('c') and display it with all the combinations of the following characters. Then we take the second character ('a') and display it followed by the combinations of its prefixes and suffixes. Similarly we repeat for the 3rd character ('t').


Recursion is useful when generating a fractal image, such as the Sierpinski gasket:
Sierpinski Gasket

First we create the large black background.  Then at each level of the recursion we display a white square in the center along with 8 smaller squares evenly spread around the sides.  To run this you will need Canvas.java, Square.java and SierpinskiDraw.java.
Č
ċ
ď
Anagrams.java
(1k)
Dale Reed,
Nov 14, 2011, 11:36 AM
ċ
ď
Canvas.java
(9k)
Dale Reed,
Nov 14, 2011, 11:36 AM
ċ
ď
SierpinskiDraw.java
(1k)
Dale Reed,
Nov 14, 2011, 11:36 AM
ċ
ď
Square.java
(5k)
Dale Reed,
Nov 14, 2011, 11:37 AM
Comments