Comment by fogzen
Yes, for some kinds of operations on some kinds of data structures. The keyword/property is "monotonicity". Monotonic functions are guaranteed to terminate under fixed-point semantics.
Look into Datafun: A total functional language that generalizes Datalog. Also be sure to watch Datafun author Michael Arntzenius's Strangeloop talk.