How to detect an infinite loop in a recursive call?

Question

I have a function that calls itself recursively, and I want to detect and end if it goes into an infinite loop, i.e. causes the same problem again. What is the easiest way to do this?

EDIT: This is a function and it will be called recursively with different values ​​of x and y. I want to finish if the value of the pair (x, y) is repeated in a recursive call.

int fromPos(int [] arr, int x, int y) 

Answer 1

If the function is purely functional, that is, it has no state or side effects, then you can save the Set arguments (edit: when you see your editing, you will save the set of pairs (x, y)) with which it was called, and each time simply check if the current argument is in the set. This way you can detect a cycle if you run into it quite quickly. But if the argument space is large, and it takes a lot of time to repeat, you can run out of memory before you discover a loop. In general, of course, you cannot do this because it is a stopping problem.

Answer 2

One way is to pass the depth variable from one call to the next, increasing it every time your function calls itself. Make sure that depth does not grow beyond a certain 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; } 

Answer 3

You will need to find a job because, as you requested, there is no general solution. For more information, see Stop Problem .

Answer 4

A simple way would be to implement one of the following:

Pass the previous value and the new value to the recursive call and take the first step of checking to make sure they are the same - this is probably 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.

Answer 5

You can only find the most trivial using software analysis. The best you can do is add guards to your special circumstances and go through the context of the depth level. It is almost impossible to detect the general case and differentiate the legitimate use of recursive algorithms.

Answer 6

You can use overloading for a consistent signature (this is the best 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; } 

The answer to John Kugelman’s question with overload better imposes thread safety on him, but static variables do not.

Billy3

Answer 7

If you want to keep your method signature, you can save a couple of sets to write the old x and y values.

 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); } } 

Answer 8

It looks like you can work on a 2D array. If you have an extra bit to store the values ​​of the array, you can use it as a flag. Check it out and complete the recursion if the flag is set. Then install it before continuing.

If you don’t have a little extra value, you can always make it an array of objects.

Answer 9

IMHO Only loops can go into an infinite loop.

If your method has too many recursion levels, the JVM will throw a StackOverflowError. You can block this error with a try / catch block and do whatever you plan to do when this condition occurs.