[ZephyrP]

> Manifestly, recursion is never strictly necessary, and is furthermore almost always slower, or anyway no faster, than you could do maintaining state "by hand".

Recursion is required in procedures like Ackermann's Function [1]. You can still simulate or write functions that avoid the syntactic fact that the procedure definition refers (either directly or indirectly) to itself, but you'll always be papering over the fact that it cannot be implemented with a fixed number of state variables.

[1] https://en.wikipedia.org/wiki/Ackermann_function

[qsort]

> Recursion is required to implement non-primitive recursive procedures

This is very untrue. While loop and a stack.

> cannot be implemented with a fixed number of state variables

Of course it can't, any function outside DSPACE(O(1)) can't. The fact that you have an implicit call stack doesn't change the space complexity.

[ZephyrP]

> This is very untrue. While loop and a stack.

>> You can still simulate

> any function outside DSPACE(O(1)) can't

The space complexity of the algorithm is only incidentally related to the number of unique variables required to represent it's state.

You said it best:

> The fact that you have an implicit call stack doesn't change the space complexity

[ncmncm]

As I said, and as you admit, contradicting yourself: "You can still simulate..."

We could better say that recursion is papering over a fundamental fact that the iterative form reveals. You encounter it in the recursive case, painfully, when your stack overflows. Assuming infinite memory is the fatal flaw in most modern systems.

Ackermann's function never appears in the real world.

[ChrisLomont]

>You encounter it in the recursive case, painfully, when your stack overflows.

People who write high performance code don't worry, because they write the recursion properly, and tail recursion doesn't use the stack.

If your understanding of recursion leads to stack overflows then you're missing a significant tool in your toolbox.

There is no more need to overflow a stack using recursion than there is to overflow a stack or heap trying to store state when unwinding a recursive function into an iterative one.

However, the recursive solution is vastly simpler in many cases since you don't have to fiddle with state, which is mutable and error prone, and can instead use immutable concepts (in any language) to write correct code more quickly with zero penalty in execution speed or space. It makes you a more valuable employee to learn these techniques.

[kazinator]

Have you heard of this Turing fellow? He produced a result according to which a function such as Ackermann can be calculated with a read-write head moving over an unlimited tape. No recursion there.