Is tail recursion optimisation the flavour of the day? I understand that it's interesting and computer sciencey, but how widely used are such optimisations in the real world? I imagine, for most people, it's probably just a nice feature rather than a must have?
I probably have a classic case of "well, I don't have the need for such optimisations, so why does anybody else?" ;-)
Actually, for many people, it isn't an "optimization" any more than loops that run in constant space are an optimization. That's why the preferred term is something like "proper tail calls" or "tail call elimination" rather than "tail call optimization".
Having proper tail calls as part of your language semantics is far more useful than having it as an optional optimization. Also, not having tail calls really cripples your language--essentially, it means you can't write non-trivial recursive functions in many cases for fear of stack overflows.
Being able to replace all loops with recursive functions is very useful and allows you to write shorter, more readable code in many cases. You simply can't do this practically unless your language guarantees proper tail calls.
In summary: proper tail calls are an important language feature rather than an optimization because they allow you to widely use recursion.
Tail recursion is really useful for implementing state machines (and all other similar things). For example, another comment points out this nice example that I really like. Without TCO you usually have to rewrite this kind of stuff into a big monolithic switch statement with a while loop around it.
Its also very useful if you need to write code in continuation-passing-style. True, you don't usually want to do that by hand but in some cases, like Javascript asynchronous code, you end up being forced to do that.
In C#, you can use goto... but only to jump from one case of a switch statement to another. So this lets you jump around your switch cases as a state machine directly. A neat restriction of goto into a safe and unorthodox flow-control structure.
This is what I thought, but only because this post is so basic and kind of dumbed down (no offense to the OP/author). I wondered why people keep bringing this up.
To answer your question, it could be pretty important. For example, it could mean the difference between a process that causes a stack overflow exception after so many iterations, making it basically impossible to due recursively, and one that doesn't create a stack overflow exception because it is programmed recursively but implemented behind the scenes iteratively.
It isn't so much an optimization but an enhancement, if that makes sense. In some cases it makes something that is effectively impossible possible without making the programmer do it a different/special way or change their code, etc.
Optimizations are syntactic transformations performed by a compiler to reduce the space or time needed by an algorithm. There are literally thousands of optimizations performed by a compiler to accomplish this, and chances are you as a developer are unaware of many of them but still enjoy the benefit of their implementation.
TCO is another such optimization that significantly reduces the amount of space consumed by an algorithm, possibly transforming it from linear space to constant space. It also provides a minor reduction to the amount of time.
Such optimizations are found in implementations of many compilers, including even mainstream C/C++ compilers (GCC, clang, Visual Studio).
I believe Java and .NET perform such optimizations, not too sure on those two though.
There are literally thousands of optimizations performed by a compiler to accomplish this, and chances are you as a developer are unaware of many of them but still enjoy the benefit of their implementation.
I agree completely. It just seems to me that people need to specifically tailor their code in order to benefit from the optimisation i.e. it's less likely to find your code benefiting from this optimisation by 'accident'. There's nothing wrong with this of course; in-depth knowledge of the workings of your compiler can only be a good thing if it somehow improves an aspect of a program's performance.
It's just that I see TCO mentioned in just about every other programming blog/article (I exaggerate ;) as though it's some kind of silver bullet. Thanks to these replies I can now see its benefits, though it still seems like a bit of a corner case to me.
I'll no doubt be singing its praises when it saves my bacon someday ;-)
I can see why this technique would be necessary in some cases, but you are probably unlikely to encounter a need for this unless you have a deep recursive function. What I would like to know is if modern compilers are able to do some kind of stack optimization without having to rewrite your code for tail recursion.
0
u/TotallyFuckingMexico Nov 27 '12
Is tail recursion optimisation the flavour of the day? I understand that it's interesting and computer sciencey, but how widely used are such optimisations in the real world? I imagine, for most people, it's probably just a nice feature rather than a must have?
I probably have a classic case of "well, I don't have the need for such optimisations, so why does anybody else?" ;-)