Endless recursion

Questions / Help
1

I’m new to Elixir, and from what I read heavy use of recursion is mandatory. With that in mind, I look at this simple blink example I found:

defmodule FlightController do
  use Application

  @blink_duration 150 # ms
  @led_pin 18
  @gpio_on 1
  @gpio_off 0

  def start(_type, _args) do
    {:ok, pid} = Gpio.start_link(@led_pin, :output)

    spawn fn -> blink_forever(pid) end

    {:ok, self}
  end

  def blink_forever(pid) do
    Gpio.write(pid, @gpio_on)
    :timer.sleep @blink_duration
    Gpio.write(pid, @gpio_off)
    :timer.sleep @blink_duration

    blink_forever(pid)
  end
end

In my non-Elixir experience, recursive programs build a new stack with each call and release it when the last recursive call returns. You can’t do it forever because you’ll be out of stack space. So, this example couldn’t work on another platform. I have not run it but I’m guessing it does work.

My question, then, is, how does Elixir / BEAM implement recursion?

3 Likes
2

Elixir / Beam supports tail-call optimization.

2 Likes
3

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.

4 Likes
4

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

2 Likes
5

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.

1 Like
6

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.

7 Likes
7

Joe Armstrong: [erlang-questions] Tail call optimization

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

6 Likes