Recursion, tail calls and fair measurement

Adding up the numbers 1 to 10,000,000 with a function that calls itself held 20,000,019 words of stack, 160 MB, at its deepest point; the same sum written with a tail call needed 19 words, whatever the count. Elixir has no loop that counts a variable up, so every loop is a function that calls itself, and the way it calls itself decides what it costs.

Below, you will write recursive functions with a base case and an accumulator, watch one stack grow and another stay flat, see a process killed by its own stack, find the one place where a tail call is required, and measure two versions in a way that does not fool you. Every output here comes from Elixir 1.20.4 on Erlang/OTP 29.1.1.

A recursive function needs a base case and a smaller call

Elixir’s data never changes, so a loop cannot step a counter through a list. The Elixir guide names what it does instead: “Recursion and tail call optimization are an important part of Elixir and are commonly used to create loops.” A recursive function handles the simplest input in one clause and, in another, does one step of the work and calls itself on what is left. Bill.total/1 adds up a bill’s prices in rupees:

# A bill's prices in rupees, added up by a function that calls itself.
defmodule Bill do
  # The base case: an empty bill adds up to 0.
  def total([]), do: 0
  # The recursive case: the first price, plus the total of the rest.
  def total([price | rest]), do: price + total(rest)

  # The same function without its base case.
  def total_no_base([price | rest]), do: price + total_no_base(rest)
end

The first clause matches the empty list and returns 0: that is the base casebase case: The clause of a recursive function that returns without calling the function again, such as total([]) returning 0. Every chain of recursive calls has to reach one, or it fails with FunctionClauseError or never ends.. The second matches a list with at least one price, splits it into price and rest, as [head | tail] did in the lists lesson, and returns price + total(rest). Each call works on a list one item shorter, so the calls must reach the empty list. Try it in IEx:

from session import shell

# Bill.total/1 in IEx, then the same function without its base case.
shell([
    "Bill.total([120, 45, 300])",
    "Bill.total([])",
    "Bill.total_no_base([120, 45, 300])",
    "System.halt()",
], command="iex bill.ex")

$ iex bill.ex
Erlang/OTP 29 [erts-17.1] [source] [64-bit] [smp:18:18] [ds:18:18:10] [async-threads:1] [jit]

Interactive Elixir (1.20.4) - press Ctrl+C to exit (type h() ENTER for help)
iex(1)> Bill.total([120, 45, 300])
465
iex(2)> Bill.total([])
0
iex(3)> Bill.total_no_base([120, 45, 300])
** (FunctionClauseError) no function clause matching in Bill.total_no_base/1

    The following arguments were given to Bill.total_no_base/1:

        # 1
        []

    bill.ex:9: Bill.total_no_base/1
    iex:3: (file)
iex(3)> System.halt()

Bill.total([120, 45, 300]) returned 465, and the empty bill returned 0. total_no_base/1 is the same function without the clause for []: it worked through the three prices, called itself with the empty rest, which no clause matches, and raised FunctionClauseError with [] as its argument. Step through the call that worked, down to the base case and back up:

Each addition waits for the call below it: 120 + total([45, 300]) cannot add until total([45, 300]) has returned. This shape, with work left to do after the recursive call, is body recursionbody recursion: Recursion with work left to do after the recursive call returns, as in price + total(rest). Each waiting call keeps a frame on the process's stack until the calls below it have returned.. It is the way most people first write a recursive function, and it reads like the definition: the total is the first price plus the total of the rest.

A tail call leaves nothing to do, so the stack stays flat

Every call that has not returned yet keeps a frame on the process’s stack: what it still has to do, and the values it needs to do it. 120 + total([45, 300]) keeps 120 there until the call below returns. A call that is the last thing a function does needs no such frame, so the BEAM reuses the caller’s frame for it: that is a tail calltail call: A call that is the last thing a function does, so nothing is left to do when it returns. The BEAM reuses the caller's stack frame for it, so a function that calls itself only this way runs in a stack of fixed size.. To make the recursive call the last thing a clause does, carry the result so far in an extra argument, an accumulatoraccumulator: An extra argument that carries the result built so far through each recursive call, such as a running total. The base case returns it; a list built in one by prepending comes out in reverse order.:

