CODEWITHSUNDEEP
stack-overflowelixir
bright-star
bright-star

Reputation: 6447

Does Elixir infinite recursion ever overflow the stack?

A number of different how-tos on Elixir programming express the view that storing state or running an infinite loop is done idiomatically either by spinning the data off into an Agent or Task, or by infinite recursion of the function that needs state. They don't mention any limits on how deep the recursion can go or any other caveats.

Since searching for "Elixir stack overflow" just results in hits to this website, let me remove the ambiguity and ask here: What implementation guarantees are there in Elixir to make sure that infinite recursion as a method of 'looping' won't result in a stack overflow, especially when state information is being carried around along the way?

Upvotes: 22

Views: 3043

Answers (1)

sasajuric
sasajuric

Reputation: 6059

To summarize excellent comments by Hristo, the general mechanism is called "Tail Call Optimization" (TCO) and it ensures that if the last thing a function does is invocation of another function (or itself), then there won't be stack push. Instead, a simple jump will occur.

There are some subtle nuances as to what is a tail call. Let's see a few example. The simplest one is:

def foo do
  # ...

  bar(...)  # tail call -> nothing is pushed to the stack
end

TCO will also apply for conditional expressions:

def foo do
  # ...

  if (...) do
    # ...
    bar(...)            # tail call
  else
    # ...
    baz(...)            # tail call
  end
end

This works because again the last thing a function does is an invocation of a function. The result of if is the result of either bar or baz so there's no need to push anything onto stack.

In contrast, if the caller function does something after calling another function, it's not a tail call, and TCO won't happen:

def foo do
  # ...

  # Not a tail call since we're doing something after bar returns
  # (increment the result by 1)
  1 + bar(...)    
end

Another example of breaking TCO is calling the function in try:

def foo do
  try do
    bar(...)    # not a tail call
  rescue
    # ...
  end
end

It's also worth mentioning that due to TCO you won't see some functions in the stack trace when an exception occurs:

def foo do
  # ...
  bar(...)  # at this point foo "disappears" from stack trace
end

def bar(...) do
  # ...
  raise("error")
end

The stack dump of this error won't include foo since it is not on the stack anymore (it is effectively replaced with bar).

Upvotes: 22

Related Questions