In the lowest level, yes, but you could say the same about regular function calls, return statements, and even loops and conditionals, break and continue, etc.
The main selling point of using recursion for looping, IMO, is immutability. As jacquesm said, you don't need mutable local variables to track the state of the loop.
And in the real world functional programming you rarely use recursion to replace a loop, you mostly use abstractions like map/reduce/etc along with lambdas, etc.
Sure, it's all gotos at the bottom, but structured programming was introduced for a reason: it makes loops easier to reason about. In functional programming, functions like map and reduce serve the same purpose. My point is that most of the time you should use some higher-level control structure to represent a loop rather than bare gotos or bare tail recursion.
Also, avoiding mutation of local variables is a poor reason to prefer recursion. Mutable local variables are harmless so long as they don't escape (as in a closure). If the inputs and outputs are immutable then it's still a pure function. You can use them if it makes the program simpler and/or faster and the program as a whole is just as pure.
It's really too bad that functional languages avoid mutable local variables; it would make the divide between imperative and functional languages easier to jump.
Though people often criticise immutability on the ground that the machine code mutates registers and memory addresses as they're scarce resource, the compilers don't often generate such code directly. The compilers generate IR in the static single assignment form for better analysis and optimisation. That said, you should know why mutation is not inherently good, but a compromise to the pathetic reality. And now you know the technique to avoid mutation in general as well.
> you don't need mutable local variables to track the state of the loop.
Erm, that's not really true is it? Isn't the main way which TCO is (usually? always?) done by introducing a counter/accumulator?
It does alleviate the kind of thing you see in c (or other similar languages):
while(int i = 0; i++; i < 10)
{
i--; // whoops
blah();
}
But you can hide that counter in many, many (useful) ways, like with iterators, or just some syntax that avoids modifying (or even checking) the counter variable in the loop.
So not having TCO is generally a way to avoid local state variables (but an ever expanding, eventually overflowing stack), implementing TCO tends to re-introduce a counter to avoid growing the stack (and then you have clever ways to emulate stack frames based on how far you got in the loop... sort of giving you the best (and/or worst) of both worlds).
Anyway, if all you want is a safe loop construct, recursion isn't the only option.
(All that said, I like the elegance of "lets pretend the call stack is infinite"-recursion -- and like the idea of TCO. Just don't oversell it.)
>> you don't need mutable local variables to track the state of the loop.
> Erm, that's not really true is it? Isn't the main way which TCO is done by introducing a counter/accumulator?
Yes, but accumulators aren't mutable. You're just passing something like acc*n or acc+1 to the tail call... acc is still the same.
Also, accumulators are not analogous to loop counters, they're more like the "sum" variable in this example (also mutable):
var list = [0,1,2,3];
var sum = 0;
for (var i = 0; i < list.length; i++)
sum += list[i];
> Anyway, if all you want is a safe loop construct, recursion isn't the only option.
I agree! The point of having TCO in a language isn't replacing every for/while loop with recursion. TCO is just an optimization. The right way (at least IMO and IME) is using better abstractions, like you mentioned. Recursion is just a way of easily building those abstractions, as are loops.
Btw, I probably write way more recursive functions in C than I do in Haskell, because in Haskell I have folds and catamorphisms.
I mean, the idiomatic way of summing those numbers as I did above in functional style is probably this:
Every function call is "goto with arguments". Sometimes there's even an argument that tells the code block where to jump back to when it's done.
>Like a goto, it's useful but potentially confusing.
How is it confusing? You don't even have to be aware of TCO to take advantage of it. Many recursive algorithms are tail-call-optimizable out of the box.
>You shouldn't use it when a more structured loop construct will work.
Ironically, there are many programmers who consider loops to be too low-level and unstructured compared to recursive algorithms.
There is a really nice example of the "goto" semantic for proper tail calls in "Programming in Lua". The example is a maze or adventure game where you need to move into different rooms (north, south, east west).
It's a nice example because it's simple, it doesn't confuse/intermix the concept with recursion, and it's an effective solution because it allows you to achieve the goal of moving to rooms (i.e. s state machine) elegantly. And in a language without proper tail recursion, it is easy to envision how you could accidentally blow up the call stack.
Loops are a much higher level construct than tail calls. It's much easier to make a mistake iterating through a list using tail calls than it is using a loop or a higher order function. (E.g. you can forget to handle the base case.)
While I agree that higher-order functions are higher-level than tail calls, I'd say that the prevalence of things like off-by-one errors makes the comparison between loops and tail calls far more ambiguous.
In FP loops are typically frowned upon and then the tail call is presented as an elegant solution, because it can be optimized into a loop but still look like a function call with all the goodies a function call normally gives you, minus the new stack frame.
I'm really not convinced of this, it looks like a function call but it is a loop. If it is a loop under the hood then I'd like to see that loop, in my mind I always see this 'stackoverflow' neon sign hover over every tail call (of course it doesn't but years of debugging stuff have ingrained all kinds of interesting detection habits).
Making it look like a loop would introduce all kinds of syntactical complexity, and suddenly you'd be re-using your local variables. So that's not a solution either. But it feels a bit like a kludge.
It looks like a function call and it is a function call. There's nothing about a function call that requires pushing a stack frame ... as the existence of TCO demonstrates.
I'd argue that's the wrong interpretation. Function-calls absolutely require pushing a stack-frame, and TCO is no exception. TCO just says "Oh hey, we're done with the current stack-frame, let's toss it out before we call the next function". That's why TCO can apply to function-calls which aren't recursive. The recursive case still follows this rule, it's just the old and new stack-frames are identical. The compiler makes another optimization of not bothering to remove the stack-frame and just reuses it for the next call (Since it's going to be the same size anyway). Even noting that, there are still some cases where this also doesn't apply, because if (in C) you use VLA's at the beginning which depend on a supplied argument, then even with TCO, you still have to remove and create a new stack-frame every call.
I suggest you read "Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO": <http://library.readscheme.org/page1.html>, in particular section C.
I'm not so sure that in FP communities recursive call based algorithms are thought of as elegant solution; rather higher abstractions are desirable (e.g. map, filter, fold, etc)
Basically you want to always use the least powerful tool you can to solve a problem. When applicable, map is better than foldl not because it's more concise, but because it tells the reader that the result is a list of the same length of the input, and the elements of the input are processed independently. Similarly, foldl is better than raw recursion because it tells the reader that every element in the input list is being processed in order, rather than potentially anything happening.
There's nothing wrong with using the more powerful tools when you need them (such as when implementing the more restricted tools). It's just that needing them frequently is a sign that you're doing weird things and should take a second look at your design to make sure there isn't a better way to do things.
Sure, it's all gotos at the machine level. There's nothing wrong with implementing map that way. The point is to use a higher-level, less free-form control structure when it matches the problem, because it gives the reader more information.
If you look at it from the perspective of continuations then tail calls are very natural. A function call is always a goto, the only difference is that calls in tail position do not need to add extra data to the continuation.
Of course! But that still doesn't mean you should use them most of the time. Continuations are great for writing compilers but confusing to use elsewhere. Just like you don't normally write assembly (but it's necessary sometimes), you shouldn't normally use these exceptionally flexible but unstructured abstractions in a program you want other people to read.
Instead you want to use constructs that are familiar and easy to reason about. It's hard to beat a for loop.
Sure, whether you should use them is a software engineering question. I was merely speaking to their theoretical elegance, pointing out that from a continuation perspective tail call optimization isn't really an optimization, it's just the most natural way to implement procedure calls to begin with.
I agree wholeheartedly with the main thrust of your argument, but I think it is slightly disingenuous to put confusability of goto and tail calls in the same league. Yes tail calls are gotos, but it is at an order of magnitude better than a goto at conveying the meaning of the code snippet to a human.
This is anecdotal, but some reasons, goto labels are not as well named as function names. With a goto it is more difficult to guess what data the destination code is expected to touch.
Tail calls are an improvement on both the counts. I often do not have to break context from reading a piece of code to start reading the piece of code that the program counter jumps to (unless it is a very local jump). The arguments passed by a tail call and the name of the function that has been tail called often makes (i) breaking code reading context less necessary and (ii) make larger semantic jumps remain within realms of easy human reasoning. With gotos, the jumps better be within 20 lines of text.
Like a goto, it's useful but potentially confusing. You shouldn't use it when a more structured loop construct will work.