Using goto to avoid stack overflows in deep function calls a good idea?

Question

I have an algorithm I need to implement, which jumps around it's code a lot, lot's of conditional check and skipping steps, going back to previous steps, and all that jazz.

It's probably implementable with loop and ifs, but it would be a huge mess which would be terribly hard to maintain and debug.

So than I though of writing each 'subsection' of the algorithm as a separate function and handling it like that, with all those functions calling each other. but this algorithm will be running a long time (it's for a NPcomplete problem, so yea...), so I'm pretty sure this will at some point result in a stack overflow.

So than the last option I could think of was using goto's. Now I always hear that once you start using goto's you should seriously reconsider your design, so that's why I'm asking if there's a better way to do this?

Oke here is the pseudo code:

As you can see it jumps around a and does lot's of check and conditional skips and stuff. I though about just adding the labels exactly as described in this pseudo code and using goto's exactly as described in the code. The alternative I was talking about with functions would be putting each of the point of the algorithm in a different function, but for reasons mentioned I do not think this is a good idea

Answer 1

This is exactly what tail recursion is for. It's goto disguised to look like a function call.

Use a language that has guaranteed semantics for tail calls, or a compiler with good tail recursion optimization for a language that doesn't.

For instance, suppose we have a state machine of this form:

{
  int state = S0       // main state variable
  int v1 = v1_initval, v2 = ..., ..., vn; // additional state variables

  while (state != S_ACCEPT) {
    switch (state) {
    case S0:
      // do whatever
      state = S5;
      break;
    case S2;
       ...
    case SN;
      ...
    }
  }
}

That can turn into tail recursion:

// case S0:
void S0(int v1, int v2, ..., int vn) {
  // do whatever
  S5(v1, v2, ..., vn);  // state = S5
}

The machine is started by a call to S0, which passes the correct initial values for the state variables. Then tail calls do the state transitions directly.

Under the tail call optimization, S5 call becomes an unconditional branch, and the argument passing is just assignment, which the compiler may be able to work out to a noop, since in the target function, the v1 parameter occupies the same storage location as the v1 argument in the caller.

Also, possible skeleton of an iterative state machine in C++:

class statemachine {
private:
  int sv1, sv2, ... , svn; // extra state variables
  void (statemachine::* state)(); // pointer-to-member: main state var

  void S0();
  void S1();
  // ...
  void S_ACCEPT();
public:
  statemachine();
  void run();
};

statemachine::statemachine()
: state(&statemachine::S0)  // initial state is S0
, sv1(...)                  // initializes for state vars
...
{
}

void statemachine::run()
{
   while (state != &statemachine::S_ACCEPT)
      (this->*state)();
}

void statemachine::S0()
{
   // modify state vars

   state = &statemachine::S5;
}

void statemachine::S_ACCEPT()
{
  abort(); // never called
}

You could almost make this look like recursion by adding a memer function which is called in order to set the next values of the member variables. The functions could end with this:

next(&statemachine::S42, v3, v1 + v2, ...);

where next is just a wrapper function that initializers the state variable and others from its arguments. So here, the next state will be S42, and v1 will take on the value of v3, v2 takes on v1 + v2 and so on.