What are optimised tail calls useful for?

Sometimes a problem can be naturally expressed recursively, but recursion seems too expensive, since usually all the stack frames have to be kept in memory.

This function defines an infinite loop in Lua:

function F() print 'yes'; return F() end

Consider this way of writing a Finite State Machine (FSM)

-- Define State A function A()
 dosomething"in state A"
 if somecondition() then return B() end
 if done() then return end
 return A()
end
-- Define State B function B()
 dosomething"in state B"
 if othercondition() then return A() end
 return B()
end
-- Run the FSM, starting in State A A()

This machine is always in either state A or B, and can run indefinitely since the tail calls are optimised into something resembling a goto.



Back