How to fix a stack overflow error caused by recursive functions? C++

Question

As titled, I figured a recursive function has caused my program stack overflowing. And the recursive logic is needed, how to fix it?

Code:

static bool orient_flip_face(HE *edge)
{
    if(edge->flip == NULL)
        return 1;
    return orient_face(face);
}

static bool orient_face(HEF *face)
{
    assert(face->oriented);
    return orient_flip_face(face->edge);
}

static bool build_HE(he::Mesh_Data *mesh,
                     std::vector<HEV*> *hevs,
                     std::vector<HEF*> *hefs)
{
     // process mesh data
     // ...

     return orient_face(first_face);
}

Basically orient_face and orient_flip_face calling each other back and forth until it's the last vertices. It's fine when I pass a simple mesh, but when I pass the stanford rabbit which has 63690 vertices, it's overflowed.Then I increased stack reversed size to 40MB and it fixed the stack overflow error. But is it a reasonable solution?

Thank you!

Answer 1

Your code is an example of tail recursion because the recursive calls are the last thing executed in each function. Tail recursion is easy to transform into a non-recursive loop. The following code is the equivalent to the code you have and doesn't use recursion at all.

static bool orient_face(HEF *face)
{
    for (;;)
    {
        assert(face->oriented);
        HE *edge = face->edge;
        if (edge->flip == NULL)
            return 1;
    }
}

static bool build_HE(he::Mesh_Data *mesh,
                     std::vector<HEV*> *hevs,
                     std::vector<HEF*> *hefs)
{
     // process mesh data
     // ...

     return orient_face(first_face);
}

As some programmer dude pointed out, the code is effectively a no-op (excepting the assert, but I'm assuming that's just a debugging detail, and not the point of the code). So unless there's something else going on you can delete it completely.

The details matter.