[abetlen]

> I'm pretty sure you could also maintain a temp table and use some kind of "insert...where...returning" construct to squeeze that into a recursive query.

I'm not sure if this is possible in SQLite, as far as I know the WITH clause is limited to SELECT statements.

> Are they actually efficient in sqlite even for trees?

Recursive common table expressions work by adding returned rows to a queue and then performing the recursive select statement independently on each row in the queue until it's empty.

You can use WITH RECURSIVE to traverse a tree by adding the root node to the queue and recursively visiting adjacent rows until the queue is empty. This works correctly and quickly because trees have only a single path between nodes. If you try the same query on a DAG though it will return every path to a given node, you then have to perform a GROUP BY to find the shortest path outside of the recursive query. In the worst case, if you have a graph with many paths between nodes, this method is exponentially slower than a standard BFS.