5 ms·

It seems like a difference without distinction to me. I mean, sure, it doesn't fit the precise dictionary definition of tail recursion, but the function would

It seems like a difference without distinction to me. I mean, sure, it doesn't fit the precise dictionary definition of tail recursion, but the function would be fairly trivial to implement in a purely tail recursive manner. As such, its close enough for most purposes.

kylec 16y ago
It matters when you have an interpreter/compiler that does tail-call optimization. If the function is tail recursive then the recursion will only use O(1) stack space, while non-tail recursive functions will use O(n).
bitwize 16y ago
Tail recursion means that there's nothing in the continuation of the recursive call besides a return from the outer call. This means that a compiler can optimize away the saving of a new stack frame for a recursive call, because the old stack frame of the enclosing call will never be used again. That's tail-call optimization. If there's stuff in between the return from the recursive call and the return from the enclosing call (like the multiply in this factorial example) then the old stack frame will have to be kept around which means you must use unoptimized recursive calls.
DrJokepu 16y ago
Sometimes it's trivial, sometimes it's not. Sometimes it's not even possible (e.g. the naive Fibionacci algorithm). Sometimes all you need to do is to add an accumulator argument to the recursive function. Still, it's not something that can be easily automated and I'm yet to see a compiler that does it automatically. In computer science (and generally, in mathematics), every word of the dictionary definition matter.
deleted 16y ago
[deleted]
ori_b 16y ago
It makes all the difference in the world - One can be converted by the compiler into a loop that will never use more than one function call's worth of stack, and the other must cause an unbounded amount of memory usage dependent on the input argument. In other words, it's the difference between O(n) and O(1) memory usage.
michaelcampbell 16y ago
> As such, its close enough for most purposes. Well, this purpose was to make it a tail call so that it could be optimized. Since it either is or it isn't, "close enough" to "is" is, sadly, "isn't". Which turns it from O(1) to O(n).

kylec 16y ago

It matters when you have an interpreter/compiler that does tail-call optimization. If the function is tail recursive then the recursion will only use O(1) stack space, while non-tail recursive functions will use O(n).

bitwize 16y ago

Tail recursion means that there's nothing in the continuation of the recursive call besides a return from the outer call. This means that a compiler can optimize away the saving of a new stack frame for a recursive call, because the old stack frame of the enclosing call will never be used again. That's tail-call optimization. If there's stuff in between the return from the recursive call and the return from the enclosing call (like the multiply in this factorial example) then the old stack frame will have to be kept around which means you must use unoptimized recursive calls.

DrJokepu 16y ago

Sometimes it's trivial, sometimes it's not. Sometimes it's not even possible (e.g. the naive Fibionacci algorithm). Sometimes all you need to do is to add an accumulator argument to the recursive function. Still, it's not something that can be easily automated and I'm yet to see a compiler that does it automatically. In computer science (and generally, in mathematics), every word of the dictionary definition matter.

deleted 16y ago

[deleted]

ori_b 16y ago

It makes all the difference in the world - One can be converted by the compiler into a loop that will never use more than one function call's worth of stack, and the other must cause an unbounded amount of memory usage dependent on the input argument. In other words, it's the difference between O(n) and O(1) memory usage.

michaelcampbell 16y ago

> As such, its close enough for most purposes. Well, this purpose was to make it a tail call so that it could be optimized. Since it either is or it isn't, "close enough" to "is" is, sadly, "isn't". Which turns it from O(1) to O(n).