Tail Call Optimisation

Tail Call Optimization is the process by which a smart compiler can make a call to a function and take no additional stack space.

The only situation in which this happens is if the last instruction executed in a function is a call to another function or the function itself.

The most common use is tail-recursion, where a recursive function written to take advantage of tail-call optimization can use constant stack space.

Normally during a recursion, the runtime needs to keep track of all the recursive calls, so that when one returns it can resume at the previous call and so on.

Keeping track of all the calls takes up space, which gets significant when the function calls itself a lot. But with tail call optimization, it can just say "go back to the beginning, only this time change the parameter values to these new ones." It can do that because nothing after the recursive call refers to those values.

Note first of all that not all languages support it.

Scheme is one of the few programming languages that guarantee in the spec that any implementation must provide this optimization (JavaScript will also, once ES6 is finalized), so here are two examples of the factorial function in Scheme:

In plain terms, TCO applies to a special case of recursion. If the last thing you do in a function is call itself (e.g. it is calling itself from the "tail" position), this can be optimized by the compiler to act like iteration instead of standard recursion.

The following example of calculating Factorial in elixir explain how Tail Call Optimization can be done.

defmodule Factorial do  
  def of(0), do: 1
  def of(n) when n > 0 do
    # Not tail call optimized
    # because recursion needs to
    # occur before multiplication
    n * of(n - 1)
  end
end

defmodule Factorial do  
  def of(0), do: 1
  def of(n), do: of(n, 1)
  def of(1, acc), do: acc 
  def of(n, acc) when n > 1 do
    # Tail call optimized
    # because recursion is the
    # last calculation
    of(n - 1, acc * n)
  end
end