This post will explore recursion using Elixir. We’ll start with writing a recursive function and then explore how to improve the function’s performance through tail recursion.

Recursion

A recursive function calls itself until it reaches a condition that stops the function from calling itself. This condition is called the base case.

Fibonacci

A Fibonacci sequence is a mathematical construct of a group of integers where each number is the sum of the previous two.

1 1 2 3 5 8 13 …

Given an input n, the Fibonacci algorithm returns the nth number of the Fibonacci sequence. For example, if the function’s input is 6, the function should return the number that would occur 6th in the Fibonacci sequence. Below, we see 8 is 6th in a Fibonacci sequence.

1 1 2 3 5 8 13…

We can solve this with a recursive function.

defmodule Fibonacci do
 def fib(0), do: 0
 def fib(1), do: 1
 def fib(n), do: fib(n-1) + fib(n-2)
end

Fibonacci.fib(6)
=> 8

The function calls itself until it reaches a base case. Below demonstrates the sequence of function calls. When the function reaches the final base case, it winds back up the call stack adding the results of previous base cases.

• fib(6) calls fib(5) + fib(4)
• fib(5) calls fib(4) + fib(3)
• fib(4) calls fib(3) + fib(2)
• fib(3) calls fib(2) + fib(1)
• fib(2) calls fib(1)) + fib(0)
• fib(2) calls fib(1) + fib(0)
• fib(3) calls fib(2) + fib(1)
• fib(2) calls fib(1) + fib(0)
• fib(4) calls fib(3) + fib(2)
• fib(3) calls fib(2) + fib(1)
• fib(2) calls fib(1) + fib(0)
• fib(2) calls fib(1) + fib(0)

Each result of the base case def fib(1), do: 1 adds up to the final result of 8. With this approach, the size of the input could slow the performance. Even just increasing the input to 50 is slower.

Why so slow?

When you call a function, a stack frame is added to the call stack. Each time a stack frame is added to the call stack, some memory is set aside to store the local state. When a recursive function exits, it winds up each stack frame in the call stack in reverse order. The greater the input, the more stack frames are added to the call stack. It takes time to wind back up the call stack to produce the final result. Also, your computer’s memory is not finite. If it runs out of memory, the program will crash with a “stack overflow” error.

Tail-recursive

Fortunately, we can use tail-recursion to improve the performance. A function is tail-recursive when the recursive function is the last step executed. We can do this by adding a private function that will accumulate the results of the previous iterations.

Below is a tail-recursive version of the algorithm:

defmodule FibonacciOptimized do
  def fib(0), do: 0
  def fib(1), do: 1
  def fib(n), do: get_fib(0, 1, n)
  
  defp get_fib(_, result, 1), do: result
  defp get_fib(a, b, n), do: get_fib(b, a + b, n - 1)
end

iex > FibonacciOptimized.fib(6)
=> 8

With this approach, we don’t have to add so many stack frames to the call stack, which speeds things up and uses less memory. In this example, the result of each previous iteration is accumulated in a variable and passed along to the final base case:

defp get_fib(_, result, 1), do: result

Now, increasing the input to 50 returns a quick result.

Final notes

You are not always going to need tail-recursion when you solve a problem with recursion. However, if the input to a function is large, variable, or streaming, you might want to consider it.