Thread: Need Help making this non-recursive

So I have some recursive code which works fine on my desktop, but when I use it in an android app and push the limits of it, I get a StackOverflow exception (I guess the stack in Android is smaller than on my desktop, which is why I'm only getting the problem on Android).

So, I need to figure out how to make this method non-recursive. The method itself is not too complex. I commented the code, so it can be more easily followed.
For reference: the Island and Bridge classes both extend the HashiSymbol class. Also, a Bridge can only exist between two Islands. A Bridge can exist in memory between two Islands, but not be visible to the user if the Bridge.getUserType() method returns a value less than 1. Islands are considered "connected" if a Bridge visibly exists between them.
Also: the getConnectingIslands() method must accept a start Island, due to it being used in situations other than the one shown below.

	public List<Island> getConnectingIslands(Island start) {
		List<Island> ret = new ArrayList<>();
		ret.add(start);
		// SymbolMode.FLOW is used to indicate that an Island has been visited
		start.setMode(SymbolMode.FLOW);
		/* This method retrieves a map of size 0 to 4, which represents the HashiSymbol
		 * immediately adjacent in each direction: NORTH, SOUTH, EAST, WEST
		 */
		Map<Direction,HashiSymbol> adjacent = Utilities.getAdjacentSymbols(this.puzzle, start.getLocation());
		// Loops through the map
		for(Direction dir : adjacent.keySet()) {
			// If the adjacent symbol is anything other than a bridge, we ignore it
			if(adjacent.get(dir) instanceof Bridge) {
				Bridge bridge = (Bridge)adjacent.get(dir); 
				// The bridge has to have a user type greater than 0 for it allow connections
				if(bridge.getUserType()<1) {
					continue;
				}
				// The bridge must be VERTICAL for directions NORTH or SOUTH of the start Island
				if(dir == Direction.NORTH || dir==Direction.SOUTH) {
					if(bridge.getUserDirection()!=BridgeDirection.VERTICAL) {
						continue;
					}
				}
				// The bridge must be HORIZONTAL for directions EAST or WEST of the start Island
				else {
					if(bridge.getUserDirection()!=BridgeDirection.HORIZONTAL) {
						continue;
					}
				}
				// Finds the Island object on the other end of the Bridge
				Island directionalIsland = getIslandInDirectionFrom(start,dir);
				// Checks if the Island has already been visited by seeing if its mode is FLOW
				if(directionalIsland.getMode()!=SymbolMode.FLOW) {
					// Makes the recursive call to add all the islands
					ret.addAll(getConnectingIslands(directionalIsland));
				}
			}
		}
		// Returns the created array of connected islands
		return ret;
	}
 
	/**
	 * @return {@code true} if the puzzle is solved, {@code false} if it is not
	 */
	public boolean isSolved() {
		// Two conditions need to be met before bother to even check
		if(!checkIslands() || Data.isTryMode()) {
			return false;
		}
		// Make the call to the recursive method
		List<Island> connectingIslands = getConnectingIslands(this.islands.get(0));
		// The puzzle is solved if the number of connecting island is equal to the number of total islands
		boolean isSolved = connectingIslands.size()==this.islands.size();
		// Reset mode values
		resetIslandMode(null);
		// Return true or false, depending on whether or not the puzzle is solved
		return isSolved;
	}

Does anyone have any design ideas for this? I can think of a few things, but none of them are particularly clean or fast.

That is kind-of a lot of code to go through (especially since it's not an MCVE), but you could try increasing the stack limit instead.

Googling got me here: stackoverflow - Android: Increase call stack size - Stack Overflow

This looks like a graph traversal algorithm, similar to pathfinding algorithms.
If this is the case then you could simply use the same mechanism used in pathfinding: put nodes of your graph into a queue and then poll queue elements as long as the queue is not empty.
You will probably need a way to mark them as visited to not generate an endless loop. But you already do that with your "SymbolMode" as far as I can tell.


By the way, this piece of code:

				// The bridge must be VERTICAL for directions NORTH or SOUTH of the start Island
				if(dir == Direction.NORTH || dir==Direction.SOUTH) {
					if(bridge.getUserDirection()!=BridgeDirection.VERTICAL) {
						continue;
					}
				}

looks suspiciously like not throwing an exception although an exception should be thrown.



By the way, here is your code in pseudo-code:

findConnected(v)
M := {v}				# Set of all connected nodes
visited(v) = true			# Whether a node was already visited or not
 
for w € adj(v) do			# For every adjacent node of v
    if not visited(w)
        M := M + findConnected(w)	# Add all elements of one set to the other
    end
end
 
return M

Making that iterative would look somewhat like this:

findConnected(v)
M := {v}				# Set of all connected nodes
visited(v) = true			# Whether a node was already visited or not
 
Q := {v}				# Queue is used instead of recursion
while size(Q) > 0 do			# While queue is not empty
	w := Q[0]			# Get first element in Queue
	Q := Q / {w}			# Remove that element from Queue
	M := M + w			# Add element to M
	for x € adj(w) do		# For each adjacent element
		if not visited(x)
			Q := Q + x	# Add element to queue if not visited
		end
	end
end
 
return M

Thanks Cornix. I'll definitely have a look into that.
It is basically a graph traversal/path finding algorithm. For reference, a HashiPuzzle just looks like this (http://www.anypuzzle.com/puzzles/log...xample-big.png) and the algorithm is supposed to determine if all the islands are connected.

Kevin, I'm reluctant to increase the stack because it seems like doing that would simply increase the limits of the program, instead of dealing with the root problem (ie: my algorithm can cause a stack overflow exception). The puzzle generator I have designed should be limited only by the physical memory the target system allows to it. The only way I even found this problem was by making it generate a puzzle with 2000 islands, which took me 2 days to solve. I've managed to do some creative things to ensure the performance of the puzzle is constant regardless of how large the puzzle is (no lag no matter how large the puzzle), but I wasn't anticipating a stack overflow exception for the final puzzle checking. Now, I do have a known issue where I don't actually check the amount of memory my program is allowed vs the amount of memory the puzzle requires, but that is because I have absolutely no way of knowing what those limits should be since I cannot accurately predict the amount of memory a puzzle will need. But I'm not too concerned, since it would take some insane user with unrealistic expectations to even try to generate a puzzle that large, which I consider relatively low-risk.

Originally Posted by aussiemcgr

The puzzle generator I have designed should be limited only by the physical memory the target system allows to it.

The stack size is also only limited by the available memory, so increasing the stack size only increases the amount of memory you use.

But I understand your point, so it's up to you. I just don't have much other help to offer without an MCVE. Good luck.

Cornix, a few questions.
First, you mentioned a part of my code looks like it should throw an exception. Why is that?
Second, I noticed something while implementing your sudo-code: the node is not being set to visited in the queue loop. Should it be like this instead (I starred what I changed):

findConnected(v)
M := {v}				# Set of all connected nodes
 
Q := {v}				# Queue is used instead of recursion
while size(Q) > 0 do			# While queue is not empty
	w := Q[0]			# Get first element in Queue
	Q := Q / {w}			# Remove that element from Queue
**	visited(w) = true		# Whether a node was already visited or not
	M := M + w			# Add element to M
	for x € adj(w) do		# For each adjacent element
		if not visited(x)
			Q := Q + x	# Add element to queue if not visited
		end
	end
end

Third, do you recommend a specific instance of Queue in this case? I implemented it with LinkedList, but I want to know if there is a better (performance wise) instance I should use. At first, I thought: what about a queue that prevents duplicates? But I think the tradeoff between the extra cost of checking uniqueness is not worth it. Instead, I put a check immediately after dequeuing which checks to see if the dequeued island has been visited. The specific concern I have is like this:

	A		B
C		D
	E		F
 
Q: A -> B,E
Q: B,E
Q: B -> A,F (A visited already)
Q: E,F
Q: E -> A,F (A visited already)
Q: F,F
Q: F -> B,E (B and E visited already)
Q: F
Q: F -> B,E (B and E visited already)
** F was checked twice since it wasn't set to visited

**Edit: Actually, I think I can deal with this by further modifying your sudo-code:

findConnected(v)
M := {v}				# Set of all connected nodes
visited(v) = true			# Whether a node was already visited or not
 
Q := {v}				# Queue is used instead of recursion
while size(Q) > 0 do			# While queue is not empty
	w := Q[0]			# Get first element in Queue
	Q := Q / {w}			# Remove that element from Queue	
	M := M + w			# Add element to M
	for x € adj(w) do		# For each adjacent element
		if not visited(x)
**			visited(x) = true	# Set to visited before adding to queue
			Q := Q + x	# Add element to queue if not visited
		end
	end
end

Originally Posted by Cornix

Because your comment says:

So when it isnt, but it must be, isnt that the perfect time to throw an exception?

Not necessarily. Those checks make sure the bridge adjacent to the Island is actually connected to the Island. For example, the different scenarios could be like this:
Scenario 1: Bridge connects A and B

A=B

Scenario 2: Bridge connects A and D, but that bridge does not connect B and C. However, the bridge that connects A and D is adjacent to B, so it will show up as an adjacent symbol. But, the bridge is South of B, which means if it connects to B, the bridge must be Vertical. Since the bridge is horizontal, it is not a connecting Bridge for B, so we ignore it in the algorithm.

 B
A=D
 C

So I am not throwing an exception, but instead just ignoring the symbol since it is irrelevant for the Island.