You've probably heard (and written) some recursive functions/methods before. Chances are you've also heard that recursive functions might be more expensive when compared to a non-recursive alternative.
Let's see what is probably the simples example of a recursive function, the factorial implementation. Here we define two clauses of
Factorial.recursive_factorial/1, on for
0 (which returns
1) and another for any other value:
defmodule Factorial do def recursive_factorial(0), do: 1 def recursive_factorial(n), do: n * recursive_factorial(n-1) end
On each call of
recursive_factorial(n) we multiply
n by the result of
recursive_factorial(n-1) (which is a recursive call until
0). On every step we need to keep the current value of
n so we can multiply it once
recursive_factorial(n-1) is returned.
This is why recursive calls are usually considered to be more expensive (specially in terms of space), each call requires the stack to be saved until the result comes back. Saving a stack, even if it is just that
n might start causing trouble when the number gets too high (say
500_000 or more, depending on where you're running it).
But there is something we can do to make it better and as performant as the non recursive alternatives
Take a look at this other implementation and compare it to the previous one:
defmodule Factorial do def tail_recursive_factorial(n), do: tail_recursive_factorial(n, 1) defp tail_recursive_factorial(0, acc), do: acc defp tail_recursive_factorial(n, acc), do: tail_recursive_factorial(n-1, acc*n) end
The first call to
Factorial.tail_recursive_factorial/1 starts the process by calling the private
Factorial.tail_recursive_factorial/2 which does the recursive process.
Notice that the multiplication is now passed to the recursive call using the second argument. This means that there is no need to store the function stack for each call!
Each call now has everything it needs and the stack can be discarded as soon as the recursive call starts. The end clause here is when
0 and it just returns the value on
When a recursive function doesn't need to store any temporary value to be used after the recursive call, it is considered a Tail Recursive function. Let's check a more interesting problem.
The 'Strain' exercise on Exercism
On exercism.io there is a nice little exercise where you're asked to implement two functions,
discard. Given a
list of items and a function
keep will return the list of items where
discard will return the list of items where
Me and some friends got together to solve this and our initial implementation of
keep was to execute
fun on the
head of the list and if it is
true return a list with the the
head and then recurse on
tail, if not then just call again ignoring the
head of the list:
def keep(, _fun) do  end def keep([head | tail] = list, fun) do keep_if(list, fun, fun.(head)) end defp keep_if([head | tail] = list, fun, true) do [head | keep(tail, fun)] end defp keep_if([head | tail] = list, fun, false) do keep(tail, fun) end
The main problem here is that for each call where
fun is true we need to save the value stored on
head and after the recursive call finishes, the return has to be appended to a list containing
For the test scenarios we had, this wasn't a big issue, but we wanted to go a bit further and think about how to make this a tail recursive function.
Our optimization was similar to what we did for
Factorial.tail_recursive_factorial/1, we create an accumulator argument and send it on each call instead of waiting to get the result back. Here is how it ended up looking like:
defmodule Strain do def keep(list, fun) do keep(list, , fun) end def keep(, filtered, _fun) do filtered end def keep([head | _tail] = list, filtered, fun) do keep(list, filtered, fun, fun.(head)) end defp keep([head | tail], filtered, fun, true) do keep(tail, filtered ++ [head], fun) end defp keep([_head | tail], filtered, fun, false) do keep(tail, filtered, fun) end end
Another nice exercise to try and apply tail recursive optimization is the 'List Operations' one where you're asked to implement basic functions that we usually take for granted, like
Recursive functions are quite common in functional languages, most of them don't even have loops, so learning about tail recursion and practicing how to implement it is a good investment :)