DEV Community

Diego Novais
Diego Novais

Posted on • Edited on

3 1

TCO (Tail Call Optimization) - Ruby

Recentemente escrevi um artigo sobre Recursão em Ruby 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:

def factorial(number)
  number == 1 ? 1 : number * factorial(number - 1)
end
Enter fullscreen mode Exit fullscreen mode

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

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)
Enter fullscreen mode Exit fullscreen mode

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:

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

  factorial(number - 1, accumulator * number)
end
Enter fullscreen mode Exit fullscreen mode

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

RubyVM::InstructionSequence.compile_option = {
  tailcall_optimization: true,
  trace_instruction: false
}
Enter fullscreen mode Exit fullscreen mode

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

Para facilitar segue todo o código:

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)
Enter fullscreen mode Exit fullscreen mode

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:

Heroku

This site is built on Heroku

Join the ranks of developers at Salesforce, Airbase, DEV, and more who deploy their mission critical applications on Heroku. Sign up today and launch your first app!

Get Started

Top comments (1)

Collapse
 
evertonlopesc profile image
Everton Lopes

Ótimo post!
Obrigado por compartilhar :)

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more