Maximum stack usage can be calculated in the presence of recursion. Tail calls can be handled as branches instead of nested call frames, but also non-tail calls are tolerable if you have (or can infer) some measure to determine maximum call stack depth.
It's a pain, and the type system rejecting any recursion is certainly simpler, but that's not a strict requirement.
It's a pain, and the type system rejecting any recursion is certainly simpler, but that's not a strict requirement.