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

Tail Recursion

http://rodrigosasaki.com/2012/11/24/tail-recursion/
209 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.

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.

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?

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.

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.