Otimizando recursividade

March 9, 2021

Ontem eu aprendi sobre tail-call optimization em funções recursivas:

https://dino.codes/posts/tail-call-optimization-in-elixir/

Resumindo, podemos usar variáveis acumuladoras para reduzir a quantidade de instrucoes que o compilador executa em chamadas recursivas. Vou usar um exemplo do Elixir ja que otimizações em C dependem muito do compilador:

https://stackoverflow.com/questions/3514283/c-tail-call-optimization

defmodule UnoptimizedSum do
  def call(list), do: sum(list)

  defp sum([]), do: 0
  defp sum([head | tail]), do: head + sum(tail)
end

Em UnoptimizedSum, só começamos a adicionar os valores após o último sum() chamado:

UnoptimizedSum.call([5, 4, 3, 2, 1])
= 5 + UnoptimizedSum.sum([4, 3, 2, 1])
= 5 + (4 + UnoptimizedSum.sum([3, 2, 1]))
= 5 + (4 + (3 + UnoptimizedSum.sum([2, 1])))
= 5 + (4 + (3 + (2 + UnoptimizedSum.sum([1]))))
= 5 + (4 + (3 + (2 + (1 + UnoptimizedSum.sum([])))))
= 5 + (4 + (3 + (2 + (1 + 0))))
= 5 + (4 + (3 + (2 + 1)))
= 5 + (4 + (3 + 3))
= 5 + (4 + 6)
= 5 + 10
= 15

Isso significa que o compilador irá executar duas instruções para cada elemento da lista: uma para a chamada de sum e outra para a soma dos valores.

defmodule OptimizedSum do
  def call(list), do: sum(list, 0)

  defp sum([], accumulator), do: accumulator
  defp sum([head | tail], accumulator), do: sum(tail, accumulator + head)
end

Ja em OptimizedSum, somamos os valores antes de cada chamada recursiva:

OptimizedSum.call([5, 4, 3, 2, 1])
= OptimizedSum.sum([4, 3, 2, 1], 5)
= OptimizedSum.sum([3, 2, 1], 9)
= OptimizedSum.sum([2, 1], 12)
= OptimizedSum.sum([1], 14)
= OptimizedSum.sum([], 15)
= 15

Assim, executamos metade das instruções para a mesma operação. Acho que é um truque muito legal e vou tentar usá-lo com mais frequência.

Hoje vou continuar estudando Elixir e trabalhando no printf.