Results 1 to 7 of 7

Thread: Break Recursion

  1. #1
    AMaineJR is offline Member
    Join Date
    May 2010
    Posts
    8
    Rep Power
    0

    Default Break Recursion

    Hey all. I'm not that new to Java, but it seems like a good topic for other beginners to learn as well. My question concerns recursive techniques for permutations. I lifted a code directly from a website (don't remember which) that permutes a string. My problem is, breaking out of the recursive function before it completes the cycle of all possibilities. I can use a public variable to store the value I am looking for, but the permutation continues until all possibilities are exhausted. How can I get out of the execution of that thread? Granted, I've tried break and returns, but it still seems to execute until the end.


    Java Code:
    	private void permuteString(String beginningString, String endingString) 
    	{
    		if (endingString.length() <= 1)
    		{
    			compareTo(beginningString + endingString);
    		}
    		else
    			for (int i = 0; i < endingString.length(); i++) 
    			{
    				try 
    				{
    					String newString = endingString.substring(0, i) + endingString.substring(i + 1);
    					permuteString(beginningString + endingString.charAt(i), newString);
    		        } 
    				catch (StringIndexOutOfBoundsException exception) 
    				{
    					exception.printStackTrace();
    		        }
    			}
    	}
    
    //will compare referenced string to an array and set the value to a position in a public array if they're equal
    	private void compareTo(String stringToCompare)
    	{
    		System.out.println(stringToCompare);
    	}
    I just hate using global variables, even though this is a one time use program, mainly for practice.

  2. #2
    Cruncher is offline Member
    Join Date
    Mar 2010
    Posts
    88
    Rep Power
    0

    Default

    Generally if a recursive method is void, the only way you can really get it to break is if you add a global variable. just when you've found what you wanted, change some boolean like endRecursion or something to true, and then at the top of the method check that, and if true, break;

  3. #3
    AMaineJR is offline Member
    Join Date
    May 2010
    Posts
    8
    Rep Power
    0

    Default

    But if you break out of a recursive function, wouldn't it return you to the previous call? For instance...

    Function
    --Function
    ----Function //found what i'm looking for.
    --Function //returned back to this point

    Which I guess with the global would be okay. I've already solved the problem I was looking at, using globals. I still had to look through every permutation, thus making it an inefficient algorithm. I guess encompassing the entire function from the first if statement in the permuteString function in a condition where one logical path would be the break, would be what you're suggesting? I can see that skipping that one recursion, returning to the previous and inevitably exiting the routine. Good call.

  4. #4
    Cruncher is offline Member
    Join Date
    Mar 2010
    Posts
    88
    Rep Power
    0

    Default

    right, even with void methods you still need to "return" forgot about that.
    But you could also put the check after the method call itself to return it, so as they return to the previous method (we don't call them functions in Java as far as i know) the next condition they reach is this one checking if we should still be doing our thing, and then will return out before it runs any code, and this should return out all of your methods. :)

    however, even putting it around the entire method SHOULD work too because the new ones that you call will ust get returned instantly, but i think putting the condition after the method comes back would be more efficient? possibly? recursion can be confusing.

  5. #5
    AMaineJR is offline Member
    Join Date
    May 2010
    Posts
    8
    Rep Power
    0

    Default

    Sounds good to me. I'm not familiar with optimizing code patterns. I figure either way, it's a conditional statement either during the loop or after. So it should be the same in the processor. The only optimizing I know of, is to set the most likely condition first, in a conditional statement.

    I forget about language specific jargon. I know a good bit of c++, java, javascript, php, basic, and sql. The only difference I know of in method and function, is that a method is a function used within a class. So, yeah, you are right. Java is always a class structure, so they'd always be methods. I forget these things sometimes. Forgive me.

  6. #6
    m00nchile is offline Senior Member
    Join Date
    Feb 2010
    Location
    Ljubljana, Slovenia
    Posts
    470
    Rep Power
    5

    Default

    Breaking out of recursion can be a bit annoying with cases like yours, where the recursive call is within a loop. Like it was said before, you'd need a global variable and check it in each loop iteration:
    Java Code:
    boolean finished = false;
    void recursive(some value) {
      if(base case) {
        finished = true;
        return;
      }
      for(...) {
        if(finished) return;
        recursive(new value);
      }
    }
    Ever seen a dog chase its tail? Now that's an infinite loop.

  7. #7
    AMaineJR is offline Member
    Join Date
    May 2010
    Posts
    8
    Rep Power
    0

    Default

    Thanks all. I solved it using the global condition test, almost code for code to what m00nchile posted. How do you mark the thread solved?

Similar Threads

  1. recursion and tail-recursion differences
    By OptimusPrime in forum New To Java
    Replies: 2
    Last Post: 12-28-2009, 07:26 PM
  2. Break to certain class
    By Arez in forum New To Java
    Replies: 4
    Last Post: 10-20-2008, 05:13 AM
  3. Break Clock
    By BruenorBH in forum Advanced Java
    Replies: 20
    Last Post: 09-12-2008, 06:27 AM
  4. How to use Break with a label
    By Java Tip in forum java.lang
    Replies: 0
    Last Post: 04-17-2008, 08:45 PM
  5. How to use Break
    By Java Tip in forum java.lang
    Replies: 0
    Last Post: 04-17-2008, 08:45 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •