last updated 2/28/07
There are a number of recursive algorithms used in manipulating data structures, in graphics processing and compiling, to name a few.
If the list is empty -> not found
If the first element contains what we're looking for -> found
Otherwise, search rest of list
private boolean isThere(LLStringNode temp, String item){ if (temp == null){ //end of list or empty return false; } else if (temp.getInfo().equals(item) ){ return true; } else { //search rest of list return isThere( temp.getLink(), item ); } }public boolean isThere(String item){ //helper function for user return isThere(head, item); }myList.isThere(item);
private void printFwd(LLStringNode temp){ if (temp != null){ System.out.println(temp.GetInfo()); printFwd( temp.getLink() ); } }public printFwd(){ printFwd(head); }myList.printFwd();private void printRev(ListNode temp){ if (temp != null){ printRev( temp.getLink() ); System.out.println(temp.getInfo()); } }
public printRev(){
printRev(head);
}
myList.printRev();
private boolean binarySearch (String item, int lo, int hi)
// Returns true if item is on this list, between lo and hi
// otherwise returns false.
{
if (lo> hi) // Base case 1
return false;
else
{
int midPoint;
int compareResult;
midPoint = (lo + hi) / 2;
compareResult = item.compareTo(list[midPoint]);
if (compareResult == 0) // item found
return true; // base case 2
else if (compareResult < 0)
// item is less than element at location
return binarySearch (item, lo, midPoint - 1);
else
// item is greater than element at location
return binarySearch (item, midPoint + 1, hi);
}
}
public boolean isThere (String item)
// Returns true if item is on this list, otherwise returns false.
{
return binarySearch(item, 0, numItems - 1);
}
The object of the game is to move the disks, one at a time, to the third peg. The catch is that a disk cannot be placed on top of one of that is smaller in diameter.
In general the solution is:
Now when you "recursively move n-1 disks from peg 1 to peg 2", use
peg 3 as the auxiliary peg.
Similary, when you "recursively move n-1 disks from peg 2 to peg 3",
use peg 1 as the auxiliary peg.
//----------------------------------------------------------------------------
// Towers.java by Dale/Joyce/Weems Chapter 4
//
// Driver class for doTowers method
// The number of circles is the first command line parameter.
// The output file name is the second command line parameter.
//----------------------------------------------------------------------------
import java.io.*;
public class Towers
{
private static PrintWriter outFile; // Output data file
public static void main(String[] args) throws IOException
{
// Prepare outputfile
String outFileName = args[1];
outFile = new PrintWriter(new FileWriter(outFileName));
// Get number of circles on starting peg
int circleCount;
circleCount = Integer.valueOf(args[0]).intValue();
outFile.println("OUTPUT WITH " + circleCount + " CIRCLES");
outFile.println("From original: ");
doTowers(circleCount, 1, 2, 3);
outFile.close();
}
public static void doTowers(
int circleCount, // Number of circles to move
int beginPeg, // Peg containing circles to move
int auxPeg, // Peg holding circles temporarily
int endPeg ) // Peg receiving circles being moved
// Moves are written on file outFile
// This recursive method moves circleCount circles from beginPeg
// to endPeg. All but one of the circles are moved from beginPeg
// to auxPeg, then the last circle is moved from beginPeg to
// endPeg, and then the circles are moved from auxPeg to endPeg.
// The subgoals of moving circles to and from auxPeg are what
// involve recursion
{
outFile.println("#circles: " + circleCount + " Begin: " +
beginPeg + " Auxil: " + auxPeg + " End: " + endPeg);
if (circleCount > 0)
{
// Move n - 1 circles from beginning peg to auxiliary peg
outFile.println("From first: ");
doTowers(circleCount - 1, beginPeg, endPeg, auxPeg);
outFile.println("Move circle from peg " + beginPeg
+ " to peg " + endPeg);
// Move n - 1 circles from auxiliary peg to ending peg
outFile.println("From Second: ");
doTowers(circleCount - 1, auxPeg, beginPeg, endPeg);
}
}
}
Many graphics applications need to set all pixels of a closed object to the same color or value. When a closed object can be any shape with convex and concave vertices, you need a way to efficiently find all the pixel coordinates that make up the inside of the shape.
For example, consider the 3 shapes in this 10x10 matrix
0 1 2 3 4 5 6 7 8 9 1 * * * * * * * * * * 2 * * * * 3 * * * * 4 * * * * * * * 5 * * * * * 6 * * * * * 7 * * * * * * * 8 * * * * 9 * * * * * * * * * *
public static void Fill( PixMatrix pixels, RowRange row,
ColRange col, Color paintColor )
{
if (pixels[row][col] == paintColor) //been there
return;
if (pixels[row][col] == BOUNDARY_COLOR) //at edge
return;
pixels[row][col] = paintColor;
//for each pixel...
if(row > TOP_ROW) //try to go up
Fill(pixels, row-1, col, paintColor);
if(col < RIGHT_COL) //try to go right
Fill(pixels, row, col+1, paintColor);
if(row < BOT_ROW) //try to go down
Fill(pixels, row+1, col, paintColor);
if(col > LEFT_COL) //try to go left
Fill(pixels, row, col-1, paintColor);
}
This is a variation on the maze solver.
A blob is a contiguous collection of X's.
Two X's in a grid are considered contiguous if they are beside each other horizontally or vertically. For example:
We can generate Blob Grids based on a percentage
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
{ //grid[i][j] = (rand.nextInt(100) < percentage);
randInt = rand.nextInt(100); // random number 0 .. 99
if (randInt < percentage)
grid[i][j] = true;
else
grid[i][j] = false;
}
----------- -X--X----X- X-X-XXX-XX- XXXXXXXXXXX ----------- X----X-X--- XXXXX-XXXXX XXXXXXXXXXX ----------- ---X-----XX XXXXX---XX- XXXXXXXXXXX ----------- XX-X-X--X-- ---X---XXX- XXXXXXXXXXX ----------- ------XX—X XX--X-XXXXX XXXXXXXXXXX Percentage 0 Percentage 33 Percentage 67 Percentage 100
int count = 0;
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
if (grid[i][j])
count++;
The problem with this code is that it counts the number of blob characters, not the number of blobs.
Whenever we encounter a blob character and count it, we must somehow mark all of the characters within that blob as having been counted.
To support this approach we create a "parallel" grid/matrix of type boolean called visited.
Let's assume we have a method called markBlob, that accepts as arguments the row and column indexes of a blob character, and proceeds to "mark" all the characters within that blob as having been visited. Then we can count the blobs using this code:
int count = 0;
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
if (grid[i][j] && !visited[i][j])
{
count++;
markBlob(i, j);
}
The markBlob method is passed the location of a blob character that needs to be marked, through its two arguments, row and col. It does that: visited[row][col] = true;
It must also mark all of the other characters in the blob. It checks the four locations "around" that location, to see if they need to be marked.
When should one of those locations be marked? There are three necessary conditions:
For example, the following code checks and marks the location above the indicated location (note the recursion):
if ((row - 1) >= 0) // if it's on the grid if (grid[row - 1][col]) // and has a blob character if (!visited[row - 1][col]) // and has not been visited markBlob(row - 1, col); // then mark it
The code for the remaining three directions (down, left, and right) is similar.
Graph and Tree traversal are simplified with recursion.
In graphs and trees, nodes are directly connected to, zero, one or more nodes. It's the multiple connections that is supported by recursion. The traversal algorithm pattern for unlimited number of children is as follows;
public void traverse(GraphNode node){
if(node == null) return;
//the following lines are needed for graphs but not trees
if(node.visited()) return; //been there
node.setVisited(); //mark this one now
// and we assume all nodes'.visited property was initialized to false
processNode(node); //this is the first visit
Iterator iter = new Iterator(getNode.children());
while(iter.hasNext()){
traverse((GraphNode) iter.next());
}
//note the processNode(node) could go here
}
See the Eight Queens problem as variation of this pattern.
Recursive Descent Parsing is a common technique in transforming programming language grammar rules into code that implements the syntactic analysis of a compiler.
Where you have recursion in the grammar rules, you will have recursion in the implementation. This is a good example of the use of indirect recursion. A major requirement is that the grammar rules must not have recursion at the beginning of the right hand side of the production. The algebraic expression grammar below is rewritten to eliminate the leading recursion.
In the following grammar
:= means "is defined as"
" " enclose literal items
[ ] enclose items which may be omitted
{ } enclose items which may appear zero or more times
| indicates a choice
( ) are used for grouping required choices
expression := term { addingOperator term }
term := factor { multiplyingOperator factor }
factor := number | "(" expression ")"
addingOperator := "+" | "-"
unaryAddingOperator := "+" | "-"
multiplyingOperator := "*" | "/" | "%"
number := digit { digit }
digit := "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
Tokens are the indivisible units of the language. Here the numbers can be multiple digits.
The scanner or tokenizer isolates the individual tokens (if they're not simple characters) but also classifies the token for use in the rest of the compiler. For example from a syntactic perspective + and - are considered adding operators and are treated identically. The digits of a number are collected together and combined/converted to its numeric value.
The scanner class skips whitespace and isolates the token. The token class does the classification and tracks this information.
Essentially the each grammar rule, assuming all alternatives for a non-token definition (left hand side) have been combined into one rule, defines a function. The tokens that make up the rule must be discovered by the function in the order given in the rule.
If there's repetition as with { and } then there's repetition in the function as well.
If there are choices in the rule, then the function must determine which alternative to pursue based on the next token in the input. If there's ambiguity in the rule at this point then you can't really use this technique.
The parser class defines the functions corresponding to the rules of the grammar.