Endless recursion

Joe Armstrong: [erlang-questions] Tail call optimization

The correct name for the optimization used in Erlang is “last call optimization”.

Actually the tail call optimisation is done for all last calls not just recursive calls. It is sometimes called last-call optimisation. So you can write:

defmodule Foo do
  def bar() do
    baz()
  end

  def baz() do
    bar()
  end
end

which will happily recurse forever without building stack. It also works with inter-module calls.

This is the classic way of implementing state machines: you change state by calling the next state function as a tail call. You could view the Foo module as implementing a state machine with 2 states bar and baz.

Yep, in fact otp has an idiom for running a self-calling recursive loop in its own process, in such a way that it can respond to messages from other processes and keep track of some internal state: that’s really all a GenServer is. However it has extra tooling to help keep it alive and respawn to a known good state in the event of errors.

So then TCO just turns the recursive function into a loop. Thanks!

The BEAM uses Tail Call Optimization (TCO) to avoid blowing the stack.

As an example:

def fac(1), do: 1
def fac(n), do: n * fac(n -1)

is not TCO because the recursive can only be done when it is the last operation of the function. In the fac function above it needs to keep the frame to do the multiplication.

This can be re-written in a TCO fashion by using an accumulator to hold the result.

def fac(n), do: fac(n, 1)

def fac(1, result), do: result
def fac(n, result), do: fac(n - 1, n * result)

In your case the blink_forever(pid) call is the last in the function and hence will use TCO.

Elixir / Beam supports tail-call optimization.