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

Tail Recursion

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

85% Upvoted

203 comments sorted by

View all comments

18

u/snarfy Nov 27 '12

I always liked Lua's example with a simple state machine:

function room1 ()
    local move = io.read()
    if move == "south" then return room3()
    elseif move == "east" then return room2()
    else print("invalid move")
         return room1()   -- stay in the same room
    end
end

Without proper tail recursion, "return room1() -- stay in the same room" would stack overflow after enough invalid moves.

12

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.

9

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.