Implementing recursion and tail recursion


#1

Does elixir use tail recursion automatically or the programmer must do it manually to optimize the algorithm ?
And therefore previous calculated calls should be stored in a map ?


#2

Elixir has tail call optimisation, but for it to happen, it must obviously be a tail call. So I’d say it’s part automatic and part manual. :stuck_out_tongue: I don’t think there are any heuristics to change code to tail recursive if it isn’t already.


#3

Ok, because in python I used to save previous calculations in a dictionary (key-value elements). And before every recursive call (key) I first check if the calculation (value) was already done.


#4

There is something similar in FP, it is called memoization.

http://rocket-science.ru/hacking/2017/11/23/idiomatic-function-memoization-in-elixir


#5

That would actually be a dreadfully slow way to do that. Instead you’d want to use ETS.

TCO is built in to the VM itself, it is entirely and fully tail call optimized.

You’d probably want to use ETS for that (that has nothing to do with TCO at all).


#6

Contrasting the three approaches:

defmodule Demo do

  # 1. body recursion, i.e. not tail call optimized
  def fib(0),
    do: 0
  def fib(1),
    do: 1
  def fib(n) when n > 1 and is_integer(n),
    do: fib(n-2) + fib(n-1)

  # 2. utilizing "last call optimization"
  # http://erlang.org/pipermail/erlang-questions/2016-October/090663.html
  defp fib_lco(_, acc, i, n) when i == n,
    do: acc
  defp fib_lco(fi_2, fi_1, i, n) when i < n,
    do: fib_lco(fi_1, fi_2 + fi_1, i + 1, n)

  def fib_lco(0),
    do: 0
  def fib_lco(1),
    do: 1
  def fib_lco(n) when n > 1 and is_integer(n),
    do: fib_lco(fib_lco(0), fib_lco(1), 1, n)

  # 3. using a result cache
  defp fib_mem_fill(_, fi_1, i, mem, n) when i > n do
    {fi_1, mem}
  end
  defp fib_mem_fill(fi_2, fi_1, i, mem, n) do
    fi =  fi_2 + fi_1
    fib_mem_fill(fi_1, fi, i+1, Map.put(mem, i, fi), n)
  end

  defp fib_mem_fill(n, mem) do
    with i <- Map.size(mem),
         {:ok, fi_2} <- Map.fetch(mem, i - 2),
         {:ok, fi_1} <- Map.fetch(mem, i - 1) do
      fib_mem_fill(fi_2, fi_1, i, mem, n)
    else
      _ -> # unexpected lookup failure - start fresh
        fib_mem_fill(0, 1, 2,  %{0 => 0, 1 => 1}, n)
    end
  end

  def fib_mem(n, mem \\ %{0 => 0, 1 => 1}) when n >= 0 and is_integer(n) do
    with {:ok, result} <- Map.fetch(mem, n) do
      {result, mem}
    else
      _ -> # not found
        fib_mem_fill(n, mem)
    end
  end

  # "show"" functionality
  def show(name,n,f,extract)  do
    result = f.(n)
    IO.puts("#{name}(#{n}): #{extract.(result)}")
    result # needed for fib_mem
  end

  defp extract({result,_}), do: result
  defp extract(x), do: x

  defp inject(nil), do: &(fib_mem(&1)) # i.e. use default argument
  defp inject(mem), do: &(fib_mem(&1, mem))

  def show2(n, mem \\ nil) do
    show("fib_lco", n, &fib_lco/1, &extract/1)
    show("fib_mem", n, inject(mem), &extract/1) # returns {result, mem}
  end

  def show3(n, mem \\ nil) do
    show("fib", n, &fib/1, &extract/1)
    show2(n, mem) # returns {result, mem}
  end

  def show_list(mem, list, show) do
    show_entry =
      fn (n, mem_map) ->
        {_, next_map} = show.(n, mem_map)
        next_map
      end

    List.foldl(list, mem, show_entry) # returns newest mem
  end

end

nil
|> Demo.show_list([0, 10, 30], &Demo.show3/2)
|> Demo.show_list([100, 1_000, 10_000], &Demo.show2/2)
$ elixir demo.exs
fib(0): 0
fib_lco(0): 0
fib_mem(0): 0
fib(10): 55
fib_lco(10): 55
fib_mem(10): 55
fib(30): 832040
fib_lco(30): 832040
fib_mem(30): 832040
fib_lco(100): 354224848179261915075
fib_mem(100): 354224848179261915075
fib_lco(1000): 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
fib_mem(1000): 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

