I have a function that is recursively calling itself, and i want to detect and terminate if goes into an infinite loop, i.e - getting called for the same problem again. What is the easiest way to do that?
EDIT: This is the function, and it will get called recursively with different values of x and y. i want to terminate if in a recursive call, the value of the pair (x,y) is repeated.
int fromPos(int [] arr, int x, int y) One way is to pass a depth variable from one call to the next, incrementing it each time your function calls itself. Check that depth doesn't grow larger than some particular threshold. Example:
int fromPos(int [] arr, int x, int y) { return fromPos(arr, x, y, 0); } int fromPos(int [] arr, int x, int y, int depth) { assert(depth < 10000); // Do stuff if (condition) return fromPos(arr, x+1, y+1, depth + 1); else return 0; } 
If the function is purely functional, i.e. it has no state or side effects, then you could keep a Set of the arguments (edit: seeing your edit, you would keep a Set of pairs of (x,y) ) that it has been called with, and every time just check if the current argument is in the set. That way, you can detect a cycle if you run into it pretty quickly. But if the argument space is big and it takes a long time to get to a repeat, you may run out of your memory before you detect a cycle. In general, of course, you can't do it because this is the halting problem.
You will need to find a work-around, because as you've asked it, there is no general solution. See the Halting problem for more info.
An easy way would be to implement one of the following:
Pass the previous value and the new value to the recursive call and make your first step a check to see if they're the same - this is possibly your recursive case.
Pass a variable to indicate the number of times the function has been called, and arbitrarily limit the number of times it can be called.
You can only detect the most trivial ones using program analysis. The best you can do is to add guards in your particular circumstance and pass a depth level context. It is nearly impossible to detect the general case and differentiate legitimate use of recursive algorithms.
You can either use overloading for a consistent signature (this is the better method), or you can use a static variable:
int someFunc(int foo) { static recursionDepth = 0; recursionDepth++; if (recursionDepth > 10000) { recurisonDepth = 0; return -1; } if (foo < 1000) someFunc(foo + 3); recursionDepth = 0; return foo; } John Kugelman's answer with overloading is better beacuse it's thread safe, while static variables are not.
Billy3
Looks like you might be working on a 2D array. If you've got an extra bit to spare in the values of the array, you can use it as a flag. Check it, and terminate the recursion if the flag has been set. Then set it before continuing on.
If you don't have a bit to spare in the values, you can always make it an array of objects instead.
If you want to keep your method signature, you could keep a couple of sets to record old values of x and y.
static Set<Integer> xs; static Set<Integer> ys;//Initialize this! static int n=0;//keeps the count function calls. int fromPos(int [] arr, int x, int y){ int newX= getX(x); int newY= getY(y); n++; if ((!xs.add(Integer.valueOf(newX)) && !ys.add(Integer.valueOf(newY))){ assert(n<threshold); //threshold defined elsewhere. fromPos(arr,newx,newy); } } IMHO Only loops can go into an infinite loop.
If your method has too many level of recursion the JVM will throw a StackOverflowError. You can trap this error with a try/catch block and do whatever you plan to do when this condition occurs.
A recursive function terminates in case a condition is fulfilled.
Examples:
0 or is 1In your case the condition is ([x0,y0] == [xN,yN]) OR ([x1,y1] == [xN,yN]) OR ([xN-1,yN-1] == [xN,yN])
0, 1, ...N are the indexes of the pairs
Thus you need a container(vector, list, map) to store all previous pairs and compare them to the current pair.
First use mvn findbugs:gui to open a gui which point to the line where this error is present.
I also faced the same problem and I solved it by adding a boolean variable in the loop verification.
Code before ->
for (local = 0; local < heightOfDiv; local = local + 200) { // Line under Error tileInfo = appender.append(tileInfo).append(local).toString(); while (true) { try { tileInfo = appender.append(tileInfo).append(getTheTextOfTheElement(getTheXpathOfTile(incr))).toString(); incr++; } catch (Exception e) { incr = 1; tileInfo = appender.append(tileInfo).append("/n").toString(); } } To Solve this problem, I just added a boolean variable and set it to false in the catch block. Check it down
for (local = 0; local < heightOfDiv; local = local + 200) { tileInfo = appender.append(tileInfo).append(local).toString(); boolean terminationStatus = true; while (terminationStatus) { try { tileInfo = appender.append(tileInfo).append(getTheTextOfTheElement(getTheXpathOfTile(incr))).toString(); incr++; } catch (Exception e) { incr = 1; tileInfo = appender.append(tileInfo).append("/n").toString(); terminationStatus = false; } } This is how i Solved this problem. Hope this will help. :)
