Changing recursive method to iterative

Question

i have recrusive function which works fine. The problem is it gives stackoverflow error when the number of lines are huge. I want to put it in iterative, probably using a for loop. Need some help in doing it.

private TreeSet validate(int curLine, TreeSet errorSet) {
    int increment = 0;
    int nextLine = 0;

    if (curLine == lines.length || errorSet.size() != 0) {
        return errorSet;
    } else {
        String line = lines[curLine];

        //validation starts.  After validation, line is incremented as per the requirements

        increment = 1 //As per requirement. Depends on validation results of the line

        if (increment > 0) {
            try{
                Thread.currentThread().sleep(100);  
            }catch(Exception ex){
                System.out.println(ex); 
            }
            nextLine = (curLine + increment);
            validate(nextLine, errorSet);
        }
    }

    return errorSet;
}

Poster's description of the method:

The method does validates textlines, these lines has instructions of how much line has to be skipped, if the line is valid. So, if the line is valid that many of lines will be skipped using the increment. if the line is not valid increment will be 0.

You are calling `validate(nextLine, errorSet)` without saving its return value. Is this on purpose? Also, `if (increment > 0)` will always be true because of the line preceding it: `increment = 1`. It may be a good idea to explain what the method is supposed to do. — Chris Dargis, Jul 30 '12 at 16:12
increment will not be always > 0. if there are errors in the line, increment will be 0. — FirmView, Jul 30 '12 at 16:19
General methodology: [How to go from a recursion to an iteration?](http://stackoverflow.com/questions/159590/way-to-go-from-recursion-to-iteration). — assylias, Jul 30 '12 at 16:20
The method does validates textlines, these lines has instructions of how much line has to be skipped, if the line is valid. So, if the line is valid that many of lines will be skipped using the increment. if the line is not valid increment will be 0. — FirmView, Jul 30 '12 at 16:23

aaronburro · Accepted Answer · 2012-07-30T16:26:34.193

I'm not sure why this was ever recursive in the first place. This is perfectly suited for the use of a FOR loop. use something like so:

private TreeSet validate(int curLine, TreeSet errorSet) { 
   int increment = 0;

   if (errorSet.size() != 0)
      return errorSet;

   for (int curLine = 0; curLine < lines.Length; curLine += increment)
   {
      // put your processing logic in here


      // set the proper increment here.
   }
}

If the increment is always going to be 1, then you can just use curr++ instead of curLine += increment

score 1 · Answer 2 · answered Jul 30 '12 at 16:22

1

for(String line : lines) {
  // validate line here

  if(!errorSet.isEmpty()) {
    break;
  }
}

answered Jul 30 '12 at 16:22

jtahlborn

52,909
5
76
118

score 1 · Answer 3 · answered Jul 30 '12 at 17:01

The solution for your problem could be simple for loop or while, with logical expression for stop condition. Typically we use for loop when we have to pass through all elements of Iterable or array. In case when we are not aware how many loops we are going to do we use a while loop. Advantage of for loop over while, is that we for free have localized variables so we ca not use them out side of the loop, therefore we reduce possibility to have some bug.

You problem is that you have to break the program on two conditions:

When errorSet is not empty.
When the array of lines have no longer items.

As contradiction, we can say that your program should continue:

Until errorSet is empty,
and until line number is smaller than array size where they are stored.

This provide us to simply expression

errorSet.isEmpty()
lineNumber < lines.length()

We can combine them using logical operator && and use as a stop rule in for loop.

for(int lineNumber= 0; errorSet.isEmpty() && lineNumber< lines.length(); lineNumber++)  {

   //code to operate

}

Note:

Typically for logical expression is used operator &&, that assure that every part of the logical expression is evaluated. An alternative for this is &, that in case of false do not operate longer and return false. We could be tempted to use this operator for this expression but i would be bad idea. Because when we would traversed all lines without error code will generate IndexOutOfBoundException, if we switch the places then we would not have any optimization as first expression would be evaluated same number of times.

Changing recursive method to iterative

3 Answers3