Which languages support tail recursion optimization?

Question

which languages support tail recursion optimization?

Answer 1

Scheme, Haskell, ...

Answer 2

The F# compiler converts directly recursive functions into loops, and all calls in tail position emit code with the CLR .tail opcode, so that you can write e.g. mutually recursive functions that need not consume the stack.

Answer 3

I would assume that tail recursion would be an implementation detail of specific compilers.

Answer 4

Without compiling a comprehensive list of languages:

• if you need it, it's there
• if it's not there, you don't need it

Typically the languages that optimise tail recursion are languages in which tail recursion is the commonest way to achieve iteration.

In Scheme, you iterate by recursing. Therefore, the language standard requires tail recursion optimisation - otherwise iterating over very long lists would be impossible.

In most procedural languages, you iterate with for or while - tail recursion optimization is no help there. In languages that provide these constructs, you wouldn't typically choose to use recursion for problems that could be solved with tail-recursion.

Answer 5

64-bit .Net supports tail recursion optimization, but you shouldn't make dependencies on it: Tail Call JIT conditions.

The 2nd part of that post goes into much more detail: Enter, Leave, Tailcall Hooks Part 2: Tall tales of tail calls

Answer 6

SML and OCaml also

Dylan also asks the implementatin to be properly tail recusive.

One interesting point though is that simply adding a type signature to a function could render a function non-tail recursive.

define function count(i :: <integer>)
  if (i == 0)
    i ;
  else
    count(i - 1) ;
  end
end

is tail recusive, but

define function count(i :: <integer>) => (sum :: <integer>)
  if (i == 0)
    i ;
  else
    count(i - 1) ;
  end
end

is not. The reason is that adding the signature to the function requires the compiler to add code after the recursive call to check the type signature. This makes the function call no longer tail recursive.

Answer 7

This isn't a laguage question, it's a compiler question. I don't know of any language that has some syntactic element in it that prevents a compiler from optimizing that way.

For example, I think any compiler that uses the gcc back end supports tail recursion elimination at -O3

Answer 8

Scheme, Lua, Standard ML, Mozart/Oz.

These languages promise that such code

return some_function(params);

reuses current stack frame.

Answer 9

Erlang is another.

Answer 10

LOGO supports tail recursion optimization.

Answer 11

Perl with goto systax:

From perldoc:

"The goto-&NAME form is quite different from the other forms of goto. In fact, it isn't a goto in the normal sense at all, and doesn't have the stigma associated with other gotos. Instead, it exits the current subroutine (losing any changes set by local()) and immediately calls in its place the named subroutine using the current value of @. This is used by AUTOLOAD subroutines that wish to load another subroutine and then pretend that the other subroutine had been called in the first place (except that any modifications to @ in the current subroutine are propagated to the other subroutine.) After the goto, not even caller will be able to tell that this routine was called first."