Programação recursiva

profile photo
Augusto Pinheiro

Como resolver um problema fingindo que ele já foi solucionado

Apesar de muitas vezes ser introduzido desde o início na maioria dos empreendimentos em programação, o conceito de recursão pode parecer estranho e potencialmente desanimador ao ser encontrado pela primeira vez. Parece quase paradoxal: como podemos encontrar uma solução para um problema usando a solução para o mesmo problema?
Image without caption
Para se familiarizar com o conceito de recursão, é preciso perceber que trata-se de mais do que uma prática programática  —  é uma filosofia de solução de problemas. A recursão é adequada para questões que podem ser trabalhadas e parcialmente resolvidas, deixando o restante da questão na mesma forma, mas simplificada.
Isso não se aplica apenas a funções na programação, já que podemos enquadrar problemas cotidianos simples usando esta prática. Por exemplo, vejamos a produção deste artigo: digamos que o objetivo seja chegar em 1000 palavras. Se 100 palavras forem escritas toda vez que o documento for aberto, em 10 repetições o problema é solucionado.
O código para escrever este texto poderia ser assim:
plain text
write_words(words_left): if words_left > 0: write_100_words() words_left = words_left - 100 write_words(words_left)
O algoritmo também pode ser implementado iterativamente:
plain text
write_words(words_left): while words_left > 0: write_100_words() words_left = words_left - 100
Se percorrermos a função chamada write_words(1000)com a implementação, veremos que ela tem exatamente o mesmo comportamento. De fato, todo problema que podemos resolver usando recursão, também podemos solucionar usando iteração ( forwhileloops). Então, por que escolheríamos esta técnica?
Image without caption
Por que recursão?
Alguns problemas são mais fáceis de resolver utilizando recursão ao invés de iteração. Às vezes, a recursão é mais eficiente e/ou mais legível; outras vezes, ela não é mais legível, mas é mais rápida de implementar. Existem estruturas de dados, como árvores, que são adequadas para algoritmos recursivos.
Há, até mesmo, algumas linguagens de programação sem nenhum conceito de loop (linguagens puramente funcionais), como o Haskell, que dependem inteiramente da recursão para resolução iterativa de problemas.
O ponto é simples: não é preciso entender a recursão para ser um programador, mas é preciso entender a recursividade para se tornar um bom programador. Compreender a recursão é sinônimo de ser um bom solucionador de problemas, mesmo fora da programação.

A essência da recursão

Em geral, com a recursão, repetimos o processo da divisão de um problema (dando o mesmo passo em direção ao desfecho) até chegarmos a uma versão da questão com uma solução muito simples (chamada de caso base). Isso resolve o nosso problema original.
Image without caption
Podemos resolver P ao dividir o problema em um passo para a solução de um problema menor remanescente da mesma forma que o original, até chegarmos a uma resolução simples para um pequeno problema (um caso base).
Suponhamos que nos sejam concedidas algumas informações reais de algum tipo de dado. Vamos chamá-lo de dₒ. A ideia com recursão é fingir que já resolvemos o problema ou calculamos a função desejada f para todas as formas desse tipo de dado que são mais simples que dₒ, de acordo com algum grau de dificuldade que precisamos definir.
Então, podemos encontrar uma maneira de expressar f (dₒ) em termos de um ou mais f (d)s, onde todos esses ds são menos difíceis (têm menor grau ) que dₒ. Assim, encontramos uma maneira que reduz e resolve para f (dₒ).
Ao repetir este processo, espera-se, em algum ponto, que o restante de f (d)s ficará tão claro que poderemos facilmente implementar uma solução fixa e fechada. Dessa maneira, o desfecho do problema original se revelará como nossas soluções para questões progressivamente mais simples, agregadas e em cascata de volta ao topo.
No exemplo da produção deste artigo, os dados são o texto (contido neste documento esperando para ser escrito) e o grau de dificuldade (que é o tamanho do documento). É um exemplo simples, mas supondo que o problema f (900), de como escrever 900 palavras, já tenha sido concluído, então o que resta para resolver f (1000) é escrever 100 palavras.
Um exemplo mais completo é encontrado quando consideramos os números de Fibonacci, onde o primeiro algarismo é 0, o segundo é 1 e o número de nᵗʰ Fibonacci é igual à soma dos dois anteriores.
Digamos que temos uma função Fibonacci que nos diz o número nᵗʰ:
plain text
fib(n): if n == 0: return 0 if n == 1: return 1 else: return fib(n-1) + fib(n-2)
Como é a execução desta função? Vamos tentar fib(4):
Image without caption
A visualização de uma árvore de recursão é possível ao considerar que o cálculo recursivo que leva a fib (4) é igual a 3. Observe que o cálculo é realizado em profundidade primeiro.
Um mantra útil para adotar a resolução de problemas de forma recursiva é “fingir até que você faça, isto é, simular que um caso mais simples já foi resolvido e, então, tentar reduzir o problema maior para encontrar a solução para a questão.
Se um problema é adequado à recursão, deve haver apenas um pequeno número de casos simples que precisam ser resolvidos explicitamente. Assim, este método de redução para um problema mais simples pode ser usado para solucionar todos os outros casos.
Isto é exemplificado no caso de Fibonacci, fib, onde, se definirmos fib(n)como algo que já calculamos, entãofib(n-1)fib(n-2), como esperávamos, se transforma em cascata e reduz o problema a casos progressivamente mais simples, até chegarmos a fib(0)fib(1), que terão soluções fixas e fáceis.
Image without caption
Faça de conta até dar certo!
Esta é primeira parte do nosso conteúdo sobre o conceito de recursão. Neste artigo, procuramos deixar claro como esta prática funciona e como é possível simular que a solução já existe para resolver um problema. Em breve, compartilharemos dicas e estratégias para te auxiliar a resolver questões de maneira recursiva. Fique ligado!
Este conteúdo foi compartilhado por Augusto Pinheiro, CTO & FOUNDER da Fluke Operadora, e pode ser encontrado no blog dele.
post image
Para construir um bom software, sem bugs ou falhas, é necessário ter um fluxo de code review bem estabelecido. Todo dev está sujeito a erros ao programar, e é importante poder contar com um processo de revisão para garantir a qual...
post image
neural networks
programming
coding
technology
Redes neurais artificiais
Warren McCulloch e Walter Pitts criaram um modelo computacional que abriu o caminho para a pesquisa da rede neural dividida em duas abordagens: uma de processos biológicos no cérebro e outra focada na aplicação de redes neurais à ...
Powered by Notaku