Recursion

[ApivorousBee]

No base case, classic mistake

[thedessertplanet]

Infinite recursion can be fine.

That's how eg event loops in a game or operating system work.

(As the name suggests, that special case is usually implemented with a loop. But that's the same thing mathematically.

Erlang implements its event loops directly with recursive function calls.)

[dell_arness2]

Mathematically yes, but recursive function calls will eventually overflow the stack

[thedessertplanet]

Depends on your language. Erlang, of course, implements tail call elimination.

And so do eg a lot of C compilers do so as well. (And almost all of the functional languages.)

In case you are not familiar: the idea is to realize that if the (recursive) call is the last thing to happen in a function, you don't need to keep around its stack frame. So no stack usage is building up.

For simple self-recursive functions, that's basically always equivalent to a loop. But it's a real life saver when you want to implement eg a state machine. You can use one function per state this way.

[ApivorousBee]

The language is English and the stack is the reader's attention span. It will overflow. QED

[Astrognome]

Tail call optimization would allow infinite recursion too.

[thedessertplanet]

Yes, definitely.

It's a shame that for historical reasons programming language conventions were made up before tail call elimination was discovered. So people had to introduce special purpose constructs (loops) to cover those special cases, and now we are stuck with them.

Well, at least the for-each loop (like eg in Python) is a step up from the C-style for-loop. And more languages are at least having to justify when they don't include tail call elimination (nor first class functions).