Conceitos de Programação: Tail Recursion

February 1st, 2008 § 8 comments

Este é o segundo artigo em uma série sobre conceitos de programação. O primeiro falava sobre Lazy Evaluation e como simular isso em uma linguagem sem suporte nativo ao conceito de uma forma simples mas funcional.

Neste segundo artigo, vamos explorar um assunto que possui aplicações bem práticas: Tail Recursion. Como a maioria dos programadores pode atestar, recursividade é uma maneira elegante de resolver várias classes de problemas sem muito esforço. Embora seja um conceito que pode confundir programadores inexperientes, uma marca de um bom programador é saber usar recursividade com eficiência.

Um dos maiores problemas da técnica, é claro, é o consumo espaço na pilha. Como cada chamada precisa criar um novo frame, funções profundamente recursivas podem esgotar rapidamente o espaço disponível gerando problemas de difícil depuração. Além disso, há o fato de que é muito fácil escrever uma função recursiva mas não tão fácil escreve uma função que saia rapidamente quando as condições não são apropriadas.

Esses dois problemas dependem muito da capacidade do programador em criar bons algoritmos. Mas o primeiro pode também receber ajuda do compilador em uma otimização conhecida como tail call optimization.

Na prática

Para mostrar como isso funciona, considere a seguinte função em Ruby:

def factorial(i)
  return 1 if i <= 0
  return i * factorial(i - 1)  
end

Essa é uma implementação trivial de um cálculo de fatorial que sofre do problema mencionado acima. À medida que as chamadas são feitas, o espaço na pilha é eventualmente consumido até que haja um estouro. Na minha máquina isso acontece depois de aproximadamente três mil chamadas para o Ruby 1.8.6 compilado nativamente.

Suponha que você faça a seguinte chamada:

factorial(5)

O resultado é 120 com a seguinte seqüência de chamadas:

factorial(5)
5 * factorial(4)
5 * 4 * factorial(3)
5 * 4 * 3 * factorial(2)
5 * 4 * 3 * 2 * factorial(1)
5 * 4 * 3 * 2 * 1

Veja que a função é chamada internamente mais quatro vezes e sempre ao final da execução. Apesar disso, esse não é um exemplo de tail recursion. O motivo é que a multiplicação acontece depois da chamada, ou seja, a invocação é feita ao final mas o retorno só pode ser conhecido com a multiplicação posterior.

Agora, veja a seguinte implementação:

def factorial_accumulate(n, a)
  return a if n <= 1
  return factorial_accumulate(n - 1, n * a)
end

def factorial(n)
  factorial_accumulate(n, 1)
end

Note que agora a chamada vem ao final, mas o resultado não depende de algo posterior. As chamadas seriam assim, para o mesma invocação factorial(5):

factorial(5)
  factorial_accumulate(5, 1)
    factorial_accumulate(4, 5)
      factorial_accumulate(3, 20)
        factorial_accumulate(2, 60)
          factorial_accumulate(1, 120)
          120
        120
      120
    120
  120
120

É aqui que entra a otimização.

Considerando a forma como funções executam, é fácil perceber que cada chamada poder ser implementada de maneira bem mais eficiente com duas substituições.

Ao invés de criar um novo frame na pilha, salvar o endereço de retorno, empilhar as parâmetros, executar a função, repetir recursivamente e ao final ir desempilhando com os retornos, é possível substituir os parâmetros na pilha e pular novamente para o início da função.

Em outras palavras, você teria algo assim, em um pseudo-código:

:fa
  
  n <= 1 ?
    goto :fe
  
  n = n - 1
  a = a * n
  
  goto :fa
  
:fe

A otimização está toda centrada no fato de que se a função é chamada de maneira similar, a invocação pode ser substituída por um salto direto precedido por uma troca dos parâmetros de maneira apropriada.

Um segundo exemplo

Para ilustrar um pouco mais o tipo de transformação necessária, vamos usar a clássica função de Fibonacci:

def fib(n)
  return 1 if n <= 1
  return fib(n - 1) + fib(n - 2)
end

Essa função também não é tail recursive mas pode ser transmudada facilmente com a seguinte implementação:

def fib(i, current = 0, next = 1)
  return current if i == 0
  return fib(i - 1, next, current + next)
end

Obviamente, esse é um exemplo bem básico mas ilustra o tipo de mudança necessária para uma otimização.

Uma pequena distinção

Na literatura sobre o assunto, dois termos são usados: tail recursion elimination e tail call optimization. O primeiro é um caso especial do segundo em que a chamada é para a própria função.

A função factorial_accumulate, mostrada acima, poderia sofrer tail recursion elimination, demonstrado no pseudo-código. Já a segunda implementação de factorial, que chama factorial_accumulate poderia sofrer tail call otimization.

Implementações

Esse tipo de otimização é freqüentemente usado linguagens funcionais já que o uso de recursividade declarativa nas mesmas é extremamente comum e não poderia ser implementado da maneira usual sem tornar as mesmas inúteis para qualquer coisa além de operações básicas. De fato, a otimização é necessária para a implementação de certos estilos de programação que eventualmente discutiremos nessa série.

Surpreendentemente, muitas linguagens modernas suportam automaticamente alguma forma dessa otimização. É o caso, por exemplo, da CLI, a infra-estrutura de linguagens por trás do .NET. Embora nem todas as linguagens sob a CLI façam uso da otimização (C# não faz, por exemplo), ela é perfeitamente possível. F#, que é funcional, usa e, ironicamente, C++ dentro do .NET também em certas condições. Linguagens baseadas em CLI podem fazer uso das funcionalidades caso desejem.

Outra linguagem que possui um suporte muito bom a isso é Lua. O compilador GCC, padrão na maioria das plataformas Unix, também é capaz de otimizar chamadas recursivas em certos casos.

Erlang, que tem chamada bastante a atenção de desenvolvedores modernos e já está em uso em vários locai como na Amazon, é outra com um bom suporte.

Leitores que usam Ruby ficarão felizes em saber tanto YARV como JRuby já suportam uma forma básica de tail call optimization e devem eventualmente suportar formas mais complexas.

O que isso significa

Conhecer e saber aproveitar as características sutis de uma linguagem é um passo essencial para a maestria na mesma. Muitos problemas podem ser resolvidos com chamadas recursivas próprias que podem acabar sendo otimizadas em muitos compiladores atuais sem que você perceba.

Obviamente, existem casos em que uma implementação recursiva pura é mais interessante para efeitos de performance. Por outro lado, se o problema não exige uma pilha enorme, muitas vezes recursividade é um bom componente para melhorar a legibilidade do código. É necessário saber balancear as duas coisas.

Finalmente, é sempre bom lembrar que, como qualquer técnica, a implementação final depende do compilador ou interpretador. Em muitos casos, recursividade simples pode acabar sendo mais eficiente e se você precisa de máxima performance, é interessante testar variações sobre o tema para realmente identificar o que funciona.

Conclusão

Espero que isso tenha ajudado a compreender um pouco do que é tail recursion. Como sempre, quaisquer dúvidas, correções e sugestões podem ser feitas nos comentários. Na próxima sexta-feira retornamos com mais um artigo.

§ 8 Responses to Conceitos de Programação: Tail Recursion"

Leave a Reply

Your email address will not be published. Required fields are marked *

What's this?

You are currently reading Conceitos de Programação: Tail Recursion at Superfície Reflexiva.

meta