Recursion is not fundamentally sequential. It depends on your data structures:
Structural recursion on sequential data structures is sequential. Structural recursion on somewhat-balanced tree-like data structures is more amenable to parallelism.
(And non-structural recursion is too general to talk here.)
Though I agree that using recursion does not scale very well in terms of program complexity. Hide your data flow behind combinators, if you don't want to get a headache.
I highly recommend Guy Steele's talk that's linked in a sibling comment. I am glad I attended ICFP that year.