Can someone explain or point towards an explanation, what the performance impact of such a query is? How does it scale with number of edges or depth of recursion? Is there a special smart way of indexing this to be efficient?
The size of the table (# of edges) won't actually matter *that* much performance wise with btree indexes. The performance will mostly depend on how deep you want to go with your recursion. The more nodes you check per query, the slower it'll be. Luckily PG will keep the frequently accessed nodes and index pages in the buffer pool, so it'll perform close enough to an in-memory graph database for most use cases that access the same data often - while not requiring your whole dataset to fit into memory all the time.
MongoDB's current graph search mechanism works the same way.
I think actually if you are using incremental ids and you don't delete edges, you could try BRIN indexes for the next/previous node columns. This could still get you pretty good performance with much lower storage space requirements than a "traditional" index, so you could theoretically store a pretty large graph (thinking billions of edges) with minimal disk space.
You can get O(1) performance on similar queries using a different storage strategy (by storing edges as pointers to the other nodes in memory) but SQL is not the right tool for that, you would be better off with a true graph DB.