# The bill again, added up and converted by tail-recursive functions that carry
# their result in an accumulator.
defmodule BillAcc do
  # The running total travels in acc, so the recursive call is the last thing
  # each clause does.
  def total(prices), do: total(prices, 0)

  defp total([], acc), do: acc
  defp total([price | rest], acc), do: total(rest, acc + price)

  # Prepending each new item to the accumulator builds the list back to front.
  def in_paise_backwards(prices), do: in_paise(prices, [])

  # The fix: reverse the finished list once.
  def in_paise(prices), do: Enum.reverse(in_paise(prices, []))

  defp in_paise([], acc), do: acc
  defp in_paise([price | rest], acc), do: in_paise(rest, [price * 100 | acc])
end

from session import shell

# The tail-recursive total, then a list built in an accumulator, without and with the reverse.
shell([
    "BillAcc.total([120, 45, 300])",
    "BillAcc.in_paise_backwards([120, 45, 300])",
    "BillAcc.in_paise([120, 45, 300])",
    "System.halt()",
], command="iex bill_acc.ex")

$ iex bill_acc.ex
Erlang/OTP 29 [erts-17.1] [source] [64-bit] [smp:18:18] [ds:18:18:10] [async-threads:1] [jit]

Interactive Elixir (1.20.4) - press Ctrl+C to exit (type h() ENTER for help)
iex(1)> BillAcc.total([120, 45, 300])
465
iex(2)> BillAcc.in_paise_backwards([120, 45, 300])
[30000, 4500, 12000]
iex(3)> BillAcc.in_paise([120, 45, 300])
[12000, 4500, 30000]
iex(4)> System.halt()

BillAcc.total/1 starts total/2 with an accumulator of 0, and each clause adds one price to it on the way down, so the base case already holds the answer, 465, and returns it. Nothing waits for any call. Step through both versions side by side and count the frames each one keeps:

An accumulator has one catch for lists: each new item is prepended, so the list comes out backwards. in_paise_backwards/1 returned [30000, 4500, 12000], the last price first. in_paise/1 reverses the finished list once with Enum.reverse/1 and returns [12000, 4500, 30000]. The reverse is one more pass over the list, far cheaper than adding each item at the end with ++, as the lists lesson measured: prepend, then reverse once.

How much does a waiting frame cost? depth.exs adds up 1 to n both ways, each in a new process, and records the size of that process’s stack, in words, at the base case, where it is deepest:

# Adds up 1 to n twice, by body recursion and by tail recursion, each in a new
# process, and records how deep the stack of that process got.
defmodule Sum do
  # Body recursion: n + ... waits until body(n - 1) has returned.
  def body(0), do: deepest(0)
  def body(n), do: n + body(n - 1)

  # Tail recursion: the call is the last thing the clause does.
  def tail(n), do: tail(n, 0)
  defp tail(0, acc), do: deepest(acc)
  defp tail(n, acc), do: tail(n - 1, acc + n)

  # Called at the base case, where the stack is as deep as it gets: keeps the
  # size of the stack, in words, in the process dictionary.
  defp deepest(value) do
    {:stack_size, words} = Process.info(self(), :stack_size)
    Process.put(:deepest, words)
    value
  end
end

defmodule Main do
  # Runs fun in a new process; returns its result and the deepest stack it saw.
  def measure(fun) do
    task = Task.async(fn -> {fun.(), Process.get(:deepest)} end)
    Task.await(task, :infinity)
  end

  def run do
    IO.puts("         n             sum  body: stack words  tail: stack words")

    for n <- [10, 1_000, 1_000_000, 10_000_000] do
      {sum, body_words} = measure(fn -> Sum.body(n) end)
      {^sum, tail_words} = measure(fn -> Sum.tail(n) end)

      IO.puts(
        pad(n, 10) <> pad(sum, 16) <> pad(body_words, 19) <> pad(tail_words, 19)
      )
    end

    IO.puts("one word is #{:erlang.system_info(:wordsize)} bytes")
  end

  defp pad(number, width), do: number |> Integer.to_string() |> String.pad_leading(width)
end

Main.run()

from session import run

run("""
elixir depth.exs
""")

$ elixir depth.exs
         n             sum  body: stack words  tail: stack words
        10              55                 39                 19
      1000          500500               2019                 19
   1000000    500000500000            2000019                 19
  10000000  50000005000000           20000019                 19
one word is 8 bytes

