Things you can’t do in Rust: tail recursion

Things you can’t do in Rust: tail recursion(medium.com)

4 points by andrew-lucker 8 years ago | 5 comments

stmw 8 years ago |

Do people often rely on tail-recursion for real-world programs? Before anyone wonders if I know what it is, yes, I do, and yes, I've used it appropriately, but it feels so... academic.

andrew-lucker 8 years ago | |

There is a whole style of programming dedicated to tail-recursion called Continuation Passing Style. It is not usually useful for programmers directly to use, because it is so complicated to read/write, but it is very useful for compilers to generate code in CPS.

If you wanted to, for example, write a new experimental functional language and reuse part of the Rust compiler to sanity check and generate the executable, then tail-recursion would be really important.

Similarly, if you create something like a parser generator and don't have tail recursion optimization, then you are going to run out of stack space before being able to parse stuff. So, there are lots of practical applications that depend on this feature too.

stmw 8 years ago | | |

Ah, thanks, makes good sense. I think of "write a new experimental functional language and reuse part of the Rust compiler" as somewhat "academic", but matter of taste. But for production parsers, I think I'd try to avoid using the stack or limit the stack, anyway.

fulafel 8 years ago |

This example is just infinite recursion. You will get a similar result in, say, Python.

Maybe the author wanted to say that Rust (currently) doesn't perform an optimization called tail call elimination that would make this program consume zero stack, which would make it hang instead of erroring out.

Some languages (like Scheme) are specified to optimize tail calls, so you can rely on this behaviour there.

steveklabnik 8 years ago | |

To be clear about this, LLVM will sometimes do TCO. But Rust doesn't guarantee it. We have reserved a keyword to make this happen sometimes in the future, possibly.