Can recursion be abandoned prematurely?

Question

My current recursive function works to some extent, but then crashes when it returns to 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 finds 0. Otherwise, it tries four different cardinal directions, which are another numbered room. Each time he makes a move, he adds the move made to the external array, and each time he returns, he removes that step from the stack.

My problem is that it has the correct path stored when it finds 0, but deletes it along the way back.

Is there a way to avoid this, for example, a gap.

No access or exceptions

Answer 1

There is a way out of recursion using exceptions, but I would not recommend it. Instead, change your function to return a bool that indicates whether you found 0 or not, and change your logic to return from the function without changing the path if 0 is found. Here is an 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; } 

Answer 2

exceptions (or C longjmp ) is a way to leave recursion. You may also have the static boolean leaveme; and run your function with if (leaveme) return; etc.

But longjmp does not work with value destructors in local frames (although there are exceptions).

Answer 3

Probably longjmp and setjmp : http://www.cplusplus.com/reference/clibrary/csetjmp/ . But I don't think it's nice to use longjmp and setjmp in C ++.

It is better to set some special return value, which, if detected by some depth, will immediately return, as in C.

Or a global flag indicating the state of the recursion, if this is true, we can do it, otherwise the recursion should return.

Answer 4

IN

//Escape the recursion!

I think you could just keep a copy of the "answer" on the field outside of recursion. If the function already changes the fields already outside the recursion, then perhaps make it a private helper function that contains an additional logical parameter that indicates whether you want to exit. A public function can simply call it, ignore the presence of such a parameter in the parameters.

Sort of:

 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;