The rational is vary reasonable. Basicly, all recursion can be replaced by a loop that does not risk blowing the stack or using extra memory. However, tail call optimization is basically the compiler doing that conversion for you which also removes the risks.
Well, if the compiler will also report error for recursive calls not in tail position...
There are strategies to prove various things about recursive calls. See Ada/Spark's explanation for Rule 17.2 in [1].
I'm not familiar with Coq and Agda, but I believe they allow recursive calls if they can prove termination, though "termination" may be different than "using too much stack".
As a rule of thumb, they permit recursion where one parameter "obviously" is getting smaller each time, with a base case at 0 or the empty list or whatever.
You can annotate the program in ways to make the compiler see that a parameter is actually getting smaller.
Replacing recursion with a loop can easily use extra memory. The usual approach is to implement a stack using a local variable: each iteration pops the head and processes it; rather than recursing, we push a new item and let the next iteration process it for us.
If the algorithm is tail-recursive, this will use constant stack space and memory, just like tail-call optimisation. If the algorithm's not tail-recursive, it will use constant stack space but large (potentially exponential) amounts of memory.
There's no way around this. The only solution is to come up with a different algorithm (eg. using an accumulator).
You're usually better off with manual recursion, if you're concerned about running out of space, for the simple reason that it's far easier in practice to back out of an out-of-memory situation than from a stack overflow.
Optimal loops don't use more memory than recursion and generally significantly less. Though if you can find an counter example in a common programming language I would love to see it.
However, we are talking about the automotive and aerospace industry so recursion overhead is often a deal breaker even if there are no other issues.
> Basicly, all recursion can be replaced by a loop that does not risk blowing the stack or using extra memory.
This isn't true at all. You can replace all recursion with loops, sure, but you're going to have to simulate a stack (i.e. use extra memory) to convert complex recursive functions to loops.
I believe that there is a better reason to ban recursion - it may mask possible execution time of code. Loops are more explicit in that regard. If you are writing a real-time system, you care about those things a lot. Ban of dynamic memory also may be caused by requirement to be real-time.
> tail call optimization is basically the compiler doing that conversion for you which removes the risks.
Then can one argue that loops vs. recursion is mostly a matter of style and loops just as good as recursion since the compiler will optimize them that way anyway ?
Not all recursive functions can be rewritten to be non-recursive. The Ackerman function is one such example. It's clearly tail recursive, but not only tail recursive so it must use some kind of stack or tree or something which isn;t linear like a loop. there's some explanation on the Computerphile youtube channel discussing it: https://www.youtube.com/watch?v=Mv9NEXX1VHc
Yes, but only in the cases where the tail recursion optimisation is applicable.
Recursive constructs are can be not tail recursive (and usually are with new starter developers) and many languages ignore it anyway (meaning even code that can be unpacked from function calls into a loop are not so the stack is still used).
Yes, but humans mess up loops far more frequently than compilers do. If we follow your argument recursively, we would all end up writing assembly language again, wouldn't we? :)
I guess. But if I make the mistake of infinitely recursing I find out the next time I run my program. If I'm writing my own loops and make an off by one error it could go uncaught potentially forever.
One of my favorite PHP gotchas is to accidentally write a function that calls itself infinitely, and then have the interpreter die without a warning message.
If a program is only doing a simple calculation and it's still running an hour later, you should probably suspect an infinite loop and not wait for it to stop.
