I've been recently learning about functional languages and how many don't include for loops. While I don't personally view recursion as more difficult than a for loop (and often easier to reason out) I realized that many examples of recursion aren't tail recursive and therefor cannot use simple tail recursion optimization in order to avoid stack overflows. According to this question, all iterative loops can be translated into recursion, and those iterative loops can be transformed into tail recursion, so it confuses me when the answers on a question like this suggest that you have to explicitly manage the translation of your recursion into tail recursion yourself if you want to avoid stack overflows. It seems like it should be possible for a compiler to do all the translation from either recursion to tail recursion, or from recursion straight to an iterative loop with out stack overflows.
Are functional compilers able to avoid stack overflows in more general recursive cases? Are you really forced to transform your recursive code in order to avoid stack overflows yourself? If they aren't able to perform general recursive stack-safe compilation, why aren't they?
Any recursive function can be converted into a tail recursive one. For instance, consider the transition function of a Turing machine, that is the mapping from a configuration to the next one. To simulate the turing machine you just need to iterate the transition function until you reach a final state, that is easily expressed in tail recursive form. Similarly, a compiler typically translates a recursive program into an iterative one simply adding a stack of activation records.
You can also give a translation into tail recursive form using continuation passing style (CPS). To make a classical example, consider the fibonacci function. This can be expressed in CPS style in the following way, where the second parameter is the continuation (essentially, a callback function):
def fibc(n, cont):
if n <= 1:
return cont(n)
return fibc(n - 1, lambda a: fibc(n - 2, lambda b: cont(a + b)))
Again, you are simulating the recursion stack using a dynamic data structure: in this case, lambda abstractions.
The use of dynamic structures (lists, stacks, functions, etc.) in all previous examples is essential. That is to say, that in order to simulate a generic recursive function iteratively, you cannot avoid dynamic memory allocation, and hence you cannot avoid stack overflow, in general.
So, memory consumption is not only related to the iterative/recursive nature of the program. On the other side, if you prevent dynamic memory allocation, your programs are essentially finite state machines, with limited computational capabilities (more interesting would be to parametrise memory according to the dimension of inputs).
In general, in the same way as you cannot predict termination, you cannot predict an unbound memory consumption of your program: working with a Turing complete language, at compile time you cannot avoid divergence, and you cannot avoid stack overflow.