Tail Recursion
In many languages like Javascript, if a function recursively calls itself, after a certain number of recursive calls, it fails with a “stack overflow” error. This is when the call stack depth exceeds some limit.
This doesn’t happen with Elixir and other Functional Programming languages.
Contents
Watch a Stack Blow
As an example, let’s run this in a Javascript console. You can paste this into a browser’s developer console to try it out.
function recurse(num) {
console.log("Step", num);
recurse(num + 1);
}
recurse(0);
After letting it run for a bit, the console struggles then throws the error.

Using Tail Recursion
Let’s try the same thing in Elixir…
defmodule StackTest do
def recurse(num) do
IO.puts "Step #{num}"
recurse(num + 1)
end
end
StackTest.recurse(0)
Run this in an IEx session and see it continually churn out numbers.

No slowing down, no stopping. This will literally run forever. To stop it, use CTRL+C
, CTRL+C
.
How does this work? How does this not blow up with a StackOverflow error?
Thinking About Tail Recursion
A pseudo-code way of expressing what’s happening is to understand that it is performing a GOTO-like operation where a new value is used for the argument.
0x01 defmodule StackTest do
0x02 def recurse(arg0) do
0x03 IO.puts "Step #{arg0}"
0x04 GOTO 0x03, arg0 is (arg0 + 1)
0x05 end
0x06 end
0x07 StackTest.recurse(0)
Tail Recursion is also called Tail Call Optimization. When the last statement is a recursive call, it gets optimized.
Another way of thinking about it is imagining it gets converted into a while
statement like you see in other languages.
Thinking about it as a goto
or a while
statement both work as a mental model. Internally however, it’s closer to an Assembler JMP (ie. jump) command.
If you unwrap what’s happening here, the instructions essentially ends up looking like this…
StackTest.recurse(0)
StackTest.recurse(1)
StackTest.recurse(2)
StackTest.recurse(3)
StackTest.recurse(4)
StackTest.recurse(5)
# ...
Where a new input value is used and it is run again. There is no call stack being generated!
Creating a Recursion Error
You can create a recursion error when the last line is NOT a recursive call. When there are more instructions to perform following a recursive call, tail recursion cannot be used. The BEAM needs to track the call stack so it can return and execute the remaining statements. However, it isn’t really a StackOverflow error, it’s a memory allocation error.
If you’d like to see it in action, this code will do it. It will take a lot longer to run before it errors. TIP: Before you run it, you might want to read what it does first!
defmodule StackTest do
def recurse(num) do
IO.puts "Step #{num}"
recurse(num + 1)
IO.puts "Another instruction but you'll never see it."
end
end
StackTest.recurse(0)
Finally it errors because it can’t allocate enough RAM. You may not actually want to run it, since it will crash at some point, then generate a very large erl_crash.dump
crash dump file. I killed mine before it finished writing the file and the file was already 27 GB in size and growing!
iex> StackTest.recurse(0)
# ...
eheap_alloc: Cannot allocate 6801972448 bytes of memory (of type "heap").
Crash dump is being written to: erl_crash.dump...
A number of things in Elixir use and depend upon tail recursion. It is an important feature and behavior of the BEAM. Know what it is so you can use it well!
When the last command is a recursive call, then tail-recursion is used and it can efficiently loop forever.
2 Comments
Comments are closed on this static version of the site.
Comments are closed
This is a static version of the site. Comments are not available.