TCO (Tail Call Optimization) - Ruby
Tags: ruby, tco, braziliandevs
Published: 2022-01-09 16:23:05

Recentemente escrevi um artigo sobre [Recursão em Ruby](https://dev.to/dnovais/recursao-ruby-35gi) e algumas pessoas me pediram para complementar o artigo falando sobre `TCO (Tail Call Optimization)`. Como é um assunto interessante, achei melhor escrever este novo artigo complementar sobre o assunto.

## Contextualizando

Quando implementamos recursão para por exemplo, calcular o fatorial de um número:

```Ruby
def factorial(number)
  number == 1 ? 1 : number * factorial(number - 1)
end
```

Se passarmos como parâmetro um número muito grande, por exemplo 11.000, provavelmente teremos um problema de **estouro de pilha**.

```Ruby
factorial(11_000)
irb(main):012:0> factorial(11_000)
Traceback (most recent call last):
       16: from (irb):5:in `factorial'
       15: from (irb):5:in `factorial'
       14: from (irb):5:in `factorial'
       13: from (irb):5:in `factorial'
       12: from (irb):5:in `factorial'
       11: from (irb):5:in `factorial'
       10: from (irb):5:in `factorial'
        9: from (irb):5:in `factorial'
        8: from (irb):5:in `factorial'
        7: from (irb):5:in `factorial'
        6: from (irb):5:in `factorial'
        5: from (irb):5:in `factorial'
        4: from (irb):5:in `factorial'
        3: from (irb):5:in `factorial'
        2: from (irb):5:in `factorial'
        1: from (irb):5:in `factorial'
SystemStackError (stack level too deep)
```

Então para evitar problemas e gargalos no processamento o erro `SystemStackError (stack level too deep)` é disparado antes mesmo de executar método recursivamente.

> _Lembrando que Stack significa pilha, e uma pilha é uma estrutura de dados, em que assim como uma pilha de pratos por exemplo, o ultimo a entrar será o primeiro a sair (LIFO - Last In First Out)._

## Como podemos resolver este problema?

Para resolver este problema e conseguirmos executar o método de forma recursiva podemos usar como estratégia o `TCO (Tail Call Optimization)`.

## O que é TCO (Tail Call Optimization)? 

TCO é uma estratégia utilizada para otimizar a execução de **pilhas de chamadas** e prevenir do estouro de pilha ao usar a recursão.

A estratégia consiste em transformar as **pilhas de chamadas** dos métodos tail-recursive em loops, o que evita a sobrecarga de chamadas de função recursivas. Ou seja, a pilha deixa de "existir" e passa ser uma sobrescrita das chamadas.

### O que é uma pilha de chamada?
Uma pilha de chamadas é onde será armazenada as informações sobre as chamadas recursivas do método. Ou seja, para cada chamada método de forma recursiva será adicionado uma nova chamada à pilha de chamadas.

Então quando o número de itens na pilha de chamadas ultrapassa o tamanho permitido, ocorre estouro de pilha.

## E como funciona o TCO (Tail Call Optimization)?
Para que seja possível utilizar essa estratégia é necessário 2 passos:

### 1 - O método recursivo precisa ser criado ou modificado para ser um método tail-recursive
Em nosso exemplo, precisaremos motificar o método e a forma como é feito cálculo, e assim, transformá-lo em tail-recursive, ficando da seguinte forma:

```Ruby
def factorial(number, accumulator=1)
  return accumulator if number <= 1

  factorial(number - 1, accumulator * number)
end
```

#### O que mudou?

1. Foi adicionado mais 1 argumento na assinatura do método para servir como acumulador do resultado;
2. O acumulador será inicializado igual a 1 para garantir que na segunda vez que o método for chamado, seu valor seja o mesmo passado para `number` inicialmente;
3. O acumulador (ou seja, o resultado) será retornado quando o `number` for igual ou menor a 1;
4. Fazendo essas mudanças garantimos que a última chamada será o próprio método sem depender de outro fator ou variável;
5. E assim garantimos que tail (calda, ultima chamada) seja o próprio método (acredito que seja esse o significado do nome Tail Call Optimization) e aconteça a sobrescrita das chamadas ;

### 2 - O Tail Call Optimization precisa estar habilitado no Ruby

Por padrão, o tail call optimization não é habilitado no Ruby. Então para que o método tail-recursive funcione corretamente precisamos habilitar (caso não seja habilitado o erro `SystemStackError (stack level too deep)` continuará acontecendo).

#### Para habilitar o TCO no ruby

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

**Agora sim o método `factorial(11_000)` será executado com sucesso.**

Para facilitar segue todo o código:

```Ruby
def factorial(number, accumulator=1)
  return accumulator if number <= 1

  factorial(number - 1, accumulator * number)
end

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

factorial(11_000)
```


## Conclusão

O uso de Tail Call Optimization é uma estratégia que não iremos usar no dia a dia, mas é importante conhecer para caso precisar.


---
>### Referências:
- https://nithinbekal.com/posts/ruby-tco/
- https://reinteractive.com/posts/214-tail-call-optimisation-in-ruby-mri
- https://ruby-doc.org/core-3.1.0/RubyVM/InstructionSequence.html#method-c-compile_option
- https://ruby-doc.org/core-3.1.0/SystemStackError.html
- https://riptutorial.com/ruby/example/30381/tail-recursion
- https://www.youtube.com/watch?v=6Tblgvvit4E
- https://harfangk.github.io/2017/01/01/how-to-enable-tail-call-recursion-in-ruby.html
- https://stackoverflow.com/questions/824562/does-ruby-perform-tail-call-optimization
- https://dev.to/edisonywh/recursion-tail-call-optimization-and-recursion-2enh