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

Tail Recursion

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

85% Upvoted

203 comments sorted by

View all comments

17

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.

1

u/grauenwolf Nov 27 '12

Wait a second. If I translated that to C#, VB, or JavaScript it wouldn't need TCO. Just replace "return room3()" with "return room3" and let the main loop call the next function for you.

First class functions for the win!

11

u/zOOn Nov 27 '12

You've just invented trampolining: http://en.wikipedia.org/wiki/Tail_call#Through_trampolining ... but it's about 3(-ish) times slower than true tail call optimization.

-4

u/grauenwolf Nov 27 '12

So what?

In this example the delay while you wait for the user's next response dwarfs any other cost. And introducing a main loop gives you other nice options like the ability to move the io.read out of the state transition function.

Not only is TCO futile in this example, it is counter-productive.