Estratégias para resolver problemas de forma recursiva

profile photo
Augusto Pinheiro
A recursão depende do problema que precisa ser resolvido. No entanto, existem alguns passos gerais que podem indicar a direção correta:
  1. Ordene seus dados
  1. Resolva os Casos Pequenos
  1. Resolva os Casos Grandes
Usaremos o exemplo simples de reverter uma string, ou seja, escreveremos a função de reverse tal forma reverse('Hello world') = 'dlrow olleH'. Para um melhor entendimento, é recomendável voltar à parte I e checar como essas etapas se aplicam à função Fibonacci e, em seguida, tomá-las e testá-las em outros exemplos.

Ordene seus dados

Este passo é a chave para começar a resolver um problema de forma recursiva, apesar de ser frequentemente negligenciado ou executado de forma implícita. Independentemente dos dados em que serão operados (números, cadeias de caracteres, listas, árvores binárias ou pessoas), é necessário encontrar explicitamente um ordenamento apropriado que indique uma direção a ser usada para reduzir a questão.
Essa estrutura depende inteiramente do problema, mas um bom começo é pensar nas ordenações óbvias: números vêm com suas próprias encomendas, sequências de caracteres e listas podem ser organizadas pelo seu comprimento, árvores binárias por profundidade, e pessoas podem ser ordenadas em um número infinito de maneiras sensatas, como altura, peso ou classificação em uma organização.
Lembre-se que este pedido deve corresponder ao grau de dificuldade para o problema a ser resolvido.
Podemos escrever o pedido como uma sequência:
0 , 1 , 2 ,…, n para inteiros (isto é, para dados inteiros d, graus (d) = d )
[], [■], [■, ■],…, [■,…, ■] para listas
(observe len = 0, len = 1,…, len = n ie para dados de lista d , grau (d) = len (d) )
Movendo-se da direita para a esquerda, passamos pelos casos gerais (“grandes”), para os casos de base (“pequenos”). Em nosso reverse exemplo, estamos operando em uma string, e podemos escolher seu comprimento como um pedido ou grau do problema.

Resolva os casos pequenos

Esta é normalmente a parte fácil. Com o pedido correto, é preciso examinar seus menores elementos e decidir como lidar com eles. Geralmente há uma solução óbvia: no caso de reverse(s), se chegarmos a len(s) == 0 e tivermos reverse(''), então sabemos a resposta, já que reverter a string não nos levaria a lugar algum.
Com os casos básicos resolvidos e o pedido em mente, solucionar o caso geral é tão simples quanto reduzir o problema de tal forma que o grau dos dados operados se move em direção aos casos-base.
Mas, atenção: é preciso ter cuidado para que nenhum caso básico se perca. Eles recebem este nome porque cobrem a base da ordenação e, em problemas de recursão mais complicados, é comum perdê-los, fazendo a etapa de redução operar com dados sem sentido e erros.

Resolva os casos grandes

Aqui, deve-se lidar com os dados diretamente nos pedidos, ou seja, dados de alto grau. Normalmente, eles são considerados dados de grau arbitrário e buscamos uma maneira de resolver a questão reduzindo-a a uma expressão contendo o mesmo problema de menor grau.
Em nosso exemplo Fibonacci, começamos com n arbitrário e reduzido fib(n) ao qual fib(n-1) + fib(n-2) é uma expressão contendo duas instâncias do problema com o qual iniciamos, mas de menor grau (n-1 e n-2 , respectivamente).
Quando se trata de reverse, podemos considerar uma string arbitrária de comprimento n, imaginando que a função reverse funciona em todas as strings de comprimento menor que n. Para resolver o problema dessa cadeia, invertemos a string sem o último caractere e, depois, levamos ele para a frente. Em código:
javascript
reverse(string) = reverse(string[-1]) + reverse(string[:-1])
onde string[-1] corresponde ao último caractere e, string[:-1], à string sem o último caractere (estes são pythonisms).  O último termo reverse(string[:-1]) é o nosso problema original, mas operando em uma cadeia de comprimento n-1. Logo, expressamos a questão em termos de um passo em direção à solução com o mesmo problema de grau reduzido.
Colocando a solução em nossa função reverse junta, obtemos:
javascript
reverse(string): if len(string) == 0: return '' else: return string[-1] + reverse(string[:-1])
Image without caption

Dicas finais

A única maneira real de melhorar a recursão é a prática. Cheque alguns dos milhares de problemas recursivos existentes e desafie-se a encontrar novos. E, caso tenha dificuldades, tente a iteração. Além de aprender a ser um programador melhor, a recursão é um método de resolução de problemas que pode tornar sua vida mais fácil.
Em problemas recursivos mais complexos, as etapas 2 e 3 da estratégia que vimos acima assumem a forma de um processo de feedback-loop mais cíclico. Se não for possível encontrar uma solução geral para o problema rapidamente, o melhor processo é resolver os casos gerais (“grandes”), e os casos de base (“pequenos”) em que você pode pensar. Então, veja como o seu método é dividido em diferentes partes de dados (isso deve desvendar casos de base e recursivos ausentes, ou quaisquer que estejam interagindo uns com os outros e precisem ser repensados).
Finalmente, lembre-se de que a ordenação é o passo mais importante para resolver um problema recursivo, e seu objetivo é cobrir os casos à direita (recursivo) e à esquerda (base).
Este conteúdo foi compartilhado por Augusto Pinheiro, CTO & FOUNDER da Fluke Operadora, e pode ser encontrado no blog dele.
post image
technology
programming
recursion
Programação recursiva
À primeira vista, o processo de recursão pode parecer causar mais dor de cabeça do que realmente solucionar questões. Mas a verdade é que, com esta técnica, os problemas são reduzidos e simplificados até serem resolvidos. Existem ...
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