CODEWITHSUNDEEP
c++recursion
Joshua
Joshua

Reputation: 4320

Possible to leave recursion prematurely?

My current recursive function works to a degree, but then ruins itself when it goes back down the stack.

void Graph::findPath( Room * curRoom )
{
if( curRoom -> myNumber == 0 )
{
    cout << "Outside.\n";
    //Escape the recursion!
}
else
{
    curRoom -> visited = true;

    if( curRoom -> North -> visited == false )
    {   

        escapePath[ _index ] = "North";
        cout << "_index: " << _index << "\n";
        ++_index;

        findPath( curRoom -> North );

        cout << "_index: " << _index << "\n";
        escapePath[ _index ] = "";
        --_index;
    }

    if( curRoom -> East -> visited == false )
    {   
        escapePath[ _index ] = "East";
        cout << "_index: " << _index << "\n";
        ++_index;

        findPath( curRoom -> East );

        cout << "_index: " << _index << "\n";
        escapePath[ _index ] = "";
        --_index;
    }

    if( curRoom -> South -> visited == false )
    {   
        escapePath[ _index ] = "South";
        cout << "_index: " << _index << "\n";
        ++_index;

        findPath( curRoom -> South );

        cout << "_index: " << _index << "\n";
        escapePath[ _index ] = "";
        --_index;
    }

    if( curRoom -> West -> visited == false )
    {   
        escapePath[ _index ] = "West";
        cout << "_index: " << _index << "\n";
        ++_index;

        findPath( curRoom -> West );

        cout << "_index: " << _index << "\n";
        escapePath[ _index ] = "";
        --_index;
    }
}
}

To save you some reading, the idea is that the base case is finding 0. Otherwise it tries four different cardinal directions, which is a different numbered room. Every time it makes a move, it adds the move it made to an external array, and every time it comes back up it removes that step from the stack.

My issue is that it has the correct path stored when it finds the 0, but removes it on the way back up.

Is there a way to escape it, such as a break.

No gotos or exceptions

Upvotes: 8

Views: 24590

Answers (5)

kiragami
kiragami

Reputation: 1

bool flag = true;
int recursionFunction(parameters){
    if(flag){
        //do whatevere you wanna do

        if(condition satisfied){
            bool = false;
        }
    }
    else{
        return (whatever you want to return);
    }
}

Upvotes: 0

Basile Starynkevitch
Basile Starynkevitch

Reputation: 1

exceptions (or the C longjmp) are the way to leave a recursion. You might also have a static boolean leaveme; flag and start your function with if (leaveme) return; etc.

But longjmp don't work nicely with destructors of values in local frames (while exceptions do).

Upvotes: 0

vitaut
vitaut

Reputation: 55544

There is a way to exit recursion using exceptions, but I wouldn't recommend it. Instead, modify your function to return a bool that indicates whether you've found 0 or not and modify your logic to return from the function without changing path if 0 has been found. Here's the illustration of the idea:

bool Graph::findPath( Room * curRoom )
{
    if( curRoom -> myNumber == 0 )
    {
        cout << "Outside.\n";
        //Escape the recursion!
        return true;
    }
    // ...
    if (findPath( curRoom -> North ))
        return true;
    // ...
    return false;
}

Upvotes: 22

Just a guy
Just a guy

Reputation: 76

At

//Escape the recursion!

I think you could just save a copy of the "answer" to a field outside your recursion. If the function is already modifying fields already outside the recursion, then perhaps make this a private helper function which contains an additional boolean parameter that flags whether you want to exit. The public function can simply call this one, to abstract away from having a flag like that in the parameters.

Something like:

void Graph::findPath( Room * curRoom, bool done )

//Escape the recursion!
done = true;

findPath( curRoom -> North );

if (done) // new line here
    return;

cout << "_index: " << _index << "\n";
escapePath[ _index ] = "";
--_index;

Upvotes: 0

phoxis
phoxis

Reputation: 61910

Probably longjmp and setjmp : http://www.cplusplus.com/reference/clibrary/csetjmp/ . But i do not think it is a good idea to use longjmp and setjmp in C++ .

Better is to set some special return value, which if detected by some depth will immediately return, like in C.

Or a global flag indicating the state of the recursion, if true we can do, else the recursion should return.

Upvotes: 0

Related Questions