But keep in mind:
2.1 Myth: Tail-Recursive Functions are Much Faster Than Recursive Functions
Erlang’s Tail Recursion is Not a Silver Bullet
Tail vs. Body Recursion in Erlang Part 1

  • Tail recursion isn’t always better than body recursion.
  • But given that formulating tail recursive versions takes practice it’s probably a good idea to take every opportunity to design a tail recursive version of a body recursive function - and then choose the implementation with the most merits.

#7

@peerreynders Thank you for the answer. Maybe to compare those 3 methods, a counter can be added to count the number of operations required to perform the calculations.


#8

mix profile.fprof

$ mix profile.fprof -e Demo.load_1
Warmup...
Reading trace data...
..................................................
.................................
End of trace!
Processing data...
Creating output...
Done!

                                                                   CNT    ACC (ms)    OWN (ms)     
Total                                                          2966862    7384.348    7370.573     
:fprof.apply_start_stop/4                                            0    7384.348       0.013     
anonymous fn/0 in :elixir_compiler_1.__FILE__/1                      1    7384.319       0.002     
Demo.load_1/0                                                        1    7384.317       0.002     
Demo.run_load/2                                                      1    7384.315       0.007     
List.foldl/3                                                         1    7384.274       0.001     
List."-foldl/3-lists^foldl/2-0-"/3                                   9    7384.273       0.024     
anonymous fn/2 in Demo.load_1/0                                      8    7384.249       0.010     
Demo.run_1/2                                                         8    7384.239       0.019     
Fib.body/1                                                     2959380    7383.630    7330.228     
:garbage_collect                                                  5424      39.637      39.637     
:suspend                                                          1708      13.775       0.000     
Demo.run_2/2                                                         8       0.590       0.040     
Fib.mem/2                                                            9       0.215       0.031     
Fib.lco/1                                                           20       0.191       0.038     
Fib.mem_fill/2                                                       6       0.175       0.036     
Fib.lco/4                                                          105       0.153       0.153     
Fib.ets/2                                                            8       0.150       0.020     
Fib.mem_fill/5                                                      35       0.120       0.087     
Fib.ets_fill/2                                                       6       0.118       0.017     
Fib.ets_fill/6                                                      35       0.092       0.070     
:maps.put/3                                                         29       0.033       0.033     
:maps.find/2                                                        21       0.021       0.021     
:ets.lookup/2                                                       14       0.021       0.021     
:ets.insert/2                                                        7       0.019       0.019     
:fprof."-apply_start_stop/4-after$^1/0-0-"/3                         1       0.016       0.006     
:ets.delete/1                                                        1       0.015       0.015     
Fib.ets_init/1                                                       1       0.012       0.005     
:maps.size/1                                                         6       0.007       0.007     
Fib.mem/1                                                            1       0.007       0.001     
Fib.ets_top/3                                                        7       0.007       0.007     
:ets.new/2                                                           1       0.003       0.003     
:undefined                                                           0       0.000       0.000   
$ mix profile.fprof -e Demo.load_2
Warmup...
Reading trace data...
..................................................
......
End of trace!
Processing data...
Creating output...
Done!

                                                                   CNT    ACC (ms)    OWN (ms)     
Total                                                            46769     104.538     102.942     
:fprof.apply_start_stop/4                                            0     104.538       0.014     
anonymous fn/0 in :elixir_compiler_1.__FILE__/1                      1     104.520       0.002     
Demo.load_2/0                                                        1     104.518       0.002     
Demo.run_load/2                                                      1     104.516       0.006     
List.foldl/3                                                         1     102.996       0.001     
List."-foldl/3-lists^foldl/2-0-"/3                                   6     102.995       0.030     
anonymous fn/2 in Demo.load_2/0                                      5     102.965       0.010     
Demo.run_2/2                                                         5     102.955       0.028     
Fib.mem/2                                                            6      47.658       0.023     
Fib.mem_fill/2                                                       5      47.628       0.028     
Fib.mem_fill/5                                                   10004      47.584      28.096     
Fib.ets/2                                                            5      29.961       0.017     
Fib.ets_fill/2                                                       5      29.936       0.015     
Fib.ets_fill/6                                                   10004      29.912      16.173     
Fib.lco/1                                                           15      25.317       0.033     
Fib.lco/4                                                        16600      25.284      24.615     
:maps.put/3                                                       9999      13.114      13.114     
:garbage_collect                                                    25      12.586      12.586     
:ets.insert/2                                                        6       6.606       6.606     
:suspend                                                            33       1.596       0.000     
:ets.delete/1                                                        1       1.491       1.483     
:maps.find/2                                                        16       0.017       0.017     
:ets.lookup/2                                                       10       0.017       0.017     
Fib.ets_init/1                                                       1       0.013       0.006     
Fib.mem/1                                                            1       0.010       0.001     
:maps.size/1                                                         5       0.006       0.006     
Fib.ets_top/3                                                        6       0.006       0.006     
:fprof."-apply_start_stop/4-after$^1/0-0-"/3                         1       0.004       0.004     
:ets.new/2                                                           1       0.003       0.003     
:undefined                                                           0       0.000       0.000     
defmodule Demo do
  # lib/demo.ex

  def load_1() do
    run_load([0,1,5,10,15,20,25,30], &run_1/2)
  end

  def load_2() do
    run_load([100,500,1000,5000,10000], &run_2/2)
  end

  def run_load(load, run_f) do
    {_, mem} = Fib.mem(0)
    tid = Fib.ets_init(:my_cache)
    _state = List.foldl(load, {mem,tid}, run_f)
    :ets.delete(tid)
  end

  def run_1(n, state) do
    Fib.body(n)
    run_2(n, state) # returns new state
  end

  def run_2(n, {mem, tid}) do
    Fib.lco(n)
    {_, next_mem} = Fib.mem(n, mem)
    Fib.ets(n, tid)
    {next_mem, tid}
  end

