I recently used RCTEs in a production environment to operate on reasonably large graphs. We eventually moved to an in memory solution built on top of ETS for various reasons, but performance was not a deciding factor (at least as much as you would think); Postgres handled our queries well beyond expectation, even with heavy factoring into functions. It's definitely not slow.

The largest burden was on development and maintenance. Iterating algorithms and queries powered by RCTEs (and functions) on a changing schema is not scaleable (in effort), at least with the traditional migration scripts approach to upgrades and rollbacks. If you do want go this route, you need to change how you ship those functions and queries.

We theorized that shipping them as part of the application and performing necessary migrations behind-the-scenes would have drastically reduced the maintenance burden. We also considered composing queries completely dynamically and fully leveraging our language (Elixir) to provide a toolbag of functions that aren't functions as far as Postgres was concerned. In either case, the hassle of versioning functions and queries would no longer get in the way iteration.