The body version’s stack grew by exactly 2 words for each waiting call, 2n + 19 in all: 2,000,019 words for a million numbers and 20,000,019 words, 160 MB with 8-byte words, for ten million. The tail version used 19 words for every n.

The stack is memory, and a process can run out of it

The body version reached ten million waiting calls without a stack overflow, because a BEAM process has no fixed stack size. The Efficiency Guide describes the first memory of a new process as 233 words “for the heap area (which includes the stack)”, and the stack grows into that memory as the heap does. So the limit is memory: the computer’s, or a limit set on the process. Process.flag(:max_heap_size, …) sets one, in words, and the erlang documentation says it counts “all generational heaps, the process stack” and the extra memory a garbage collection needs. A process that goes over is killed. limit.exs adds up 1 to n in processes with such a cap:

# Adds up 1 to n in a process whose memory is capped, three ways: body recursion,
# tail recursion and Enum.reduce/3 over a range.
defmodule Sum do
  def body(0), do: 0
  def body(n), do: n + body(n - 1)

  def tail(n), do: tail(n, 0)
  defp tail(0, acc), do: acc
  defp tail(n, acc), do: tail(n - 1, acc + n)

  def reduce(n), do: Enum.reduce(1..n//1, 0, &+/2)
end

defmodule Main do
  # Runs Sum.<name>(n) in a new process whose heap, stack included, may hold at
  # most `cap` words; a process that goes over is killed.
  def capped(name, n, cap) do
    parent = self()

    {pid, ref} =
      spawn_monitor(fn ->
        Process.flag(:max_heap_size, %{size: cap, kill: true, error_logger: false})
        send(parent, {:sum, apply(Sum, name, [n])})
      end)

    receive do
      {:DOWN, ^ref, :process, ^pid, :normal} ->
        receive do
          {:sum, sum} -> "returned #{sum}"
        end

      {:DOWN, ^ref, :process, ^pid, reason} ->
        "stopped with reason #{inspect(reason)}"
    end
  end

  def run do
    for n <- [100_000, 1_000_000], name <- [:body, :tail, :reduce] do
      IO.puts("cap 1000000, n = #{n}, #{name}: #{capped(name, n, 1_000_000)}")
    end

    for cap <- [2_100_000, 4_000_000] do
      IO.puts("cap #{cap}, n = 1000000, body: #{capped(:body, 1_000_000, cap)}")
    end
  end
end

Main.run()

from session import run

run("""
elixir limit.exs
""")

$ elixir limit.exs
cap 1000000, n = 100000, body: returned 5000050000
cap 1000000, n = 100000, tail: returned 5000050000
cap 1000000, n = 100000, reduce: returned 5000050000
cap 1000000, n = 1000000, body: stopped with reason :killed
cap 1000000, n = 1000000, tail: returned 500000500000
cap 1000000, n = 1000000, reduce: returned 500000500000
cap 2100000, n = 1000000, body: stopped with reason :killed
cap 4000000, n = 1000000, body: returned 500000500000

Under a cap of 1,000,000 words, all three versions returned 5,000,050,000 for n = 100,000, when the body version’s stack held about 200,000 words. For n = 1,000,000 the body version was killed: its stack would have needed 2,000,019 words. The tail version and Enum.reduce/3 over the range returned 500,000,500,000 in a few words of stack.

The last two lines show how the cap counts. A cap of 2,100,000 words, just above the stack’s 2,000,019, still killed the body version, and 4,000,000 was enough. The check happens when the process collects garbage, and it counts the room the collection needs as well as the heap and the stack it already has, so a cap must leave room for well over the stack itself.

When the tail call matters, and when it does not

The measured stacks make tail recursion look always better, but the Efficiency Guide says otherwise for functions that build lists: in modern versions of Erlang, “there is usually not much difference in performance” between a body-recursive list function and a tail-recursive one that reverses the list at the end. The body version keeps a frame for each item; the tail version builds the list backwards and then again in the reverse. So the guide’s advice is to write the clearer one, and “In the time-critical parts of your code, measure before rewriting your code.” For a function that returns one value, such as a sum or a count, it draws the line the other way: a tail-recursive function that builds no list “runs in constant space”, as depth.exs showed.

One case leaves no choice. A process that waits for messages runs a loop that calls itself after each message, and the guide is direct: “The main (outer) loop for a process must be tail-recursive.” The easy way to break that rule by accident is try. loop.exs runs three versions of a counter process and asks each for its stack size:

# Three versions of a counter process that adds up the numbers it is sent. After
# a number of messages, each one is asked for the size of its stack, in words.
defmodule Counter do
  # The recursive call is the last thing the loop does: a tail call.
  def plain(count) do
    receive do
      {:add, n} -> plain(count + n)
      {:stack_size, from} -> report(from, &plain/1, count)
    end
  end

  # The same loop inside try, so that a bad message such as {:add, "5"} cannot
  # stop it. try has to stay ready to rescue an error raised by the call inside
  # it, so the recursive call is no longer a tail call.
  def guarded(count) do
    try do
      receive do
        {:add, n} -> guarded(count + n)
        {:stack_size, from} -> report(from, &guarded/1, count)
      end
    rescue
      ArithmeticError -> guarded(count)
    end
  end

  # The fix: rescue only the addition, then make the call outside try.
  def fixed(count) do
    receive do
      {:add, n} -> fixed(add(count, n))
      {:stack_size, from} -> report(from, &fixed/1, count)
    end
  end

  defp add(count, n) do
    count + n
  rescue
    ArithmeticError -> count
  end

  defp report(from, loop, count) do
    send(from, Process.info(self(), :stack_size))
    loop.(count)
  end
end

defmodule Main do
  # Starts a counter, sends it `messages` numbers, then asks for its stack size.
  def stack_after(loop, messages) do
    pid = spawn(fn -> loop.(0) end)
    for _ <- 1..messages, do: send(pid, {:add, 1})
    send(pid, {:stack_size, self()})

    receive do
      {:stack_size, words} ->
        Process.exit(pid, :kill)
        words
    end
  end

  def run do
    loops = [plain: &Counter.plain/1, guarded: &Counter.guarded/1, fixed: &Counter.fixed/1]

    for {name, loop} <- loops, messages <- [1_000, 100_000] do
      IO.puts("#{name}, after #{messages} messages: #{stack_after(loop, messages)} words of stack")
    end
  end
end

Main.run()

from session import run

run("""
elixir loop.exs
""")

$ elixir loop.exs
plain, after 1000 messages: 6 words of stack
plain, after 100000 messages: 6 words of stack
guarded, after 1000 messages: 3009 words of stack
guarded, after 100000 messages: 300009 words of stack
fixed, after 1000 messages: 6 words of stack
fixed, after 100000 messages: 6 words of stack

The plain loop held 6 words of stack after 100,000 messages. guarded/1, the same loop wrapped in try so that a bad message cannot stop it, grew by 3 words a message, to 300,009 words, and it would keep growing for as long as it runs. The documentation of try/1 gives the reason: “Calls inside try/1 are not tail recursive since the VM needs to keep the stacktrace in case an exception happens.” fixed/1 rescues only the addition, in a function of its own, and makes the recursive call outside try: 6 words again.

Answer the two questions about a function of your own to see which way of writing it fits:

In short: let Enum build lists and compute sums when it can, write whichever recursion is clearer for a list builder on input of ordinary size, use an accumulator for a value computed over input that can grow large, and always make a process’s loop a tail call.

Measure fairly before you rewrite

The guide’s “measure before rewriting” needs a measurement that measures the code. The quick way is to time each version with :timer.tc/1 in the process you are already in. naive_bench.exs does that for the tail and the body version of Double, then does the same again, all in one process, on the same 1,000,000 numbers:

# Three ways to double every number of a list, compared by the two benchmarks.
defmodule Double do
  # Body recursion: each new cell waits for the doubled rest of the list.
  def body([]), do: []
  def body([n | rest]), do: [n * 2 | body(rest)]

  # Tail recursion: build the list back to front, then reverse it once.
  def tail(list), do: list |> tail([]) |> Enum.reverse()

  defp tail([], acc), do: acc
  defp tail([n | rest], acc), do: tail(rest, [n * 2 | acc])

  # What you would usually write.
  def enum(list), do: Enum.map(list, &(&1 * 2))
end

# The quick way to compare Double.tail/1 and Double.body/1: time each one once,
# then both again, in the script's own process, on the same 1,000,000 numbers.
Code.require_file("double.ex", __DIR__)

defmodule Main do
  def run do
    numbers = Enum.to_list(1..1_000_000)

    for round <- [1, 2] do
      [tail, body] = for name <- [:tail, :body], do: time(name, numbers)
      IO.puts("round #{round}: tail #{ms(tail)}, body #{ms(body)}; #{verdict(tail, body)}")
    end
  end

  # One measurement, in microseconds.
  defp time(name, numbers) do
    {micros, _doubled} = :timer.tc(fn -> apply(Double, name, [numbers]) end)
    micros
  end

  defp verdict(tail, body) when tail > body, do: "body looks #{ratio(tail, body)} times as fast"
  defp verdict(tail, body), do: "tail looks #{ratio(body, tail)} times as fast"

  defp ratio(a, b), do: :erlang.float_to_binary(a / b, decimals: 1)
  defp ms(micros), do: :erlang.float_to_binary(micros / 1000, decimals: 1) <> " ms"
end

Main.run()

from session import run

run("""
elixir naive_bench.exs
""")

$ elixir naive_bench.exs
round 1: tail 67.7 ms, body 16.4 ms; body looks 4.1 times as fast
round 2: tail 61.9 ms, body 14.3 ms; body looks 4.3 times as fast

Both rounds tell the same story: the body version about four times as fast as the tail version, 16.4 ms against 67.7 ms in round 1. The fair measurement below shows that the story is wrong. All four runs shared one process, whose heap already held the million numbers and kept what each run left behind for the next, so each time depended on the state of that heap as much as on the code. The Benchmarking page of the Efficiency Guide warns that when tests share a process, “the later tests start out with larger heap sizes and therefore probably do fewer garbage collections”. Its advice is to run each test in “its own, newly created Erlang process”, several times, and to note the shortest time. fair_bench.exs does that, and reports the median as well, the typical run, which one slow run cannot move far:

# A fairer comparison: every run in a new process, 21 runs of each version, and
# the median and the fastest run reported; then the same with each process given
# a heap of 4,000,000 words from the start, so that it never has to grow.
Code.require_file("double.ex", __DIR__)

defmodule Bench do
  @runs 21

  # One run: a new process times one version on the numbers and sends the time
  # back. The numbers are copied into the process when it starts, before the clock.
  def once(name, numbers, spawn_options) do
    parent = self()

    {pid, ref} =
      :erlang.spawn_opt(
        fn ->
          {micros, _doubled} = :timer.tc(fn -> apply(Double, name, [numbers]) end)
          send(parent, {self(), micros})
        end,
        [:monitor | spawn_options]
      )

    receive do
      {^pid, micros} ->
        receive do
          {:DOWN, ^ref, :process, ^pid, _reason} -> micros
        end
    end
  end

  # The median and the fastest of @runs runs, in microseconds.
  def summary(name, numbers, spawn_options) do
    times = Enum.sort(for _ <- 1..@runs, do: once(name, numbers, spawn_options))
    {Enum.at(times, div(@runs, 2)), hd(times)}
  end
end

defmodule Main do
  def run do
    otp = File.read!(Path.join([:code.root_dir(), "releases", System.otp_release(), "OTP_VERSION"]))

    IO.puts(
      "Elixir #{System.version()} on Erlang/OTP #{String.trim(otp)}, " <>
        "#{:erlang.system_info(:system_architecture)}, #{System.schedulers_online()} schedulers"
    )

    IO.puts("21 runs of each, each run in a new process: median (fastest)")
    IO.puts("version          default heap        heap of 4,000,000 words")
    numbers = Enum.to_list(1..1_000_000)

    for {name, label} <- [body: "body", tail: "tail + reverse", enum: "Enum.map"] do
      {median, fastest} = Bench.summary(name, numbers, [])
      {big_median, big_fastest} = Bench.summary(name, numbers, min_heap_size: 4_000_000)

      IO.puts(
        String.pad_trailing(label, 17) <>
          String.pad_trailing("#{ms(median)} (#{ms(fastest)})", 20) <>
          "#{ms(big_median)} (#{ms(big_fastest)})"
      )
    end
  end

  defp ms(micros), do: :erlang.float_to_binary(micros / 1000, decimals: 1) <> " ms"
end

Main.run()

from session import run

run("""
/usr/sbin/sysctl -n machdep.cpu.brand_string
elixir fair_bench.exs
""")

$ /usr/sbin/sysctl -n machdep.cpu.brand_string
Apple M5 Pro
$ elixir fair_bench.exs
Elixir 1.20.4 on Erlang/OTP 29.1.1, aarch64-apple-darwin, 18 schedulers
21 runs of each, each run in a new process: median (fastest)
version          default heap        heap of 4,000,000 words
body             24.9 ms (21.5 ms)   8.8 ms (8.2 ms)
tail + reverse   28.8 ms (25.9 ms)   7.3 ms (6.2 ms)
Enum.map         35.8 ms (32.7 ms)   11.1 ms (10.5 ms)

With every run in a new process, the medians were 24.9 ms for the body version and 28.8 ms for the tail version: the tail version about 16 % slower, not four times. The second column gives each process a heap of 4,000,000 words from the start, big enough that it hardly collects garbage during the run; the erlang documentation says a larger minimum heap “can speed up some processes because less garbage collection is done”. Every version became three to four times as fast, and the order changed: the tail version, at 7.3 ms, was now the fastest.

So most of the time in the first column was garbage collection, and the style of the recursion moved the result by a few milliseconds either way. Enum.map/2, which calls the function it is given once for every number, was the slowest in both columns, at 35.8 ms and 11.1 ms. That is the guide’s advice in numbers: write the clearer version, and if a function is slow, measure in new processes before rewriting it.

Practise: walk a tree

A binary tree here is either nil, the empty tree, or a tuple {left, value, right} whose left and right are trees. Write three functions for it: depth/1, the number of levels, flatten/1, the values from left to right, and sum/1, which must be tail-recursive. A tree has two subtrees, so a tail-recursive walk cannot just call itself on “the rest”: sum/2 keeps a list of the subtrees still to visit, an explicit stack, and the total so far. Copy the two files into an empty folder:

# A binary tree is either nil (empty) or a tuple {left, value, right}, where left
# and right are trees. Write the three functions; each starter returns a
# placeholder.
defmodule Tree do
  # The number of levels: 0 for nil, 1 for a tree of one node.
  def depth(_tree), do: 0

  # The values from left to right: the left subtree's, the node's own, then the
  # right subtree's.
  def flatten(_tree), do: []

  # The sum of the values, tail-recursive: sum/2 keeps a list of the subtrees
  # still to visit, and the total so far.
  def sum(tree), do: sum([tree], 0)

  def sum(_pending, total), do: total
end

Code.require_file("tree.ex", __DIR__)
ExUnit.start(seed: 0)

defmodule TreeTest do
  use ExUnit.Case

  #        4
  #      /   \
  #     2     5
  #    / \
  #   1   3
  @tree {{{nil, 1, nil}, 2, {nil, 3, nil}}, 4, {nil, 5, nil}}

  # A tree that is one long chain: each node's right subtree is the next node.
  defp chain(n), do: Enum.reduce(1..n//1, nil, fn value, rest -> {nil, value, rest} end)

  test "an empty tree" do
    assert Tree.depth(nil) == 0
    assert Tree.flatten(nil) == []
    assert Tree.sum(nil) == 0
  end

  test "depth counts the levels of the longest path" do
    assert Tree.depth({nil, 7, nil}) == 1
    assert Tree.depth(@tree) == 3
  end

  test "flatten lists the values from left to right" do
    assert Tree.flatten(@tree) == [1, 2, 3, 4, 5]
  end

  test "sum adds every value" do
    assert Tree.sum(@tree) == 15
  end

  test "sum/2 takes the subtrees still to visit and the total so far" do
    assert Tree.sum([], 7) == 7
    assert Tree.sum([nil, {nil, 5, nil}], 1) == 6
    assert Tree.sum([{nil, 2, nil}, @tree], 0) == 17
  end

  test "a chain of 1,000,000 nodes" do
    tree = chain(1_000_000)
    assert Tree.depth(tree) == 1_000_000
    assert Tree.sum(tree) == 500_000_500_000
    assert Tree.flatten(tree) |> Enum.take(3) == [1_000_000, 999_999, 999_998]
  end
end

Run elixir tree_test.exs. The starter returns placeholders, so only the test of the empty tree passes:

from session import run

# The tests against the starter, whose functions return placeholders.
run("""
cd practice
!elixir tree_test.exs
""")

$ cd practice
$ elixir tree_test.exs
Running ExUnit with seed: 0, max_cases: 36

.

  1) test depth counts the levels of the longest path (TreeTest)
     tree_test.exs:23
     Assertion with == failed
     code:  assert Tree.depth({nil, 7, nil}) == 1
     left:  0
     right: 1
     stacktrace:
       tree_test.exs:24: (test)



  2) test flatten lists the values from left to right (TreeTest)
     tree_test.exs:28
     Assertion with == failed
     code:  assert Tree.flatten(@tree) == [1, 2, 3, 4, 5]
     left:  []
     right: [1, 2, 3, 4, 5]
     stacktrace:
       tree_test.exs:29: (test)



  3) test sum adds every value (TreeTest)
     tree_test.exs:32
     Assertion with == failed
     code:  assert Tree.sum(@tree) == 15
     left:  0
     right: 15
     stacktrace:
       tree_test.exs:33: (test)



  4) test sum/2 takes the subtrees still to visit and the total so far (TreeTest)
     tree_test.exs:36
     Assertion with == failed
     code:  assert Tree.sum([nil, {nil, 5, nil}], 1) == 6
     left:  1
     right: 6
     stacktrace:
       tree_test.exs:38: (test)



  5) test a chain of 1,000,000 nodes (TreeTest)
     tree_test.exs:42
     Assertion with == failed
     code:  assert Tree.depth(tree) == 1_000_000
     left:  0
     right: 1000000
     stacktrace:
       tree_test.exs:44: (test)


