By Yuji Yokoo

# Tail Call Optimisation in Ruby (MRI)

I have recently discovered that MRI implements Tail Call Optimisation (TCO). It is a common optimisation technique used in many programming languages. Let me show you a short summary of what I found about the TCO in MRI.

## Background: What is Tail Call Optimisation?

Tail Call Optimisation refers to a form of optimisation, or program transformation commonly used in programming languages with optimising-compilers. It optimises tail-recursive functions by transforming (or rewriting) them in loops, which avoids the overhead of recursive function calls. As the name suggests, it can only be applied to tail-recursive functions. A tail-recursive function is a function in which the final action to be performed is the call to the function itself.

For example, here we have a non-tail-recursive version and a tail-recursive version of `reverse` which reverses an array:

```def arr_reverse(array)
return [] if array.empty?
return arr_reverse(array[1..-1]) + [array[0]]
end

def arr_reverse_tail_recursive(array, accumulator = [])
return accumulator if array.empty?
return arr_reverse_tail_recursive(array[1..-1], [array[0]] + accumulator)
end
```

They both return reversed arrays:

```2.1.2 :029 > arr_reverse([1,2,3,4])
=> [4, 3, 2, 1]
2.1.2 :030 > arr_reverse_tail_recursive((1..10).to_a)
=> [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
2.1.2 :031 > arr_reverse_tail_recursive(arr_reverse [1,2,3])
=> [1, 2, 3]
```

The first example makes the recursive call, takes the result, appends the element, and finally returns the resulting array. The second example simply returns the return value from the call to itself. The first example is not tail-recursive because the final action is not the call to itself. The second example is tail-recursive because the final action is the recursive call to itself. The second version is, of course, the version that can have TCO applied.

## Factorial example

Consider this example for calculating the factorial:

```# fact_simple.rb

def fact(n)
raise InvalidArgument, "negative input given" if n < 0
return 1 if n == 0
return fact(n-1) * n
end
```

This is a simple recursive implementation. Let us save this as `fact_simple.rb`.

```2.1.2 :001 > require './fact_simple'
=> true
2.1.2 :002 > fact(10)
=> 3628800
2.1.2 :003 > fact(5)
=> 120
```

One problem here is that when we run it with sufficiently large input, we will get an error:

```2.1.2 :007 > fact(10000)
SystemStackError: stack level too deep
```

This happens because each recursive call grows our call stack with a new stack frame, and our runtime environment is running out of space.

We can rewrite this function in a tail-recursive manner, and execute with the TCO to solve the problem.

Let us start with rewriting the code first. Here, a tail-recursive version might look like this:

```# fact_tail_call.rb

def fact(n, accumulator = 1)
raise InvalidArgument, "negative input given" if n < 0
return accumulator if n == 0
return fact(n-1, accumulator * n)
end
```

Let us save this as `fact_tail_call.rb`. This is a tail-recursive version of the factorial. However, just running this will result in no improvement.

```2.1.2 :001 > require './fact_tail_call'
=> true
2.1.2 :002 > fact(10000)
SystemStackError: stack level too deep
```

This is because the TCO is not enabled by default in MRI. We can enable the TCO by doing this instead:

```2.1.2 :001 > program = RubyVM::InstructionSequence.new File.open('./fact_tail_call.rb').read, nil, nil, nil, tailcall_optimization: true, trace_instruction: false
=> <RubyVM::InstructionSequence:<compiled>@<compiled>>
2.1.2 :002 > program.eval
=> :fact
```

Now we have the same function with the TCO enabled. At this point, we can run `fact(10000)` successfully. However, since it will output a very large number, let us just check the number of digits instead:

```2.1.2 :003 > fact(10).to_s.length
=> 7
2.1.2 :004 > fact(100).to_s.length
=> 158
2.1.2 :005 > fact(1000).to_s.length
=> 2568
2.1.2 :006 > fact(10000).to_s.length
=> 35660
2.1.2 :007 > fact(100000).to_s.length
=> 456574
```

The last one takes a while but still does not result in an error.

## Possible Problem

The TCO is a great tool if it is used appropriately. However, we have to remember that it transforms the program, and it can affect the semantics.

Consider this example where we implement a simple linked list using Hash, and we have a simple function to print all values. It will exit with an error message if the recursive calls is not terminating:

```node1 = { value: 1 }
node2 = { value: 2, next: node1 }
node1[:next] = node2 # looping list

def print_values(node)
puts node[:value]
print_values(node[:next]) if node[:next]
end

begin
print_values(node1)
rescue SystemStackError
puts "Your list is too long or it is looping somewhere"
end
```

If we execute this without the TCO, it will terminate with the message `"Your list is too long or it is looping somewhere"`.

```...
2
1
Your list is too long or it is looping somewhere
=> true
2.1.2 :019 >
```

However, with the TCO, it will not terminate. In this example, the execution relies on the `stack level too deep` error. This is not a good programming style but if we happened to be working on code like this, the TCO cannot be applied. This is an unrealistic example, and in real life, it will probably be more subtle than this.

## Final Thoughts

MRI supports tail call optimisation, but it is not enabled by default. While we may not need this so often, it still is a useful thing to know as a programmer in case we have to design a linked list or tree traversal algorithm for potentially very large input data.

### We Hire Only the Best

reinteractive is Australia’s largest dedicated Ruby on Rails development company. We don’t cut corners and we know what we are doing.

We are an organisation made up of amazing individuals and we take pride in our team. We are 100% remote work enabling us to choose the best talent no matter which part of the country they live in. reinteractive is dedicated to making it a great place for any developer to work.

### Free Community Workshops

We created the Ruby on Rails InstallFest and Ruby on Rails Development Hub to help introduce new people to software development and to help existing developers hone their skills. These workshops provide invaluable mentorship to train developers, addressing key skills shortages in the industry. Software development is a great career choice for all ages and these events help you get started and skilled up.

• Webinars

Webinars are our online portal for tips, tricks and lessons learned in everything we do. Make the most of this free resource to help you become a better developer.

• Installfest

The Ruby on Rails Installfest includes a full setup of your development environment and step-by-step instructions on how to build your first app hosted on Heroku. Over 1,800 attendees to date and counting.

• Development Hub

The Ruby on Rails Development Hub is a monthly event where you will get the chance to spend time with our team and others in the community to improve and hone your Ruby on Rails skills.