Stopping Backtracking

Question

Is there any way in C/C++ to stop a backtracking algorithm after finding the first solution without exiting the program.

I want my function to immediately exit the function,not to quit every level of recurrsion one by one stating return.

Answer 1

You could use setjmp()/longjmp() in both C and C++ for a crude but effective way of bypassing the need to pass a flag all the way back.

Answer 2

Without knowing exactly what you need, I would look at implementing your own stack, and avoid recursion completely. That way it becomes trivial to exit the backtracking tree (a single "return"), and it is also possible to resume the search to find the next solution by calling the function again, presuming the state of the user-defined stack is preserved (in static variables). Of course, there is a bit of programming overhead to convert a simple recursive program to a loop, but it's pretty straightforward to do.

Answer 3

A quick and dirty way is to throw an Exception and catch it at the base level (around right now a lot of people will scream to only use Exceptions for Errors, I argue, founding a solution is an exceptional event since not finding one is the norm)

Answer 4

if you have a flag that is set when you are done and then which is checked in your functions you could solve this. e.g.

void foo(..)
{
   if (g_done) return;
...
}

Answer 5

It actually depends on your implementation, but you could set some special param and use it as a flag like "Did we get a solution? If yes, then abort your current routine and get only that solution to the output".

Answer 6

Why do you want the function to immediately exit? Not backtracking through the stack is dangerous as you could have objects on it that need to be destroyed. Throwing an exception might due the trick for you, and it will cleanup the stack. Provide more information about what you are trying to do and we might be able to provide other approaches.

Answer 7

If your backtracking algorithm is actually recursing deep enough for this to matter, you shouldn't use recursion because you'll be in danger of blowing the stack. Rather than committing some atrocity involving longjmp, you should consider rewriting your algorithm to an iterative approach with your own heap-allocated stack which stores a POD object representing the state. When you find your solution the state container can be destroyed in one efficient step and the answer can be returned.

See Way to go from recursion to iteration

Answer 8

First, note that you can not do it for any recursive function. Consider the following code:

int SumNum(int nMax)
{
    if (0 == nMax)
        return 0;
    else
        return nMax + SumNum(nMax-1);
}

The actual value is calculated during the backtracking.

However, you can rewrite the code in the following way:

int SumNum(int nMax, int nSum)
{
    if (0 == nMax)
        return nSum;
    else
        return SumNum(nMax-1, nSum+nMax);
}

Now, you can do the following trick:

    int SumNum(int nMax, int nSum)
    {
        if (0 == nMax)
            throw nSum;
        else
            return SumNum(nMax-1, nSum+nMax);
    }


f()
{
        int nSum;

        try
        {
            SumNum(100, 0);
        }
        catch (int _nSum)
        {
            nSum= _nSum;
        }
}