O que é recursão e Tail-Call Optimization (TCO) ?

Ao começar a aprender sobre programação funcional, um dos primeiros conceitos que se precisa entender é o de recursão, uma vez que essa mecânica é usada para permitir um programa a trabalhar em cima de conjuntos de coisas (por exemplo listar todos funcionários de uma empresa), manter-se rodando indefinidamente (loop, usado para manter um programa rodado por tempo indefinido) e até produzir conteúdo indefinidamente (como produzir números primos on-demand).

Segundo o Priberam, no contexto de informática, recursão pode ser definida como “Propriedade de função, programa ou afim que se pode invocar a si próprio”[1]. Isto é, em termos práticos, podemos exemplificar recursão como uma função chamando a si mesma. Veja:

Como pode se ver no codigo acima, a função funcao_recursiva chama a si própria; isso por si só é recursão; simples assim.

Dando voltas com a recursão

O objetivo da recursão é lidar com problemas de uma forma natural. Por exemplo, digamos que queremos enviar um email para cada conhecido da nossa lista de email, certo ? Programaticamente falando isso significaria pegar uma lista de endereços e para cada um deles enviar um email; veja o exemplo:

No exemplo acima, a função enviar_email_para_varios_contatos recebe uma lista de endereços, pega o primeiro (variável email) e separa do resto; então envia o email (usando a função codigo_que_vai_enviar_o_email), retornando true se esse for o último email da lista ou passando o resto de volta para a função.

Perfeito, espero que até aqui esteja suficientemente claro que recursão é basicamente você fazer com que uma função fique executando a si mesma como forma de passar por uma lista ou fazer algo similar.

Recursão é ineficiente ?

Uma das primeiras coisas que você deve ter ouvido sobre recursão, especialmente se você cursou ciência da computação, é que ela é ineficiente. Isso é uma meia-verdade, vou explicar o porquê:

Primeiro, vamos entender por que alegam que recursão é ineficiente; considere o código abaixo:

Basicamente o que o código faz é “considerando uma lista, pegue o primeiro elemento e some com o resto da lista (para cada elemento da lista); caso este seja o fim da lista, considere como zero”. Assim, para a execução de soma([1, 2, 3, 4]) , esperamos o resultado 10 (que é a soma de todos os números da lista).

Tudo bem até aí, né ? Agora vamos fazer uma analogia com matemática. Considere:

1 + x = ?

Qual o resultado ? Não temos como saber porque x não é um número, por isso precisamos descobrir o que é x :

1 + x = ?
x = 2 + y = ?

Ok, agora sabemos que x é 2 + y. Mas o que é y ? Não sabemos, então temos que continuar expandindo até o fim:

1 + x = ?
x = 2 + y
y = 3 + z
z = 4
Portanto
1 + x =
1 + (2 + y) =
1 + (2 + (3 + z)) =
1 + (2 + (3 + (4))) =
1 + (2 + (7)) =
1 + (9) =
10

Se não ficou muito claro, vejamos como uma representação da stack em si:

soma([1, 2, 3, 4])
-> 1 + soma([2, 3, 4])
       -> 2 + soma([3, 4])
              -> 3 + soma([4])
                     -> 4
              -> 3 + 4
       -> 2 + 7
-> 1 + 9
// 10

Viu quantos passos foram necessários para chegar ao resultado ? Considere que no contexto de programação, cada passo dessa operação é uma execução de função que consome memória etc, então estamos gastando muito por algo simples; se fizessemos direto 1 + 2 + 3 + 4teríamos o resultado sem todo esse trabalho, né ? É por isso que dizem que recursão é ineficiente.

No entanto, no mundo real, hoje em dia, isso não é mais verdade pois temos diversas otimizações de operações de recursão como a tail-call optimization (ou em português, otimização de chamada de cauda).

Ok, mas o que é Tail-Call Optimization ?

Então, considerando que computadores têm recursos (como memória e processamento) finitos e que queremos um programa rápido sem desperdiçar desnecessariamente esses recursos, cientistas bolaram um meio de se fazer recursão sem que se aumente exponencialmente a quantidade de recursos gastos para poder passar por uma lista de coisas.