Finished in 0.1 seconds (0.03s on load, 0.00s async, 0.1s sync)

Result: 1/6 passed
Failed: 5 tests
[exit status 2]

depth/1 is body recursion: one more than the deeper of the two subtrees, with nil as the base case at 0. For sum/2, take the first tree off the list of pending trees: nil adds nothing, and a node adds its value and puts both of its subtrees on the front of the list, so the call to sum/2 is the last thing every clause does. For flatten/1, avoid flatten(left) ++ [value | flatten(right)], whose ++ copies the left part at every level; pass an accumulator instead, flatten the right subtree into it first and prepend the value, so the list comes out in order without a reverse. The last test walks a chain of 1,000,000 nodes. A finished version passes all six tests:

from session import run

# The same tests against a finished Tree module.
run("""
cd finished
cp ../practice/tree_test.exs .
elixir tree_test.exs
""")

$ cd finished
$ cp ../practice/tree_test.exs .
$ elixir tree_test.exs
Running ExUnit with seed: 0, max_cases: 36

......
Finished in 0.1 seconds (0.03s on load, 0.00s async, 0.1s sync)

Result: 6 passed

Then test yourself: the self-check asks about the five ideas of this lesson one question at a time, the weakest idea first, and explains each answer as soon as you give it:

Interview questions

