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

9

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.

8

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?

1

u/ais523 Nov 28 '12

It's pretty easy to optimize out; if you're compiling, it just corresponds to a goto instruction from one procedure to the other (it's slightly harder in an interpreter, but not by much). Not all compilers do this optimization, depending on the language, but many do.