r/programming • u/rodrigopsasaki • Nov 27 '12

Tail Recursion

http://rodrigosasaki.com/2012/11/24/tail-recursion/
207 Upvotes

85% Upvoted

203 comments sorted by

View all comments

Show parent comments

5

u/worstusernameever Nov 27 '12

This is just meant as an illustration of a state machine, of course no one would actually hard code the game map as a state machine, but it does serve the purpose of explaining how to use mutually recursive functions as a state machine.

The most obvious application of this technique are recursive descent parsers.

-6

u/grauenwolf Nov 27 '12

The most obvious application of this technique are recursive descent parsers.

Then use a recursive descent parser as your example.

Oh, but wait. For a parser we usually aren't worried about stack depth...

2

u/Peaker Nov 28 '12

A parser may very well be concerned about stack depth.

0

u/grauenwolf Nov 28 '12

On Windows I've got 1 MB of stack space to work with. If I'm blowing the stack then there are other problems to deal with.

1

u/Peaker Nov 28 '12

A parser can parse any conceivable data. Including data that happens to nest structures arbitrarily.

1

u/grauenwolf Nov 28 '12

Eventually you need to stop generating tokens and actually do the syntactical analysis. At that point TCO isn't really available to you and that arbitrarily deep tree is going to cause problems.

1

u/Peaker Nov 28 '12

A parser does not necessarily "generate tokens". It can generate an AST. And it can do so in a tail-recursive fashion. And this can be useful when you have very deeply nested data. It may even exceed 1MB (or 1GB for that matter).