I see, but you could still wrap all other cases in some predefined functions or higher level primitives, and just have an "unsafe" mode for unrestricted recursion. It could even be treated as a side effect.
Also, in a high-performance setting, a surprising number of programs do not need recursion (and hence Turing-incompleteness) at all. In the vast majority of the Futhark programs I've written, `while` loops are either not used at all, or used for something fairly simple like an outermost convergence loop (and typically with a iteration bound anyway, so it could be written as a `for` loop with early exit).