CODEWITHSUNDEEP
javarecursion
FirmView
FirmView

Reputation: 3150

Changing recursive method to iterative

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.

Upvotes: 0

Views: 150

Answers (3)

Damian Leszczyński - Vash
Damian Leszczyński - Vash

Reputation: 30865

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:

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

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

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

This provide us to simply expression

  1. errorSet.isEmpty()
  2. 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.

Upvotes: 1

aaronburro
aaronburro

Reputation: 554

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

Upvotes: 2

jtahlborn
jtahlborn

Reputation: 53694

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

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

Upvotes: 1

Related Questions