Warm-up: what is a tail call, and why does it matter in Elixir?

A tail call sits in the last position of a function: once it returns, the caller has nothing left to do and passes the result on unchanged. The BEAM reuses the caller’s stack frame for it, so a function that calls itself only in tail position, usually with an accumulator, runs in a stack of fixed size: 19 words for any n in this lesson, against 2 words per waiting call for body recursion. It matters most in two places. A process’s receive loop never returns, so it must be a tail call or its stack grows with every message, and a call in the do block of a try never is one. A function that computes one value over a long input stays small too. For list builders the Efficiency Guide finds little difference between the two styles, so write the clearer one and measure before rewriting.

Two questions from code that loops and code that was measured:

Key takeaways

• A recursive function handles the simplest input in a base case and calls itself on a smaller input in its other clauses; without a base case the calls reach an input no clause matches.
• A tail call is the last thing a function does, so the BEAM reuses its frame: a tail-recursive sum kept 19 words of stack for any n, while body recursion kept 2 words per waiting call, 20,000,019 words for ten million.
• An accumulator carries the result through the calls and builds lists backwards, so reverse once, in the clause that returns.
• A process’s stack is part of its memory, so a deep body recursion is limited only by memory, or killed by a max_heap_size cap that counts the heap, the stack and the room a garbage collection needs.
• For list builders the two styles cost about the same, but a process’s receive loop must be tail-recursive, and a call in the do block of a try never is.
• Measure with a new process for every run, many runs, the median and the fastest; timings from one process that has already done work measure its heap, not the code.