Loops are a special case of tail recursion which is a special case of recursion [0] which is a special case of calling functions.

However, loops aren't the only use for tail recursion. Another classic example are state machines as described in the 'Lambda: the ultimate goto' paper. See eg https://en.wikisource.org/wiki/Lambda:_The_Ultimate_GOTO

[0] Well, recursion on functions. You can also have eg recursive data types or recursion in mathematics in general. But let's focus on functions.

▲

Kranar 5 days ago | parent [-]

I think it's the other way around. Tail recursion is a special case of loops. All tail recursive functions can be rewritten as a loop but there exist loops that can not be rewritten as a tail recursive function.

▲

mrkeen 5 days ago | parent [-]

I'll bite.

What's an example of such a loop?

▲

eru 4 days ago | parent [-]

> All tail recursive functions can be rewritten as a loop but there exist loops that can not be rewritten as a tail recursive function.

And the other way round: how do you (sanely) write a state machine as a loop?

See https://en.wikisource.org/wiki/Lambda:_The_Ultimate_GOTO for some examples.

I agree that (most) functions that only ever tail-call themselves can relatively easily be expressed as loops, if for some reason you really love loops. But state machines aren't like that.

With tail calls, you can represent each state as a function, and you can pass different parameters to different states. Very neat, and just works.

▲

jsmith45 4 days ago | parent [-]

For simple tail recursion, expression as a loop is pretty simple, just define the function with the same parameters, and mutate the parameters, possibly creating local copies of the original values if you need the previous value to evaluate another new parameter.

But since your example is relying on mutual tail recursion with functions for each state. Yeah, that is much harder to cleanly map to a simple loop. Like obviously making a giant function to cover all the state functions with a giant switch statement is possible, and even relatively common, but not especially clean.

If all state functions have the same parameters, then an approach with functions per state that return the new state and new parameter values, which get called from a loop using a state value to function dictionary can be relatively clean. But if states need different parameters, yeah that gets complicated.

	▲	eru 4 days ago \| parent [-]
		Yes, exactly. > If all state functions have the same parameters, then an approach with functions per state that return the new state and new parameter values, which get called from a loop using a state value to function dictionary can be relatively clean. But if states need different parameters, yeah that gets complicated. In a language like Rust, you can encode your state in an enum, and the different variants (= states) in a Rust enum can have different parameters. Then your implementation basically becomes a loop around a match statement over that enum. But all you've done here is manually implement a 'trampoline'. The trampoline is to a tail call what manually maintaining a (call) stack is for simulating non-tail calls. See https://en.wikipedia.org/wiki/Trampoline_(computing)#High-le...