Vamos falar sobre stack. Computadores precisam de memória para rodar programas, certo ? (se você jogou Minecraft ou qualquer outro jogo 3D indie no começo, tu vai se lembrar que eram super lentos e quebravam muito e sempre falavam que para consertar era só comprar mais memória, né ?) Então, essa memória é usada para armazenar o código compilado do seu programa e para armazenar as informações usadas numa execução de código. Talvez eu faça no futuro um artigo explicando isso em mais detalhes mas se quiser saber mais, leia sobre a Arquitetura de von Neumann.

Bem, imagine o seguinte código:

Então, se fossemos executar esse código, além de armazenar na memória o código compilado, precisaríamos armazenar na parte de execução que o código começou executando funcao0() , que existe a variável a com o valor 1 , que a funcao0() chamou a funcao1 passando 1 como argumento e que esse valor 1 foi colocado na variável input etc…

Então, a parte que armazena que funções estão sendo chamadas (eg: funcao0 -> funcao1 -> console.log e qual argumento é usado para elas é a stack, as variáveis e seus valores ficam em outra parte chamada heap. Não se preocupe, não é importante memorizar isso, só entender que cada chamada de função precisa ocupar memória.

Bem, considerando que precisamos armazenar cada função que chamamos, isso não significaria que numa recursão teríamos que armazenar nessa stack inúmeras vezes que a função foi chamada ? Sim… E aqui começa a parte interessante: sabendo que recursão é ineficiente basicamente por ter que armazenar informação de inúmeras chamadas a si mesmo, não teria como fazer a mesma coisa mas sem armazenar essas informações das chamadas de função ? Sim, isso é o tal do TCO.

Vamos então entender direitinho como essa otimização é feita:

Considere que loop está chamando a si própria, por que precisamos então adicionar na stack informação de cada chamada a si mesma se o fluxo será o mesmo ? Talvez pudéssemos, sabendo disso, só armazenar informação da chamada uma vez e a reutilizar mudando só qual parâmetro está sendo usado para isso.

Pois é, é isso que é a tail-call optimization: uma simples otimização do compilador que identifica que uma função está se chamando de forma recursiva e então usa algumas trapaças de computação para que não se armazene informação inútil na stack.

Como ela sabe que está chamando a si mesma ? Ela vê que a última operação chamada no corpo da função é a própria função; isto é:

Como você pode ver, funcao_nao_otimizada e funcao_nao_otimizada2 são basicamente a mesma coisa. Elas não podem ser otimizadas porque a gente precisa executar as chamadas até o fim para então somar o resultado de uma com a outra (vide o exemplo que usamos lá em cima). No entanto, funcao_otimizada é um tanto differente, ela tem uma variável a mais que guarda o valor contado até então e ela chama a si mesma até bater no 0; por isso o compilador consegue dizer com segurança que a função é recursiva e aplicar as modificações necessárias para que a stack não se expanda ao executá-la.

Segredo de Charlotte: Nas implementações de diversas linguagens, a otimização de tail-call é feita aplicando uma iteração (um loop de for). Isso mesmo, mutável, feio e eficiente.
Mas esse é um segredo só entre eu, você e o compilador, viu ? 🤫

Muito curioso como programação é algo que evolui tão rápido que poucas décadas atrás era inviável programar com recursão e hoje ela é uma forma cada vez mais adotada.

Bem, por hoje é só isso, mas que tal no próximo artigo falarmos sobre como o compilador moderno tem o dever de ajudar o programador ? :)

Poste nos comentários suas dúvidas, impressões e até a história de como foi para você se envolver com as comunidades de programação!

Créditos

Desenho “Moinho” por Webalys - Streamline Illustrations.
Desenho “Quadrinho XKCD” por XKCD — Functional

Referências bibliográficas

[1] Dicionário Priberam da Língua Portuguesa — https://dicionario.priberam.org/recursividade [consultado em 18–04–2019].