Avoid recursion

Question

I have some code which uses recursion in its implementation. The profiler which I'm using doesn't do well with recursive function calls, so I'd like to rewrite it to be non-recursive.

The current code is something like this:

void Parse(Foo foo)
{
  A()
  for (;;)
  {
    B();
    if (C())
      return;
    if (D())
    {
      Run();
    }
    E();
  }
}

void Run()
{
  X();
  if (Y())
  {
    Parse();
  }
  Z();
}

The above is pseudo-code. The letters A, B, C, D, E, X, Y, and Z are methods, and so are Parse() and Run(). For simplicity I left out various parameters and object dereferences (e.g. Run is a method of an object instance, and it takes some parameters).

Anyway, my question is, how do I turn this into non-recursive code?

The equivalent non-recursive code seems to me to be:

void Parse(Foo foo)
{
  //create a local stack variable to emulate recursion
  Stack<Foo> foos = new Stack<Foo>();
  foos.Add(foo());
start_subroutine:
  A()
  for (;;)
  {
    B();
    if (C())
    {
      //instead of returning from a recursive call
      if (foos.Count > 1)
      {
        foo = foos.Pop();
        goto end_subroutine;
      }
      return;
    }
    if (D())
    {
      //instead of invoking Run as a subroutine, bring its functionality inline
      //Run();
      X();
      if (Y())
      {
        //instead of calling self recursively
        //Parse();
        //push onto a local stack variable and jump
        foos.Add(foo);
        goto start_subroutine;
      }
end_subroutine:
      Z();
    }
    E();
  }
}

I'm okay with doing this, but I don't see how to do it without using goto; and I don't remember ever seeing someone write that this is one of the cases when goto is necessary.

Answer 1

I think you're on the right track! I don't see any real problem using a goto in this case. It's really pretty clear what's going on in the code, and really the only reason people try to avoid direct jumping is that it can lead to confusion when reading someone else's code.

If you keep it structured this neatly and have most of your implementation code in other functions, this looks completely reasonable. Especially since you're only using the non-recursive code for profiling :)

Good luck however you end up proceeding!

Answer 2

I can't really test this, but it seems to me that you can replace goto start_subroutine with

A();
continue;

and goto end_subroutine with

Z();
E();
continue;

I'm not sure if that's really all that much better though :)