How to evaluate the utility of recursive algorithms in Java?
Background:
I'm trying to learn algorithms and Java Run 320 × 320 grid, 100 trials, 5 times faster than non recursive quick union implementation However, more than about 400 × 400 (160000 sites) grid, I have a stack overflow error
I know Java is not optimized for tail recursion (let alone non - tail recursion) However, I think it is sometimes possible to choose a recursive algorithm over a non recursive version because it runs faster and is equally safe
Remember, I'm just learning these things, and my code may not be the best However, in order to better understand my problem, I include it
problem
What is the evaluation process when recursive algorithms can be safely used in Java applications (assuming that it runs faster than non recursive alternatives)?
Implementation of recursion and Alliance
(Note: 2x ratio is only the previous current running time divided by the previous running time)
|-----------|-----------|------------|-------------|-------------| | N | Recursive | Recursive | Quick-Union | Quick-Union | | (sites) | time | 2x Ratio | time | 2x Ratio | |===========|===========|============|=============|=============| | 196 | 35 | | 42 | | | 400 | 25 | 0.71 | 44 | 1.05 | | 784 | 45 | 1.80 | 46 | 1.05 | | 1600 | 107 | 2.38 | 86 | 1.87 | | 3136 | 48 | 0.45 | 113 | 1.31 | | 6400 | 75 | 1.56 | 303 | 2.68 | | 12769 | 183 | 2.44 | 858 | 2.83 | | 25600 | 479 | 2.62 | 2682 | 3.13 | | 51076 | 1253 | 2.62 | 8521 | 3.18 | | 102400 | 4730 | 3.77 | 27256 | 3.20 | |-----------|-----------|------------|-------------|-------------|
Review course
public class PercolateRecur implements Percolation {
// the site has been opened for percolation but is not connected
private final int OPEN = 0;
// the site is not open for percolation (default state)
private final int BLOCKED = -1;
// the matrix that will be percolated. Values default to `BLOCKED = -1`
// two sites that are connected together share the same value.
private int[][] matrix;
// the size of the sides of the matrix (1 to n)
private int size;
// whether water can flow from top to bottom of the matrix
private boolean percolated;
public PercolateRecur(int N) {
percolated = false;
size = N;
initMatrix();
}
/**
* initializes the matrix to default values
*/
private void initMatrix() {
matrix = new int[size+1][size+1];
// open up the top of the matrix
for (int x = 1; x < size+1; x++)
matrix[x][0] = x;
// set all values in matrix to closed
for (int x = 1; x < size+1; x++)
for (int y = 1; y < size+1; y++)
matrix[x][y] = BLOCKED;
}
/**
* indicates site (x,y) is a valid coordinate
* @param x x-portion of x/y coordinate
* @param y y-portion of x/y coordinate
* @return boolean
*/
private boolean isValid(int x,int y) {
return x > 0 && x < size+1 && y > 0 && y < size+1;
}
/**
* returns value of site above (x,y)
* @param x x-portion of x/y coordinate
* @param y y-portion of x/y coordinate
* @return int value
*/
private int above(int x,int y) {
if (y <= 0)
return BLOCKED;
else
return matrix[x][y-1];
}
/**
* returns value of site below (x,y)
* @param x x-portion of x/y coordinate
* @param y y-portion of x/y coordinate
* @return int value
*/
private int below(int x,int y) {
if (y >= size)
return BLOCKED;
else
return matrix[x][y+1];
}
/**
* returns value of site left of (x,y)
* @param x x-portion of x/y coordinate
* @param y y-portion of x/y coordinate
* @return int value
*/
private int left(int x,int y) {
if (x <= 0)
return BLOCKED;
return matrix[x-1][y];
}
/**
* returns value of site right of (x,y)
* @param x x-portion of x/y coordinate
* @param y y-portion of x/y coordinate
* @return int value
*/
private int right(int x,int y) {
if (x >= size)
return BLOCKED;
else
return matrix[x+1][y];
}
/**
* connects (x,y) to open adjacent sites
* @param x x-portion of x/y coordinate
* @param y y-portion of x/y coordinate
*/
private void connect(int x,int y) {
if (isFull(x,y))
return;
if (above(x,y) > OPEN)
matrix[x][y] = above(x,y);
else if (below(x,y) > OPEN)
matrix[x][y] = below(x,y);
else if (left(x,y) > OPEN)
matrix[x][y] = left(x,y);
else if (right(x,y) > OPEN)
matrix[x][y] = right(x,y);
else if (matrix[x][y] == BLOCKED)
matrix[x][y] = OPEN;
}
/**
* recursively connects open sites in same group as (x,y)
* @param x x-portion of x/y coordinate
* @param y y-portion of x/y coordinate
*/
private void expand(int x,int y) {
if (!isFull(x,y) == OPEN)
openWith(x,y-1,matrix[x][y]);
if (below(x,y+1,matrix[x][y]);
if (left(x,y) == OPEN)
openWith(x-1,y,matrix[x][y]);
if (right(x,y) == OPEN)
openWith(x+1,matrix[x][y]);
}
/**
* opens a site (x,y) on the matrix
* @param x x-portion of x/y coordinate
* @param y y-portion of x/y coordinate
*/
public void open(int x,int y) {
if (percolated || !isValid(x,y))
return;
connect(x,y);
expand(x,y);
}
/**
* opens a site with given value
* @param x x-portion of x/y coordinate
* @param y y-portion of x/y coordinate
* @param val value of point
*/
private void openWith(int x,int y,int val) {
matrix[x][y] = val;
open(x,y);
}
/**
* Returns whether site (x,y) is open
* @param x x-portion of x/y coordinate
* @param y y-portion of x/y coordinate
* @return true if not blocked
*/
public boolean isOpen(int x,int y) {
return matrix[x][y] > BLOCKED;
}
/**
* Returns whether site (x,y) is full (connected to the top)
* @param x x-portion of x/y coordinate
* @param y y-portion of x/y coordinate
* @return true if is full
*/
public boolean isFull(int x,int y) {
return matrix[x][y] > OPEN;
}
/**
* indicates whether site is blocked (not open)
* @param x x-portion of x/y coordinate
* @param y y-portion of x/y coordinate
* @return true if blocked
*/
public boolean isBlocked(int x,int y) {
return matrix[x][y] == BLOCKED;
}
/**
* indicates whether water can flow from top to bottom of matrix
* @return true if matrix is percolated
*/
public boolean percolates() {
for (int x = 1; x <= size; x++)
if (matrix[x][size] > OPEN)
percolated = true;
return percolated;
}
/**
* prints the matrix to the command line
*/
public void print() {
for (int y = 1; y < size+1; y++) {
System.out.println();
for (int x = 1; x < size+1; x++) {
if (matrix[x][y] == BLOCKED)
System.out.print("XX ");
else if (matrix[x][y] < 10)
System.out.print(matrix[x][y] + " ");
else
System.out.print(matrix[x][y] + " ");
}
}
System.out.println();
}
}
Solution
One problem with implementing recursive algorithms in Java is that the Java platform does not perform the standard tail call elimination optimization This means that deep recursion requires a deep stack Moreover, because the java thread stack does not "grow", this means that you are vulnerable to stack overflow
There are two solutions:
>Increase the thread stack size by using the - XSS option on the command line or by explicitly providing (larger) stack size in the thread constructor. > Explicit tail call elimination in Java code... At least ugly
In your case, the first solution will give you a measure of "true recursion" Second... Then the algorithm will no longer be really recursive, but this is what you can do to implement a recursive algorithm for "depth" problems in Java
Note: you can always convert a recursive algorithm in Java into an equivalent iterative algorithm that uses the "simulated stack" data structure to maintain the recursive state The algorithm complexity of the two versions should be the same Perhaps you should try this method and include the "simulation stack" variant as the third pair of columns in the evaluation