Eulerian Tour in Python This is a recursive algorithm implementation of Eulerian tour search.

I guess there is no way to make it more efficient (except rewriting with loops instead of recursion). Any advice on style?

def sub(visited, _cur, graph):
    if not graph:
        return visited + [_cur]
    for i, edge in enumerate(graph):
        cur, nex = edge
        if _cur not in edge:
            continue
        _graph = graph[:]
        del _graph[i]
        if _cur == cur:
            res = sub(visited + [cur], nex, _graph)
        else:
            res = sub(visited + [nex], cur, _graph)
        if res:
            return res


def find_eulerian_tour(graph):
    head, tail = graph[0], graph[1:]
    prev, nex = head
    return sub([prev], nex, tail)

assert find_eulerian_tour([(1, 2), (2, 3), (3, 4), (4, 1)]) == [1, 2, 3, 4, 1]
assert find_eulerian_tour([
    (0, 1), (1, 5), (1, 7), (4, 5),
    (4, 8), (1, 6), (3, 7), (5, 9),
    (2, 4), (0, 4), (2, 5), (3, 6),
    (8, 9)
]) == [0, 1, 7, 3, 6, 1, 5, 4, 8, 9, 5, 2, 4, 0]
Comments and good docstrings would go a long way. Obviously if I was familiar with the algorithm I'd understand easier, but you're not helping a lot with your naming. Why are you using _cur and cur? Do you just want to use the same name twice without clashing? If so you should do it another way, because _var is the Python style of indicating a variable that should be treated as private and not modified externally. It's an idiom for classes and looks out of place here.

Even still, cur, nex mean current and next, right? As you noted you shouldn't use next because it's a builtin name, but using next_branch or something more descriptive is better than stripping away a letter. Also if I've got the wrong end of the stick and nex is something else, that also just means you need a better shortened word or a comment explaining what nex is.

Also more whitespace will make the flow of your code easier to read than a solid block of text:

def sub(visited, _cur, graph):
    if not graph:
        return visited + [_cur]

    for i, edge in enumerate(graph):
        cur, nex = edge
        if _cur not in edge:
            continue

        _graph = graph[:]
        del _graph[i]

        if _cur == cur:
            res = sub(visited + [cur], nex, _graph)
        else:
            res = sub(visited + [nex], cur, _graph)

        if res:
            return res


Even before adding code and more readable names, this breaks up what's happening so a reader can parse it easier.