Is this the best way to utilise tail call recursion traversing a linked list?

Question

Basically I am creating a base class that will be used for classes stored as a linked list, which are traversed and deleted as dictated by a virtual update() function which returns a bool.

I am wondering if this is the most efficient case (I like the fact that it can be a singley linked list in particular):

class Traversable
{
    public:
        Traversable();
        virtual ~Traversable();
        void traverse(Traversable** prevNext);
        virtual bool update()=0;
    protected:
    private:
        Traversable* next;
};


void Traversable::traverse(Traversable** prevNext)
{
    if (!update()) /// Virtual function that returns a death flag
    { /// Death
        if (next)
        {
            Traversable* localNext = next;
            delete this;
            localNext->traverse(prevNext);
        }
        else
        {
            *prevNext = NULL;
            delete this;
        }
    }
    else
    { /// This node stays alive, for now
        *prevNext = this;
        if (next)
        {
            next->traverse(&next);
        }
    }
}

Note the linked list is NULL terminated.

I think the careful lack of an assigment operation to a local variable after the next traverse function is called will secure usage of this function using tail calls. Can anyone spot anything I have done wrong, or perhaps suggest a slightly less convoluted approach :p

Nice code, but perhaps this ought to move to http://codereview.stackexchange.com/? — Kerrek SB, Jun 24 '11 at 00:27
Well, the most *efficient* way would be to replace the recursion with iteration. However, I don't think that's what you want. :) — Billy ONeal, Jun 24 '11 at 00:51
Compile the function, and see if your compiler performs the optimization. It doesn't really matter if the function is eligible for an optimization if the compiler doesn't actually do it. — Dennis Zickefoose, Jun 24 '11 at 01:00
Tail recursion or not may depend on your compiler and settings. This was discussed [here](http://stackoverflow.com/questions/34125/which-if-any-c-compilers-do-tail-recursion-optimization) — thorsten müller, Jun 24 '11 at 01:04

FrankH. · Accepted Answer · 2011-07-04T11:54:33.227

You're deliberately obfuscating the code in order to "tempt" the compiler into creating a specific result; whether this happens or not is quite probably more dependent on the compiler used, the optimization flags in effect, or even the code compiled that's using the above. The following is more compact code:

void Traversable::traverse(Traversable** prevNext)
{
    bool doUpdate = update();

    *prevNext = doUpdate ? this : next ? *prevNext : NULL;

    Traversable **argNext = doUpdate ? &next : prevNext;
    Traversable *localNext = next;

    do_the_traversal_action();     // not spec'ed ...

    if (!doUpdate)
        delete this;
    if (localNext)
        localNext->traverse(argNext);
}

and still ends the function with a single tail return point. The only reason this uses conditionals is because you're changing prevNext in there.

Edit: what I'm trying to say is that no matter how you code it, in the end it's up to the compiler to decide whether it wants to tail-optimize the function or not. For modern optimizing compilers, there's often switches (-fconserve-stack or -foptimize-sibling-calls in GCC) that have a more immediate effect on this more than the sourcecode itself.

Edit 2: yes if course it's possible to write this function non-recursively; all it is, in the end, is a visitor type pattern. So the actual activity ends up being something like:

static void Traversable::traverse(Traversable *start)
{
    Traversable *cur, *next;

    for (cur = start; cur; cur = next) {
        next = cur->next;

        cur->do_the_traversal_action();     // not spec'ed ...

        if (cur->update())
            continue;                       // not supposed to remove this

        if (next)
            next->prevNext = cur->prevNext; // remove cur from list
        delete cur;
    }
}

Though, when you code it like that, the next obvious question is why one would not implement simple iterator types for Traversable and use std::remove_copy_if() for the visit-and-remove-on-condition task. Or use an STL list to start with.

Also most any recursive code that is suitable for tail call optimization is easily convertible to an iterative solution that is as easily readable and does not require the compiler to recognize that it can be optimized — dschaeffer, Jun 28 '11 at 19:49
You're perfectly right about that of course; I've added the nonrecursive version, just to make that obvious. — FrankH., Jul 04 '11 at 11:57
Yea, I guess if you want efficiency, looping is just the way to go as opposed to recursion — deek0146, Aug 01 '11 at 12:12

Is this the best way to utilise tail call recursion traversing a linked list?

1 Answers1