Back to Posts

Elixir and recursion part II

Nikola Novakovic in Code

Hello people of the internet!

How are you all doing today ? Hopefully you are all having an amazing weekend :)

In my previous blog post I introduced the idea of recursion, why you should do it and how to do it in Elixir.

I did not talk about a really important thing on recursion and that is going to be explored here.

Tail Call Optimization ( TCO )

As I said in my previous post, there is a lot of computer science behind recursion and recursion optimization and all of that jazz so I am not going to go deep into that instead I will try to explain it as simple as possible.

A recursive function falls under TCO if the last thing function does is call itself (or some other function) and with that it will not push to the stack. If it's not going to push to the stack that means there will be no stack overflow ( ever wondered where stackoverflow got name from ? :) ). Here is an example of TCO recursive function:

def awesome do  
  # do something
  bar(...)  # tail call. Calling awesome(...) would work as well
end  

Here is an example of a function that does not fall under TCO:

def not_awesome do  
  # do something
  10 + bar(...) # it calculates something after we return the function
end  

Good news is that when Elixir compiles, Erlang tries to optimize recursive functions for TCO, but you as a programmer have to watch out and not do things that brake TCO principle.

If you are not really familiar with terms like stack and stack overflow, just know that stack overflow is a bad thing and by writing TCO friendly recursion functions stack overflow will not happen. But I really encourage you to go and explore those two things more in depth.

Well that's all from me on recursion. I just wrapped up reading Programming Elixir and I highly recommend to anyone who is trying to get into functional programming itself and Elixir. I might write a book review type of blog post on this.

Have a great day everyone!

Software engineer that loves business side of things as well. Also lifts a lot of weights.

Read Next

Recursively iterating in the wild with Elixir