2 ms·
Tali recursion should be equivalent to a loop, if the language compiler/implementation offers TCE/TCO. C does not guarantee this. But I'll also point out, tail
by Jtsummers 10y ago
Tali recursion should be equivalent to a loop, if the language compiler/implementation offers TCE/TCO. C does not guarantee this.
But I'll also point out, tail recursion could be statically analyzed in the same way that you would with a for loop (for the purpose of Rule 2). As long as it is structured in a way that demonstrates that:
1) Forward progress is always being made (that is, there's an iteration/index parameter that always increases/decreases monotonically) towards a bound:
void f(state,n)
{
if(n > MAX) return;
f(g(state),n+1);
}
2) There's a single entry point which initiates the recursion (loop) with 0 (or MAX if you're decrementing, or whatever):
void start(state)
{
f(state,0);
}
Both can be demonstrated (with code structured like the above) statically.
- AnimalMuppet 10y agoAll true. A modified C compiler could be built that would do TCO. But, for this kind of application, it would mean that you'd have to re-validate your compiler, so that's pretty much not going to happen.
- Jtsummers 10y agoLooking it up, it seems that GCC (at least) presently does do (at some optimization levels) tail call elimination. Others probably do as well. I guess I've never looked it up because it was never relevant (if I'm using C, I might as well use for loops, they're at least as clear as the equivalent tail recursive function).