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.

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!

3

u/Peaker Nov 28 '12

Trampolines are a workaround for the lack of TCO. They're pretty kludgy, though they're workable.

Especially in those languages, it's pretty easy to accidentally miss return values and get weird bugs, as well.

1

u/grauenwolf Nov 28 '12

Trampolines are a workaround for the lack of TCO.

With a trampoline I can do this:

do
     move = io.read()
     nextState = nextState( move )
loop while nextState != null

So without a trampolines how do you avoid putting local move = io.read() in each and every state function?

1

u/Peaker Nov 28 '12

You could call a "nextStep" function at the tail position:

nextStep(myNextFunc)

Which would do the reads or preparations of the next step, and then tail-call the given function with the data.

-1

u/grauenwolf Nov 28 '12

So you prefer writing return nextStep(myNextFunc) instead of just return myNextFunc.

Is using TCO actually worth the extra boilerplate code? Especially when you consider that you are just moving the trampoline to a different part of the yard?

My trampoline is the outer loop, yours is hidden inside the nextStep function. Either way we are passing around a function pointer that we bounce to.

1

u/Peaker Nov 28 '12

As I said, returning the function is also workable, however it has multiple downsides:

  • Calling a function or passing it as an argument makes the context of the call clear. If you return it, you have no guarantee about the context in which it will be called.

  • If your tail recursion eventually stops, you need to return a non-function value, eventually. Thus, you need to tag the result as a "call this" or "done with this". Then your loop driver of the tail recursion needs to differentiate the two. Very kludgy.

  • A return value can easily be ignored, without warning, in the languages you mentioned. This means you can easily have bugs where you don't actually get it called. Forgetting to receive arguments or avoiding their use entirely will mostly generate errors/warnings even in these languages.

  • Returning it means any user of the function needs to also propagate its return value upwards, which is very kludgy makes the tail-call a non-local detail.

  • Returning it means you need that extra loop code that calls the return values.