Em 2022 durante um boletim de humor sobre a Copa do Mundo, os humoristas Daniel Furlan e Caito Mainier expuseram um dilema bem humorado sobre a tatuagem que havia sido feita nas costas do atacante Richarlison, com os rostos do Neymar, Ronaldo Fenômeno e o próprio Richarlison (A partir do minuto 4:30 do vídeo abaixo).
Segundo consta, o jogador Neymar possui uma tatuagem da irmã no seu braço e o fato de ela também possuir uma imagem do seu irmão poderia fazer com que o artista tatuador entrasse num loop infinito, dentro da tatuagem do Richarslison.
É uma piada genial, que introduz em nosso cotidiano um conceito que está bastante presente na Matemática e principalmente na Ciência da Computação: a Recursão.
Desejo demonstrar neste artigo que, se bem aplicada essa técnica pode trazer excelentes resultados. Sendo inclusive base de alguns algoritmos bem famosos.
Introdução
Segundo Adam Drozdek, em seu livro Estrutura de Dados e Algoritmos em C++, uma recursão acontece quando uma função de um sistema chama a si mesma durante o seu processamento, e na segunda execução pode chamar a si mesma uma terceira vez, e por aí vai.
Para evitar um loop infinito indesejado em nosso algoritmo é necessário definir uma “trava” para que ele pare de se alto referenciar.
Aditya Y. Bhargava define, em seu livro “Entendendo Algoritmos”, uma estratégia que eu considero bastante interessante e simples: definir um caso base e um caso recursivo.
Como exemplo, veja o código genérico abaixo. Ele basicamente:
- Define um método chamado subtraia que recebe como parâmetro um valor numérico qualquer.
- Mostra na Tela do usuário este valor
- Chama a função subtraia com o parâmetro numero menos um.
Infelizmente, esse código é uma implementação ruim, porque irá levar o nosso sistema a decrementar número eternamente.
Uma pequena modificação que podemos fazer é adicionar uma condição para que esta recursão pare de executar.
No exemplo de código consertado abaixo, podemos perceber que uma condição de parada (parâmetro numero ser maior que 1) evita que nosso algoritmo execute indefinidamente.
Porque não usar loops?
Nesse momento você deve estar se perguntando: se a intenção era subtrair um número até ele ser menor que zero, por que não usar um loop?
Esta é uma pergunta importante de ser feita, uma vez que esse exemplo realmente é mais simples de ser resolvido com a utilização de loops. Porém há alguns tipos de problemas que podem ser muito mais triviais de serem resolvidos com a utilização de iterações recursivas.
Por exemplo:
- Situações que envolvem hierarquias, onde o agente-pai também precisa herdar as mesmas características de seus descendentes (ex: Gerente que também é funcionário, avô que também é pai…)
- Atividades com regras sucessivas que envolvem algum tipo de empilhamento/desempilhamento (Torre de Hanoi é um exemplo clássico)
- Algoritmos de Divisão e Conquista como HeapSort ou QuickSort
Desvantagens
É claro que nem tudo são flores e há um pequeno detalhe que um programador deve ficar bem atento ao implementar esse tipo de estratégia:
Uma vez que precisam armazenar informações numa pilha para gerar o resultado final, as funções recursivas gastam uma quantidade maior de memória.
Irei usar o clássico exemplo de um cálculo de fatorial para melhorar o nosso entendimento.
Nesse algoritmo, o caso-base é conhecido: o fatorial de zero ser igual a 1.
Veja na figura abaixo, que o computador precisa armazenar todas as chamadas numa pilha, até chegar no caso base conhecido.
Tabela composta por 5 linhas e 3 colunas. Na primeira coluna da primeira linha está o valor 5 Fatorial que resulta em 5 vezes 4 fatorial (segunda coluna)., Na terceira coluna está a pergunta : quanto é 4 fatorial. E o padrão se estende até o 0 fatorial, cujo resultado é conhecido
Logo após, o algoritmo irá voltar respondendo as “perguntas” que ficaram pendentes até conseguir o resultado final.
Chamadas do fatorial de 5 executadas de baixo para cima, resultando no valor 120
Ou seja, pra calcular um fatorial de 5 foi necessário empilhar 5 “perguntas” a serem resolvidas depois que o caso base fosse encontrado.
Dessa forma, quanto maior a distância da primeira execução da função recursiva estiver do caso-base, maior será a pilha de chamadas que o Sistema irá guardar na memória e maior é a chance de o pobre programador receber algum alerta de StackOverflow em sua tela.
Conclusão
Recursão é um tema simples de entender, mas que em alguns casos pode ser extremamente complexo de ser aplicado.
A minha intenção de apresentá-lo foi para preparar nossa jornada rumo à análise de alguns algoritmos que dependem de recursão para funcionar.
Espero que o conceito tenha ficado claro e torço que assim como eu, você também passe a enxergar os filmes A Origem, Como se fosse a primeira vez, Meia Noite e um, Feitiço do Tempo e No Limite do Amanhã com outros olhos.
Um abraço e obrigado pela leitura.
