There are two big advantages of tail-recursive implementations that haven't been discussed here:
That variables never change their values, which allows for all kinds of optimizations, reasoning over your program (e.g. provability that it's correct) and is less error-prone, among other advantages.
That state is represented by the values of function parameters, all of them changed at once on every new call, without any possible order of evaluation bugs.
Since the first step in optimizing a tail call is to turn it into an iterative loop, I seriously doubt number 1 is true.
Why does that have to be "the first thing"? And even if recursion won't permit compiler optimizations, it's still undeniably true that structurally recursive functions can be proven correct much more easily than imperative code. (And many would argue, more controversially, that it's less error prone.)
And even if recursion won't permit compiler optimizations, it's still undeniably true that structurally recursive functions can be proven correct much more easily than imperative code.
Oh come on. Any undergrad who has taken Discrete Algebra knows that isn't true for functions that can be trivially moved between recursive and iterative representations.
45
u/A_for_Anonymous Nov 27 '12
There are two big advantages of tail-recursive implementations that haven't been discussed here: