Gotas de Elixir – O que é tail recursion e como usar

Sabe quando você está aprendendo sobre chamadas recursivas e os professores e materiais avisam que nem sempre é uma boa ideia? Quando temos uma chamada recursiva, o compilador/interpretador precisa salvar o estado atual da chamada e criar uma nova chamada. Daí, ao executar a nova função a mesma coisa acontece, salva-se o estado anterior e faz-se uma nova chamada.

defmodule Fatorial do
  def normal(0), do: 1
  def normal(n), do: n * normal(n-1)
end

O código acima é a solução comum para o problema. Se você não entendeu o motivo de termos duas funções normal, veja o post anterior sobre pattern matching.

Apesar de simples, essa solução pode ser otimizada para evitar desperdícios de memória ao executar a recursão.

Tail Recursion

Tail Recursive é uma propriedade de funções em que não é necessário fazer nenhuma outra operação após a chamada recursiva a não ser retornar o valor. [1]

O exemplo anterior pode enganar pois a última ação da função é chamar ela mesma. Mas perceba que é preciso multiplicar n pelo retorno da função. Assim o compilador precisa ir salvando todos os valores de n para depois da última chamada recursiva calcular o valor de retorno.

Elixir implementa Tail Call Optimization, ou seja, se a função for otimizada para ao final apenas retornar o valor, sem nenhuma outra lógica, o compilador consegue economizar espaço em memória.

Podemos refatorar o código anterior e mover a multiplicação para dentro da chamada, com a ajuda de um acumulador e métodos auxiliares.

defmodule Fatorial do
  def otimizado(n), do: _fatorial_otimizado(n, 1)
  defp _fatorial_otimizado(0, acc), do: acc
  defp _fatorial_otimizado(n, acc), do: _fatorial_otimizado(n-1, acc*n)
end

Como vamos precisar de um acumulador, criamos a função privada _fatorial_otimizado para garantir que a interface do método continue a mesma (recebendo apenas o número n).

Inicialmente nosso acumulador será 1, para não interferir no cálculo do fatorial, já que n*1=n. Em seguida definimos o caso quando o número n chega a 0, retornando apenas o acumulador.

Por fim, lidamos com a recursão multiplicando n pelo acumulador antes de chamar a função com n-1. Assim, garantimos que depois da recursão não será necessário executar mais nada.

Nem tudo precisa ser otimizado

Premature optimization is the root of all evil – DonaldKnuth

(otimização prematura é a raiz de todo mal)

Elixir é uma linguagem bem eficiente com a ajuda da superpoderosa VM do Erlang. Esse exemplo do fatorial não consegui notar muita diferença entre o tempo de execução da versão normal e da otimizada.

A execução de Fatorial.normal(100_000) e Fatorial.otimizado(100_000) não teve ganhos significativos, mas quando o número subiu para 500.000 vi uma diferença de mais de um minuto. A diferença não está exatamente na velocidade de execução mas na memória consumida.

Para ter uma referência, implementando esse mesmo cenário em Scala, só consegui executar o fatorial de 100.000 depois que fiz a otimização para Tail Recursion. Antes disso a VM ficou sem memória.

Apesar de ser uma melhoria simples, é sempre bom entender melhor o contexto para tomar decisões de otimização.

 

Referências

[1] http://c2.com/cgi/wiki?TailRecursion

Anúncios

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s