How to detect an infinite loop in a recursive call?

Question

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)

Answer 1

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

Answer 2

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.

Answer 3

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

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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.

Answer 8

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

Answer 9

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.