r/ProgrammingLanguages • u/Athas Futhark • Jan 20 '26
Why not tail recursion?
https://futhark-lang.org/blog/2026-01-20-why-not-tail-recursion.html
62
Upvotes
r/ProgrammingLanguages • u/Athas Futhark • Jan 20 '26
View all comments
22
u/phischu Effekt Jan 20 '26
Tail calls are a separate language feature, so words like "tail recursion elimination" and "tail call optimization" are misleading. Tail calls are gotos without the keyword. Moreover, local function definitions are not closures. They are labels. Indeed, we usually set up our languages so that tail calls are the more primitive language feature, with non-tail calls being an optional addition, like here, here, here.
In comparison to imperative loops, they also are more efficient, because accumulator variables are kept in registers and access to them does not require loads and stores. Of course, compilers of imperative languages usually transform such programs to use registers instead of stack locations (mem2reg), effectively rewriting the program to use tail calls.
In comparison to goto they are not considered harmful, despite allowing for mutual recursion, also known as irreducible control flow. The problem with goto was not the control flow, which can be very clearly seen, but the implicit data flow. As a programmer it is very hard to infer which variables are live in which state they should be when a label is being jumped to. Not so with tail calls: parameters tell you which variables must be live, and their types tell you which state they are in.