Recursion in

About Recursion

Recursive functions are functions that call themselves.

A recursive function needs to have at least one base case and at least one recursive case.

A base case returns a value without calling the function again. A recursive case calls the function again, modifying the input so that it will at some point match the base case.

Very often, each case is written in its own function clause.

# base case
def count([]), do: 0

# recursive case
def count([_head | tail]), do: 1 + count(tail)

A recursive function can have many base cases and/or many recursive cases. For example the Fibonacci sequence is a recursive sequence with two base cases:

def fibonacci(0), do: 0
def fibonacci(1), do: 1
def fibonacci(n), do: fibonacci(n - 1) + fibonacci(n - 2)

Counting the number of occurrences of some given value x in a list has two recursive cases:

def count_occurrences([], _x), do: 0
def count_occurrences([x | tail], x), do: 1 + count_occurrences(tail, x)
def count_occurrences([_ | tail], x), do: count_occurrences(tail, x)

Loops through recursion

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, loops have to be implemented with recursion.

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

In practice, iterating over lists and other enumerable data structures is most often done using the Enum module. Under the hood, functions from the Enum module are implemented using recursion.

Infinite execution

Recursive functions, if implemented incorrectly, might never return their result. This can be problematic because each time a function is called, a reference is stored in memory where the VM should return the result (on the call stack). If a recursive function calls itself infinitely, it is possible to run out of memory causing the VM to crash (a stack overflow error). The Erlang VM, on which Elixir runs, is specially optimized for recursion and reliability, so it may take a long time before infinite recursion errors are apparent or crashes occur.

This problem of infinite execution can be caused by:

• Forgetting to implement a base case.
• Not defining the base case as the first clause.
• Not modifying the argument properly when doing the recursive call, and thus never reaching the base case.