Aprendendo recursão com decomposição em fatores primos
Recursividade ou recursão é uma prática poderosa na programação. Grosso modo, é a versão funcional dos laços de repetição. Vamos fazer uma explicação rápida utilizando a decomposição de fatores primos como base.
O conceito
Decomposição em fatores primos
Decomposição em fatores primos é o processo pelo qual encontramos o número ou números que, quando multiplicados, resultam no número dado. Esses números são os fatores primos de um dado valor.
Para encontrar os fatores primos de um dado valor A, dividimos A pelo menor número primo pelo qual A seja divisível. Repetimos o processo para cada número seguinte até chegar a 1.
Recursão
O processo explicado acima onde repetimos uma operação várias vezes até chegarmos a um valor é conhecido como repetição. A forma mais comum e inicialmente ensinada é a iteração, onde repetimos uma operação até que uma condição seja atingida.
A recursão, por sua vez, é o processo onde declaramos o resultado de uma função nos termos dela mesma. Um exemplo natural de recursão é a declaração os descendentes de uma pessoa são os seus pais mais os descendentes dos seus pais. Essa definição faz com que, para termos uma lista completa dos descendentes de uma pessoa, precisemos também ter uma lista completa dos descendentes dos seus pais, o que faz com que repitamos a operação até chegar a uma pessoa sem descendentes.
Recursão é um método de solução de problemas onde a solução depende da solução de versões menores do mesmo problema […] O poder da recursão está na possibilidade de definir uma série infinita de objetos em uma declaração finita […] mesmo que este programa não contenha nenhuma repetição explícita.
— Niklaus Wirth, Algorithms + Data Structures = Programs (1976)
A solução
Uma das primeiras coisas que vem à mente da maioria dos programadores são laços de repetição. No entanto, podemos resolver esse problema de forma muito mais elegante utilizando recursão.
Aqui estão os passos que precisamos seguir para encontrar os fatores primos de um valor val:
- Encontrar o menor número primo primo tal qual val % primo = 0;
- Dividir val por primo e guardar o valor resultado;
- Repetir a operação com o resultado até que resultado seja 1
Com isso, devemos ter resultados como fatores_primos(5) = [5] e fatores_primos(100) = [2, 2, 5, 5].
Vamos escrever nossa solução em Python 3, mas será simples adaptá-la para outra linguagem de sua preferência. Vamos começar escrevendo os testes:
Primeiro, vamos definir a função sem implementá-la:
def fatores_primos(num):
passO primeiro passo da fatoração que vamos implementar é encontrar o menor fator primo de um número. Para isso, precisamos saber
- se um dado número n é primo;
- se n é um fator de num, isto é, se o resto de num / n é igual a zero
Para saber se um número num é primo, existem muitos métodos — alguns são mais eficientes que outros. Aqui vamos usar o mais simples, e não o mais rápido:
Essa função garante que nenhum número entre 2 e num seja um divisor de num.
Agora, para encontrar o menor fator primo de um número num, basta passar por todos os números inteiros menores ou iguais a num até que um deles seja primo e também um fator de num. [Nota: aqui estamos utilizando iteração (através do laço for). O exemplo de recursão será feito na função principal.]
Agora, basta aplicar a lógica repassada acima para encontrar os fatores primos. Caso atinjamos o número 1, a lista de fatores primos consiste apenas no próximo número (isto é, a lista de fatores de 5, um número primo, consiste apenas no próprio número 5).
Pronto! Agora nossa função chamará a si mesma com a lista modificada e o próximo número até que o valor atinja 1, e passamos todos os testes. Usando o número 100 como exemplo, o processo ocorre da seguinte forma:
# MFP = menor fator primo
fatores(x) = [ MFP(x), *fatores( x / MFP(x))]
fatores(100) = [MFP(100), *fatores(100 / MFP(100))]
fatores(100) = [ 2, *fatores(100 / 2)]
fatores(100) = [ 2, *fatores(50) ]
fatores(100) = [ 2, *[MFP(50), *fatores(50 / MFP(50))]]
fatores(100) = [ 2, *[ 2, *fatores(50 / 2)]]
fatores(100) = [ 2, *[ 2, *fatores(25)]]# ... e assim por diante até resolver todos os fatoresfatores(100) = [2, *[2, *[5, *[5]]]]# o operador * adiciona os elementos de uma lista dentro
# da lista que está acima ("achata" as listas)fatores(100) = [2, 2, 5, 5]
Abaixo temos o código final, que passa os testes:
Conclusão
Conceitos de programação funcional podem parecer muito científicos, mas com o tempo e alguma imersão você começará a enxergar soluções funcionais para problemas práticos. Esse foi apenas um exemplo de como podemos aplicar recursão em um problema real, mas tenho certeza que você encontrará vários outros!
Gostou do artigo? Não esqueça de aplaudir! Se tiver sugestões ou correções, por favor entre em contato com o autor.
