Recentemente escrevi um artigo sobreRecursão em Ruby e algumas pessoas me pediram para complementar o artigo falando sobreTCO (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:

deffactorial(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 deestouro de pilha.

factorial(11_000)irb(main):012:0>factorial(11_000)Traceback(mostrecentcalllast):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 erroSystemStackError (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 oTCO (Tail Call Optimization).

O que é TCO (Tail Call Optimization)?

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

A estratégia consiste em transformar aspilhas 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:

deffactorial(number,accumulator=1)returnaccumulatorifnumber<=1factorial(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 paranumber inicialmente;
3. O acumulador (ou seja, o resultado) será retornado quando onumber 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 erroSystemStackError (stack level too deep) continuará acontecendo).

Para habilitar o TCO no ruby

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

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

Para facilitar segue todo o código:

deffactorial(number,accumulator=1)returnaccumulatorifnumber<=1factorial(number-1,accumulator*number)endRubyVM::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