As far as I know, there aren't any languages which provide a way to do this out of the box. If a language wants to provide an environment where no stack overfl

As far as I know, there aren't any languages which provide a way to do this out of the box. If a language wants to provide an environment where no stack overflows can happen, then it needs to provide a runtime where the stack programs use is transplanted over to the heap as it gets too large (or maybe it just starts out there). At this point the answer is that you only need a stack big enough to hold your runtime (which you can engineer to be sufficiently small always). Of course you can imagine a language where your function signature includes how much stack space it takes up. The stack size being recursively calculated by looking at all the functions your function calls etc. If recursion is included, then you're correct that this would require solving the halting problem. The obvious solution would be to just not allow recursion. Although, if you also consider languages like Idris (which are technically sometimes not turing complete) you can setup a termination checker and then certain rules can give you an upper bound on how long a recursive function will run (and therefore how much stack it takes up).