Elixir Note - Recursion

1. Loop over the list

Due to immutability, loops in Elixir are written differently from imperative languages. For example, loops commonly look like:

for(i = 0; i < array.size; i++) {
  # do something with array[i]
}

In a functional language, mutating i (by calling i++) is not possible. Thus, Elixir uses recursion for looping over data structures like lists.

The equivalent of a for loop in Elixir would look like this:

def loop([]), do: nil

def loop([head | tail]) do
  do_something(head)
  loop(tail)
end

Example: sum all integer of the list

defmodule SumList do
  def sum_numbers([head | tail]) do
    sum_numbers(tail) + head
  end
 
  def sum_numbers([_head | tail]) do
    sum_numbers(tail)
  end
 
  def sum_numbers([]), do: 0
end

2. Tail Call Recursion

Because Elixir implements tail call optimization, so we can use tail call recursion to reduce the number of stack frames.

We will rewrite sum_numbers function in example 1 using tail call recursive version.

defmodule SumList do
  def sum_numbers(list) do
    do_sum_numbers(list, 0)
  end
 
  defp do_sum_numbers([head | tail], sum)do
    do_sum_numbers(tail, sum + head)
  end
 
  defp do_sum_numbers([], sum), do: sum
end

In tail call recursive version, an accumulator sum is used to pass the current state of the function's execution. When the base case is reached, the accumulator is used to return the final value of the recursive function call.

Note: Not at all programming languages support tail call optimization. Python, Javascript don't support. Ruby allows you to optionally enable it, even though it’s not the default.

View more about Tail Call Optimization in elixir: https://dino.codes/posts/tail-call-optimization-in-elixir/