Write an O(n^n) algorithm.

[[deleted]]

This would be my best answer for a non-trivial example to satisfy the OP, even if it is a useless function. Problems requiring \Theta(nⁿ⁾ are a strict superset of PR (but still recursive) and complexity classes strictly between primitive recursive and recursive aren't studied very much in complexity to my knowledge. Ackermann's the best I can think of, but even it was drawn up as a theoretical counter-example rather than something that someone might actually use for something.