You only have one recursive call in findNext
and it is return findNext(...)
so the so-called tail-call optimization can be applied. Your compiler might do it at -O3. But if you don't trust the compiler to do this, you can do it by hand. Below is the transformed function, no longer recursive:
bool findNext(const voronoi_diagram::cell_type * c,
std::list<voronoi_diagram::cell_type *> & list)
{
const voronoi_diagram::edge_type * e = c->incident_edge();
bool justCalled; // true when we repalce the tail call
do
{
justCalled = false;
// Follow infinite edges, adding cells encountered along the way
if (e->is_infinite() && e->twin()->cell() != list.front() &&
e->twin()->cell() != list.back())
{
list.push_back(c);
c = e->twin()->cell(); // reassigns function argument
e = c->incident_edge(); // replay the initiaization (before do loop)
justCalled = true; // force the loop to continue
continue; // jump to start of loop
// everything happens as if we called findNext(e->twin()->cell(), list);
else if (e->twin()->cell() == list.front())
{
list.push_back(c);
return true; // we reached the starting point, return
}
e = e->next();
} while (justCalled || e != c->incident_edge());
return false;
}
This function is equivalent to the one you wrote, so you'd use it the same and you're sure there's no recursion involved. The bool
flag is necessary because continue
jumps to the test of the loop and not its body see here, thus the test might fail before the loop even begins when we change arguments and call continue.
This is a general technique, not specific to graph traversal but to all recursive algorithms. Of course if you have many function arguments and a large body of code, the transform is heavy lifting, but in this case I think it's a good match.
In more complex cases when the recursion is not a tail call, you still can "de-recusify" any function by maintaining your own stack. This has the advantage that replacing the stack structure with say a priority fifo may change the traversal order in ways more subtle that what recursion can (easily) achieve.