I feel like this is circling around total functional programming. I found this to be an accessible paper on this:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.106...

The language it uses enforces that all recursive steps "simplify" the input, and gives a simple definition of "simplify".

Note that the language is not (nor does it try to be) Turing complete - intuitively you could imagine that there might be some level of expressiveness which is not enough to get to halting problem like levels of complexity, but enough to get "real world" complexity.