Recursive queries are definitely top of the complexity pile IMO. However I usually discount them because I am yet to actually need them in a production environment. Window functions are super useful on the other hand.
One instance was to turn a column containing comma separated values into rows[1], so I could join on them. Wasn't for a query that needed performance of course.
If only the DB we're using had one of those :)