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
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)
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
O que mudou?
- Foi adicionado mais 1 argumento na assinatura do método para servir como acumulador do resultado;
- 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; - O acumulador (ou seja, o resultado) será retornado quando o
number
for igual ou menor a 1; - Fazendo essas mudanças garantimos que a última chamada será o próprio método sem depender de outro fator ou variável;
- 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
}
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)
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
Top comments (1)
Ótimo post!
Obrigado por compartilhar :)