> Recursion and non-strict evaluation, however, are clearly problematic viz. stack consumption, system load, and execution time; ditto for purely functional data structures and associated functions.

What you'd want is not a Turing complete language by default, but one that's guaranteed to halt. (And only have Turing complete bits as a fallback, just like unsafePerformIO today.)

Primitive Recursion might be a good limited but useful model of computation. Or something along the lines of Agda.

With such a more restricted notion, recursion doesn't necessarily have to be compiled to a stack.