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.

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)
Thinking Tip: An Optimization

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.

Comments are closed

This is a static version of the site. Comments are not available.

2 Comments

  1. Sergey Makarichev on December 11, 2022 at 4:35 am

    Hi, Mark!
    1) It’s better to add some comments why the strings below are not 6 various stack calls (the sample in the middle of the lesson):
    StackTest.recurse(0)
    StackTest.recurse(1)
    StackTest.recurse(2)
    StackTest.recurse(3)
    StackTest.recurse(4)
    StackTest.recurse(5)

    For me it looks like 6 independent stack calls – StackTest.recurse() function is called with various arguments 6 times, and all these calls are added into stack.
    For example, in Kotlin tail recursion transforms into plain iteration, but that iteration is within 1 function call. And that’s not what I see in the example above – I expected 1 function call in Elixir too, but I saw 6 function calls…

    2) All this means that Elixir doesn’t have a limited stack (like С or Java), but it’s stack limit equals the total amount of RAM of the system?
    So tail recursion won’t last forever, but until all system RAM is used, right?

    • Mark Ericksen on December 19, 2022 at 7:27 am

      Hi Sergey,

      Elixir also has a RAM limited stack. If the recursive call is followed by more instructions, then a regular stack is used and it can be blown. When the final instruction is a recursive call, then it is “tail recursion” and will effectively run forever without pushing on to the stack.

      Yes, the list of functions could be confusing since the name is “recurse”. I’ll have to think about a clearer way to express that.

Comments are closed on this static version of the site.