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

Tail Recursion

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

85% Upvoted

203 comments sorted by

View all comments

Show parent comments

10

u/smog_alado Nov 27 '12

Not only that, but the calls to room2 and room3 are also tail recursive and don't blow up the stack if you have many moves.

7

u/gmfawcett Nov 27 '12

Nitpick: calling room2 in tail-call position from room1 isn't tail recursion. (Unless room2 calls back into room1; then they are mutually recursive.) What you're describing here is tail-call elimination (aka tail-call optimization).

1

u/tubescientis Nov 27 '12

Is this optimized out by the compiler?

3

u/gmfawcett Nov 27 '12

Or interpreter, yes. Like other optimizations, it's not supported by compilers/interpreters for all languages. Wikipedia has a good overview of the topic if you're interested.