Recursion, Tail Call Optimization and Recursion.
Tags: ruby, elixir, computerscience, functional
Published: 2018-11-30 09:27:31

Recently I thought I'd take a jab at functional languages just to try out a different paradigm of thinking, and I decided to pick up `Elixir` since it's so syntatically similar to `Ruby`. While I was learning, I found something.


> **TLDR**:
>
> - Elixir has no loops
> - Recursion makes an additional call to call stack (which is why your stack overflows if you forget your base case)
> - Tail Call Optimizations is a compiler feature that optimizes recursions (if the last thing it does is call itself)!

## There is no concept of loop in Elixir.

Yes, none of your `for` loops or `.each`. It's a bit of a strange concept at first, but let's see what's the alternative.

If you can't use an iterative approach to iterate a loop, how do you traverse a list? *Recursion*.

>  Brief recap: Recursion is when a function calls itself, [like this](https://dev.to/edisonywh/recursion-tail-call-optimization-and-recursion-2enh)

A Ruby Example:

```ruby
def traverse(tail)
  head = tail.shift # shift takes out the first element
  puts "Element: #{head}"
  return if tail.empty?
  traverse(tail)
end
```

An Elixir Example:

```elixir
defmodule Recursion do
  def traverse([]), do: IO.puts "Done"
  def traverse([head | tail]) do
  	IO.puts "Element: #{head}"
    traverse(tail)
  end
end
```

*Pretty interesting to traverse recursively instead of the iteratively aye?*

## LARGE NUMBERS!

Next, let's see what happens when it comes to a large number!

*Ruby*:

```ruby
large_array = Array.new(500_000).fill { |i| i + 1 }

traverse(large_array)
# Element: 1
# Element: ...
# Element: ...
# Element: 10918
#=> stack level too deep (SystemStackError)
```

It crashes with a `SystemStackError`! Wow, does that mean `recursion` is bad? does that mean `recursion` is bad? does the mean `recursion` is bad? does that mean `recursion` is ... Okay, before we go crazy, let's take a look at how Elixir deals with it.

*Elixir*:

```elixir
start = 1
increment = 1
length = 500000
list = Stream.iterate(start, &(&1 + increment)) |> Enum.take(length)

Recursion.traverse(list)
# Element: 1
# Element: ...
# Element: ...
# Element: 500000
# Done
#=> :ok
```

You can see that Elixir effortlessly handles all **five hundred thousands** recursion. But why does it work in `Elixir` but not `Ruby`?

Because of  `Tail Call Optimization`!

## What is Tail Call Optimization?

**Tail Call Optimization (TCO)** is a compiler feature in which the compiler automatically optimizes the *stack*, if the last thing that a function does is call itself.

>  *But what is the stack?* *and what do you mean by 'optimizes the stack'?*

Stack is a data structure that employs the LIFO mindset (Last-In-First-Out), think of it as a fixed array but you can only insert from one end and take out from the same end. What we're specifically talking about here is the call stack.

To understand this better, we need to first understand how call stacks work.

When you *call* a function, it gets added to the call stack, and when it finish executing, it gets popped off the stack, like so:

![Call Stack Visualization](https://thepracticaldev.s3.amazonaws.com/i/vm6ringb5e2biqugrctt.gif)

And when you have a recursive function call, it's basically adding itself to the call stack every single time. If you forget your base case/have too big of a call stack, it throws a stack overflow error! (what we saw earlier), like this.

![Recursion Stack Visualization](https://thepracticaldev.s3.amazonaws.com/i/s209q55x1gwq5usnjfo0.gif)

All TCO means is that, when the compiler sees the last call of the function is calling itself, instead of adding the function call to the call stack, it does a ` goto` instead, and basically restarts the same function call, requiring **O(1)** instead of **O(n)** space (we will prove this later).

Now this is what it looks like when it's TCO-ed:

![TCO Call Stack Visualization](https://thepracticaldev.s3.amazonaws.com/i/qfm7l9u3vk3zx10r3l42.gif)

## Do we have that in Ruby?

We do indeed! However TCO is not enabled by default, so you have to pass in the compile option during runtime, and you can do it like so:

```ruby
RubyVM::InstructionSequence.compile_option = {
  tailcall_optimization: true,
  trace_instruction: false
}

require './tail_recursion.rb'

large_array = Array.new(500_000).fill { |i| i + 1 }
traverse(large_array)

# Element: 1
# Element: ...
# Element: ...
#=> Element: 500000
```

Not very useful if you have to enable it with a flag, but it's there if you need it!

## Proof?

Got your back! In RubyLand, We can inspect the current call stack with a call to `Kernel#caller`. Lets `.count`!

Change our code like so:

```ruby
def traverse(tail)
  head = list.shift
  puts "Element: #{head}, Stack Count: #{caller.count}" #=> new line
  return if tail.empty?
  traverse(tail)
end

# Normal ruby
traverse(large_array)
# Element: 1, 			Stack Count: 1
# Element: ..., 		Stack Count: ...
# Element: ..., 		Stack Count: ...
# Element: 10918, 	        Stack Count: 10918
# => stack level too deep (SystemStackError)

# TCO-enabled
traverse(large_array)
# Element: 1, 			Stack Count: 1
# Element: ..., 		Stack Count: 1
# Element: ..., 		Stack Count: 1
# Element: 500000, 	        Stack Count: 1

```



## Conclusion

Alright so that's it for today! Thought it's pretty cool that I'm trying to learn Elixir but end up learning something about compiler instead!

Check out my previous articles too:

- {% link edisonywh/ruby-has-no-class-methods-39l5 %}
- {% link edisonywh/my-ruby-journey-hooking-things-up--feg %}


## Attribution

[Russian doll cover image source](https://www.vecteezy.com)