11 Replies Latest reply: Jan 10, 2009 4:45 AM by 710081 RSS

    breaking out of a  recursion

    809475
      hello all,

      I have a recursive method in a java program.
      the main program contains a for loop which calls the recursive method for a certain number of times.

      the recursive method obviously calls itself. so I have stacks generated during the program execution.
      how can I end the recursive method when it has called itself more than once.
      and return back to the main program for the next iteration?

      program structure is something like this:
      private method (int, string){
      
          // some code
          //
      
          method (int, string) 
      
          // Say that I want to return to main() here
      }
      
      
      public main () {
      
          // some code
          //
          
          for (int i = 0; i <= somenum; i++) {
      
                  // some code
      
                  method (int, string) // i'll have different argument values for each call
          
         }
      }
      I know about System.exit(). But that stops the program execution.
      I need to keep the method running for the next "for" iteration.
      Also "return;" will pass program execution to the previous stack. which I don't want.

      Any Ideas/Suggestins??
        • 1. Re: breaking out of a  recursion
          796365
          Counters that you create and monitor?
          • 2. Re: breaking out of a  recursion
            798635
            vickywj wrote:
            how can I end the recursive method when it has called itself more than once.
            From your code sample, you have not convinced me that you need recursion. Just loop your code twice and get over it.
            • 3. Re: breaking out of a  recursion
              809475
              For example, the recursive method is searching in a tree.

              My method is such that it needs to stop as soon as it has found a result.
              • 4. Re: breaking out of a  recursion
                798635
                Well, in that case, a mere return would unwind the stack all the way down.
                • 5. Re: breaking out of a  recursion
                  809475
                  no it does not unwind all the way down.
                  it goes back to the previous stack.

                  More details for the method
                  public method (int, string, boolean) {
                  
                     // some code
                     // more code
                  
                     if (boolean == true) {
                         
                        // Point A
                        // here I want to close all stacks and return to main() at Point B
                     }
                  
                     method (int, string, boolean);
                  }
                  
                  public main () {
                  
                     // some code
                     // more code
                    
                     for (int i = 0 ......) {
                         method(int, string, boolean);
                     }
                     
                     // Point B
                  
                     // code block 1
                  
                  }
                  I am using System.exit() at Point A.
                  But that works for running "method" only once.

                  Moreover, the code block 1 never gets executed,
                  Since the program execution stops due to System.exit().

                  I hope this example helps to understand my problem.
                  • 6. Re: breaking out of a  recursion
                    798635
                    >
                    public method (int, string, boolean) {
                    
                    // some code
                    // more code
                    
                    if (boolean == true) {
                    
                    // Point A
                    // here I want to close all stacks and return to main() at Point B
                    }
                    
                    method (int, string, boolean);
                    }
                    <snip>
                    I hope this example helps to understand my problem.
                    No, not really. I still don't understand what is the problem. If you have a return statement at "Point A", it will return to the previous method() call. There's not a single statement after the call, so the stack will unwind accordingly.
                    • 7. Re: breaking out of a  recursion
                      807589
                      vickywj wrote:
                      For example, the recursive method is searching in a tree.

                      My method is such that it needs to stop as soon as it has found a result.
                      Your examples only show a single path of execution in your recursive method, so for the code you give you don't need anything more than a simple return.

                      If you are calculating something, then it's normal to return the result.
                      long fact (final int n, final long acc) {
                        if (n <= 1) return acc;
                        return fact(n - 1, acc * n); 
                      }
                      
                      long factorial (int n) {
                        return fact(n, 1);
                      }
                      If you are searching a tree, for example a binary tree, then a common pattern is to return a boolean value to indicate success, or return either the result or null if the search is for a value.
                      Node search (final Node parent, final Value value) {
                        // is this the node you want?
                        if (value.equals(parent.getValue()) return parent;
                      
                        // maybe it's on the left branch
                        final Node searchLeft = find(parent.getLeft(), value);
                      
                        if (searchLeft != null) return searchLeft;
                      
                        // otherwise it's on the right branch or nothing 
                        return search(parent.getRight(), value);
                      }
                      In both cases, the only thing the calling recursive function does with a successful result is to return it to its caller, so the stack unwinds.
                      • 8. Re: breaking out of a  recursion
                        710081
                        You can follow this approach:
                        private static int times = 0;
                        
                        int method(int arg)
                        {
                        lala if bla bla {
                         if (times == limit) break or exit
                        else times++
                         method(arg+1);
                        }
                        
                        }
                        • 9. Re: breaking out of a  recursion
                          809475
                          @remus, the number of recursive calls made are not constant.
                          So I am not sure if your code snippet will work all the times. Thank you very much though.

                          In my method, I pass the value of the boolean variable to the method and the next recursive call.
                          If It is true in any one of the calls, I need to exit the method closing all the stacks and return to main() at "Point B".
                          Since we have pass-by-value in java, the boolean variable is set to true on the topmost stack but not on the stacks below.
                          Hence the method continues with the stack below at "Point C" ( See the Method below )
                          I can break out of the method using System.exit at "Point A", But then the "for" loop in main() runs only for the first iteration
                          and "Code Block 2" in main() never gets executed.

                          public method (int, string, boolean) {
                           
                             // some code
                             // more code
                           
                             if (boolean == true) {
                                 
                                // Point A
                                // here I want to close all stacks and return to main() at Point B
                             }
                           
                             method (int, string, boolean);
                          
                             // Point C
                             // and some more code
                          
                          }
                          
                          public main() {
                          
                             // Code block 1
                          
                             for (int i = .....) {
                               method (int, string, boolean);
                             }
                          
                              // Point B
                             // Code block 2
                          }
                          I hope my problem is pretty clear.
                          I apologize I forgot to mention the "Point C" part in method earlier.

                          Yes. If the method call is the last statement in the recursive method, the stack will unwind naturally.
                          But it is not in my case. Hence the problem.

                          Is there a way to pass the boolean variable to the recursive method using pass-by-reference?
                          • 10. Re: breaking out of a  recursion
                            807589
                            You can't skip all the other stack frames. That wouldn't be recursion (except in the case of tail recursion which also isn't really skipping them, it doesn't create them in the first place, and IIRC Java doesn't even support it).

                            If you don't want the rest of the recursive function invoked, then have it check a return value:
                            boolean doSomething(SomeType val) {
                            
                              // do first thing (not shown)
                            
                              // do second, recursive thing
                              boolean result = doSomething(someOtherVal);
                              if (result)
                                return;
                            
                              // do third thing (not shown)
                              
                              return statusOfThisRecursiveCall;
                            }
                            Edited by: paulcw on Jan 10, 2009 5:20 PM
                            • 11. Re: breaking out of a  recursion
                              809475
                              thanks paul.

                              I modified my method according to your example.
                              and it works for now. Currently testing it with different test cases.

                              Thanks to all who posted in my thread.
                              Greatly appreciated.