How can I recursively search a list of lists for an item, getting the "closest" match

Answer 1

Sounds like you are asking for a Breadth-first search.

I think your question may be related to a homework assignment, so I won't divulge more details here.

Answer 2

Use a breadth-first search. As you access a node that isn't equal to the query value, you push that node onto the back of the queue. Process nodes from the front of the queue first. The first match you find will be the one closest to the root.

Class* Class::findItem(const std::string& n) const {
    std::list<Class>::const_iteratior i;
    std::queue<Class*> q;
    q.push(this);
    while (!q.empty()) {
        Class *c = q.front(); q.pop();
        if (c->name() == n) return c;
        for(i=c->_members.begin(); i!=c->_members.end(); ++i)
            q.push(i);
    }
    return NULL;
}

Answer 3

If you do it breadth-first-search style, i.e. first look at all the Bs, then all the Cs, etc., your match node will automatically be the closest.

Answer 4

It seems as if you are interested in performing a BFS (Breadth Search First). The simplest way of implementing it is not by recursion but rather with a FIFO queue where you add the neighbor elements to the one you are testing at the end, and extract the first element from the queue to perform the next check.

The order of insertions would be [ A(1), B(2), B(3), C(3), ... ] and you will find B(3) before testing C(3).