Enquanto estava estudando a linguagem de programação Lua, em um capítulo sobre elementos funcionais da linguagem, me deparei com uma explicação interessante para tail recursion. Nela, o autor do livro (Programming in Lua, 1ª Edição) falava como a linguagem implementa completamente tail recursion(que acho que fica bem traduzido como recursão de cauda). Até aí tudo legal, mas melhora.

Bem, pra demonstrar que implementa e também explicar o conceito, o autor se utiliza de um jogo-exemplo: um labirinto. O jogo constrói o labirinto através de funções que chamam umas às outras, porém utilizando-se de recursão de cauda para manter sempre o uso de memória como se só houvesse uma função. Explicação e o exemplo utilizado podem ser encontrados aqui.

Explicando melhor recursão de cauda: o princípio é que não precisamos que uma função fique esperando o retorno de um resultado de outra para terminar sua execução, como acontece normalmente. Se você faz uma função em C, ou um método em Java, que termina com um comando return outraFuncao;, a função original ficaria esperando o termino da chamada para poder terminar sua execução. Só que outraFuncao pode fazer chamadas a outras funções, e essas a mais outras, e assim por diante. Tal carga será deixada para a memória, que acabará por estourar(um stack overflow, ou estouro de pilha). Mas perceba que, no caso de uma instrução final de uma função, não há motivo para a espera de retorno da chamada. Pode-se simplesmente indicar que o retorno será o da função agora chamada, e limpar a memória utilizada pela execução da original. É isto que linguagens funcionais como Haskell e Scheme e linguagens com fortes influências, como Lua, implementam.

A novidade que gostaria de compartilhar aqui é uma implementação do mesmo código feito em Lua, para Haskell. O código pode dar origem a um jogo bastante complexo e infinitamente escalável, já que ao chamar uma nova função (entrar em um novo quarto) nenhuma informação é mantida da que chama, e sua execução é encerrada por completo. Código em Haskell abaixo:

import IO

main = do
         room1

room1 = do
          putStrLn "You're in room #1"
          text <- getLine
          if text=="south" then
            room3 -- movendo-se pro quarto 3
            else
              if text=="east" then
                room2 --movendo-se pro quarto 2
                else
                  putStrLn "Invalid move" >>
                  room1 --permanece no mesmo quarto

room2 = do
          putStrLn "You're in room #2"
          text <- getLine
          if text=="south" then
            room4
            else
              if text=="west" then
                room1
                else
                  putStrLn "Invalid move" >>
                  room2 

room3 = do
          putStrLn "You're in room #3"
          text <- getLine
          if text=="north" then
            room1
            else
              if text=="east" then
                room4
                else
                  putStrLn "Invalid move" >>
                  room3 

room4 = do
          putStrLn "You're in room #4! You won!"

O código é simples, elegante, e correto. É este mesmo comportamento que torna a recursão um ponto tão forte em Haskell: iteração não é necessária à linguagem pois recursividade não apresenta peso adicional algum ao código. Isto nos permite escrever funções recursivas muito mais poderosas do que podemos encontrar em uma linguagem como C ou Java, onde a pilha de execução não suporta tantas chamadas quanto uma tarefa mais complexa possa precisar(ex.: inserção em uma árvore AVL com 100 mil nós). Isso nos permite executar códigos como o clássico exemplo do fatorial:

fact x = if x < 0 then error"Fatoriais sao de numeros positivos!"
                       else fact2 x 1 where
                              fact2 0 acumulador = acumulador
                              fact2 x acumulador = fact2 (x-1) (acumulador*x)

Pode-se rodar este exemplo e calcular o fatorial de 100 mil, o que não é possível com recursão em C. Apesar do peso do alto nível de abstração, vemos aí parte do poder do paradigma funcional e da linguagem Haskell!

PS: Erro corrigido no quanto à recursividade do fatorial. Ah, e o exemplo do fatorial pode não dar Stack Overflow, mas dependendo da entrada você pode atingir picos de uso de CPU. =)