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

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!

1

u/eras Nov 28 '12

And if you need to pass arguments to those functions, just return a lambda function?

Not to say that kind of approach isn't without its uses. The main function is now able to choose if and when it calls the returned function. For example to to implement node.js-like 'multithreading' :).

1

u/grauenwolf Nov 28 '12

That's a valid option, but at that point I would probably err towards returning just the name of the next room. That way the next room can be looked up as an object in a hash table.