Sure, and you can use things like co-recursion, which is how Agda (a total language) models potentially non-terminating computations. It means that while you can run forever, you need to perform productive work within finite time. As an example, consider producing an infinite sequence of items, but where each item is produced in finite time.

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).