Return to Answer

Considering what this has been compiled to, we have turned code that uses the call stack to implement recursion into code that does not (and in doing so turned code that will throw a stack-overflow exception for even quite small values into code that will merely take an excruciatingly long time to return [see How can I prevent my Ackerman function from overflowing the stack? for some further optimisations that make it actually return for many more possible inputs]).

Considering what this has been compiled to, we have turned code that uses the call stack to implement recursion into code that does not (and in doing so turned code that will throw a stack-overflow exception for even quite small values into code that will merely take an excruciatingly long time to return [see How can I prevent my Ackerman function from overflowing the stack? for some further optimisations that make it actually return for many more possible inputs]).

If we strictly require it to involve the call-stack (which for one thing assumes the existence of a call-stack), then we can always replace it with something that doesn't. Indeed, languages that lead naturally to heavy use of recursion tend to have compilers that make heavy use of tail-call optimisation, so what you write is recursive but what you run is iterative.

If we strictly require it to involve the call-stack (or whatever mechanism for maintaining program state is used), then we can always replace it with something that doesn't. Indeed, languages that lead naturally to heavy use of recursion tend to have compilers that make heavy use of tail-call optimisation, so what you write is recursive but what you run is iterative.

Of course, all of this assumes you have a choice. There are both languages that prohibit recursive calls, and languages that lack the looping structures necessary for iterating.