Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 9 of 9

Thread: Need Help making this non-recursive

  1. #1
    Forum VIP
    Join Date
    Jul 2010
    Posts
    1,697
    Thanks
    25
    Thanked 334 Times in 310 Posts

    Default 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.
    NOTE TO NEW PEOPLE LOOKING FOR HELP ON FORUM:

    When asking for help, please follow these guidelines to receive better and more prompt help:
    1. Put your code in Java Tags. To do this, put [highlight=java] before your code and [/highlight] after your code.
    2. Give full details of errors and provide us with as much information about the situation as possible.
    3. Give us an example of what the output should look like when done correctly.

    Join the Airline Management Simulation Game to manage your own airline against other users in a virtual recreation of the United States Airline Industry. For more details, visit: http://airlinegame.orgfree.com/


  2. #2
    Crazy Cat Lady KevinWorkman's Avatar
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    5,529
    My Mood
    Hungover
    Thanks
    144
    Thanked 647 Times in 552 Posts

    Default Re: Need Help making this non-recursive

    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
    Useful links: How to Ask Questions the Smart Way | Use Code Tags | Java Tutorials
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  3. #3
    Senior Member
    Join Date
    Jul 2013
    Location
    Europe
    Posts
    849
    Thanks
    0
    Thanked 158 Times in 141 Posts

    Default Re: Need Help making this non-recursive

    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
    Last edited by Cornix; September 4th, 2014 at 10:14 AM.

  4. #4
    Forum VIP
    Join Date
    Jul 2010
    Posts
    1,697
    Thanks
    25
    Thanked 334 Times in 310 Posts

    Default Re: Need Help making this non-recursive

    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.
    NOTE TO NEW PEOPLE LOOKING FOR HELP ON FORUM:

    When asking for help, please follow these guidelines to receive better and more prompt help:
    1. Put your code in Java Tags. To do this, put [highlight=java] before your code and [/highlight] after your code.
    2. Give full details of errors and provide us with as much information about the situation as possible.
    3. Give us an example of what the output should look like when done correctly.

    Join the Airline Management Simulation Game to manage your own airline against other users in a virtual recreation of the United States Airline Industry. For more details, visit: http://airlinegame.orgfree.com/

  5. #5
    Crazy Cat Lady KevinWorkman's Avatar
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    5,529
    My Mood
    Hungover
    Thanks
    144
    Thanked 647 Times in 552 Posts

    Default Re: Need Help making this non-recursive

    Quote Originally Posted by aussiemcgr View Post
    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.
    Useful links: How to Ask Questions the Smart Way | Use Code Tags | Java Tutorials
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  6. #6
    Forum VIP
    Join Date
    Jul 2010
    Posts
    1,697
    Thanks
    25
    Thanked 334 Times in 310 Posts

    Default Re: Need Help making this non-recursive

    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
    NOTE TO NEW PEOPLE LOOKING FOR HELP ON FORUM:

    When asking for help, please follow these guidelines to receive better and more prompt help:
    1. Put your code in Java Tags. To do this, put [highlight=java] before your code and [/highlight] after your code.
    2. Give full details of errors and provide us with as much information about the situation as possible.
    3. Give us an example of what the output should look like when done correctly.

    Join the Airline Management Simulation Game to manage your own airline against other users in a virtual recreation of the United States Airline Industry. For more details, visit: http://airlinegame.orgfree.com/

  7. #7
    Senior Member
    Join Date
    Jul 2013
    Location
    Europe
    Posts
    849
    Thanks
    0
    Thanked 158 Times in 141 Posts

    Default Re: Need Help making this non-recursive

    Yeah, I forgot that, but you got it right with your edited version.
    Of course the vertex needs to be set to visited before (or after) being added to the queue.

    Which queue to take is not an easy question to answer. I would say look whether you actually have a problem with the performance (which I doubt you will have unless you have hundreds of vertices) before thinking about the type of queue. A set will not do the trick because you might add the same vertex to the set twice if it has been removed from the set in between.

    First, you mentioned a part of my code looks like it should throw an exception. Why is that?
    Because your comment says:
    The bridge must be VERTICAL for directions NORTH or SOUTH of the start Island
    So when it isnt, but it must be, isnt that the perfect time to throw an exception?

  8. #8
    Forum VIP
    Join Date
    Jul 2010
    Posts
    1,697
    Thanks
    25
    Thanked 334 Times in 310 Posts

    Default Re: Need Help making this non-recursive

    Quote Originally Posted by Cornix View Post
    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.
    NOTE TO NEW PEOPLE LOOKING FOR HELP ON FORUM:

    When asking for help, please follow these guidelines to receive better and more prompt help:
    1. Put your code in Java Tags. To do this, put [highlight=java] before your code and [/highlight] after your code.
    2. Give full details of errors and provide us with as much information about the situation as possible.
    3. Give us an example of what the output should look like when done correctly.

    Join the Airline Management Simulation Game to manage your own airline against other users in a virtual recreation of the United States Airline Industry. For more details, visit: http://airlinegame.orgfree.com/

  9. #9
    Senior Member
    Join Date
    Jul 2013
    Location
    Europe
    Posts
    849
    Thanks
    0
    Thanked 158 Times in 141 Posts

    Default Re: Need Help making this non-recursive

    Well in that case you are of course right. I was just saying, if the comment suggests it should never happen it would be better to actually never let it happen.

Similar Threads

  1. Replies: 4
    Last Post: December 9th, 2013, 10:40 AM
  2. Recursive Maze Help
    By Deejay1992 in forum Java Theory & Questions
    Replies: 1
    Last Post: November 26th, 2012, 11:25 PM
  3. help with recursive method
    By mflb94 in forum What's Wrong With My Code?
    Replies: 1
    Last Post: September 27th, 2012, 07:30 PM
  4. Recursive Maze Help
    By chono in forum What's Wrong With My Code?
    Replies: 1
    Last Post: February 22nd, 2012, 08:02 PM
  5. [SOLVED] Recursive Methods ; StringIndexOutOfBoundsException
    By Medo Almasry in forum What's Wrong With My Code?
    Replies: 3
    Last Post: July 18th, 2011, 05:33 AM