Is there an easy way to push variables onto the stack for later retrieval

Question

I have a member function of an object that is typically used in an iterative manner but occasionally in a recursive manner. The function is basically following the path of a stream of water downhill, and under certain conditions the stream could split. In order to support the occasional recursion I have to push the state of the object onto the stack and pop it off afterwords. I'm currently doing this using local variables, but the code looks awful. I'd like to write PushState and PopState members but most of the implementations I've looked at aren't great. e.g. using a stack member in my object which ends up using the heap which is slow and leads to other issues. _alloca won't work as the stack frame is lost when the push function returns.

Are there any other reasonable generic ways of pushing and popping from the stack that i'm missing?

class CMyObject
{   
    enum Direction
    {
      left,right,branch,finished;
    }

    // state variables
    double m_XPos,m_YPos;

    void Navigate(double x,double y);
    Direction GoLeft();
    Direction GoLeft();
};

void    CMyObject::Navigate(double x,double y)
{
    m_XPos = x; m_YPos = y;

    Direction d = GoLeft(x,y);
    while(d != finished)
    {
     switch(d)
     {
      case left: d = GoLeft(); break;
      case right: d = GoRight(); break;
      case branch:
      {
       // push object state onto the stack
       double temp_x = m_XPos; double temp_y = m_YPos;
       Navigate(m_XPos,m_YPos);
       // pop object state from the stack
       m_XPos = temp_x; m_YPos = temp_x;
       GoRight();
      } break;
     }
    }
}

Answer 1

I guess the obvious way would be to create a copy of your entire object and the do the recursive call on that. This way, each branch has it's own state, and you compiler does the stack management for you. Basically, a method has to be reentrant in order to be safely used in recursion. That is not the case here, since your methods rely on a persistant state. So you have to copy that state, and that means copying the object.

UPDATE:

Some more links about recursion and reentrancy:

• this article is about reentrancy in emedded systems, but also explains the realtion to recursion
• Wikipedia on the subject
• another Article(pdf) by the author of the first one

Sadly, Donald Knuth has not yet finished the fourth part of his masterpiece, but when he does, read it, for it certainly clear that up.

Answer 2

I think you may need two objects - one that maintains position and any other state, and another which does the recursive navigation of an instance of the first object through the tree. In that way, the state of the navigated object will be restored when recursive calls in the navigator return.

Answer 3

How about something like this?

struct Restore {
    Restore(double& value) : m_value(value), m_initial(value) {}
    ~Restore() {m_value = value;}
    double& m_value;
    double m_initial;
};

and then:

{ //scope
    Restore r1(m_XPos), r2(m_YPos);
    Navigate(m_XPos,m_YPos);
} // m_XPos and m_YPos automatically restored when r1 and r2 goes out of scope