Судя по тому что говорят интернеты рекурсия линейная, и рекурсия первого порядка - это одно и то же, а именно рекурсия с одним вызовом (т.е. без ветвления).
Соответственно, такая рекурсия по сути является циклом написанным в виде рекурсии.
Цикл можно распараллелить в случае если вычисляемые значения не зависят от предидущих итераций цикла (или хотя бы их часть)
Как вариант примера: map на multithreading коллекции (то есть распаралеленный map)
docs.scala-lang.org/overviews/parallel-collections... 