end
defmodule Fib do
  # lib/fib.ex

  # 1. body recursion
  def body(0),
    do: 0
  def body(1),
    do: 1
  def body(n) when n > 1 and is_integer(n),
    do: body(n-2) + body(n-1)

  # 2. utilizing "last call optimization"
  # http://erlang.org/pipermail/erlang-questions/2016-October/090663.html
  defp lco(_, acc, i, n) when i == n,
    do: acc
  defp lco(fi_2, fi_1, i, n) when i < n,
    do: lco(fi_1, fi_2 + fi_1, i + 1, n)

  def lco(0),
    do: 0
  def lco(1),
    do: 1
  def lco(n) when n > 1 and is_integer(n),
    do: lco(lco(0), lco(1), 1, n)

  # 3. using a result cache
  defp mem_fill(_, fi_1, i, mem, n) when i > n do
    {fi_1, mem}
  end
  defp mem_fill(fi_2, fi_1, i, mem, n) do
    fi =  fi_2 + fi_1
    mem_fill(fi_1, fi, i+1, Map.put(mem, i, fi), n)
  end

  defp mem_fill(n, mem) do
    with i <- Map.size(mem),
         {:ok, fi_2} <- Map.fetch(mem, i - 2),
         {:ok, fi_1} <- Map.fetch(mem, i - 1) do
      mem_fill(fi_2, fi_1, i, mem, n)
    else
      _ -> # unexpected lookup failure - start fresh
        mem_fill(0, 1, 2,  %{0 => 0, 1 => 1}, n)
    end
  end

  def mem(n, mem \\ %{0 => 0, 1 => 1}) when n >= 0 and is_integer(n) do
    with {:ok, result} <- Map.fetch(mem, n) do
      {result, mem}
    else
      _ -> # not found
        mem_fill(n, mem)
    end
  end


  # 4. ETS cache
  defp ets_top(fib_i1, fib_i, i),
    do: {:top, {fib_i1, fib_i, i}}

  defp ets_fill(fib_i1, fib_i, i, kvs, tid, n) when i == n do
    :ets.insert(tid, [ets_top(fib_i1, fib_i, i) | kvs])
    fib_i
  end
  defp ets_fill(fib_i1, fib_i, i, kvs, tid, n) when i < n do
    fib_next =  fib_i1 + fib_i
    next = i + 1
    ets_fill(fib_i, fib_next, next, [{next, fib_next}|kvs], tid, n)
  end

  defp ets_fill(n, tid) do
    with [{_, {fib_i1, fib_i, i}}] <- :ets.lookup(tid, :top) do
      ets_fill(fib_i1, fib_i, i, [], tid, n)
    else
      _ -> # unexpected lookup failure
        raise ArgumentError, message: "Provided inconsistent ETS cache"
    end
  end

  def ets_init(name) when is_atom(name) do
    tid = :ets.new(name,[:set, :private, {:keypos, 1}])
    :ets.insert(tid, [{0, 0}, {1, 1}, ets_top(0,1,1)])
    tid
  end

  def ets(n, tid) do
    with [{_ ,fib_n}] <- :ets.lookup(tid, n) do
      fib_n
    else
      _ ->
        ets_fill(n, tid)
    end
  end

end

Edit: Added an ETS version.