Uma Introdução à Recurssão

A recorrência é uma ferramenta brilhante para a programação. Fornece uma solução simples mas poderosa para abordar vários problemas. Dito isto, a recursividade pode por vezes ser um pouco complicada, especialmente para principiantes. As pessoas têm muitas vezes dificuldade em pensar recursivamente para ver como podem abordá-la. Além disso, as pessoas também têm dificuldade em escrever um programa recursivo que não demore um tempo excessivo a correr. Neste artigo vamos discutir os fundamentos da recursividade, ajudando-o a refinar ou desenvolver esta habilidade de programação essencial.

Recurssão Explicada

A recorrência é um método para resolver problemas através de categorias mais pequenas da mesma questão. Resolvemos problemas através dos sub-problemas até chegarmos à sua versão mais pequena, também conhecida como o caso base. As pessoas têm frequentemente dificuldade em compreender a recorrência por várias razões. Uma função recursiva continua a chamar-se a si própria até a execução parar, e uma condição de base torna-se verdadeira. Há duas partes duas: uma função recursiva:

• O Caso Base
• A Estrutura Recursiva

Caso Base

A base é a parte mais pequena do problema. Surpreendentemente, conhecemos a condição terminal ou solução onde a função poderia devolver imediatamente os resultados.

A Estrutura Recursiva

Encontrar a resposta a um problema através da solução do seu sub-problema é uma estrutura recursiva. Mais uma vez, as coisas tornam-se confusas à medida que a função se autodenomina por quebrar o actual desafio a um nível simples.

Compreender a Recurssão através do Problema da Contagem Decrescente

Deve imprimir números começando por N a um em ordem decrescente. Temos de quebrar a solução do problema para encontrar versões mais pequenas do problema. Portanto, seria melhor imprimir primeiro N e depois chamar a função para imprimir o resto do N para um número.

Imprimir números de N a um igual a imprimir (N) + Imprimir de N-um a um
Neste exemplo, o primeiro é o problema original, e o segundo (N-one to one é o subproblema.) Deve estar a pensar, a cadeia de chamadas funcionais deve parar em algum lugar, e qual poderia ser o caso base?

Caso de base

A contagem decrescente deve ser concluída após a impressão de um. Agora, temos de introduzir uma condição de base para terminar a execução do programa. Devemos agora misturar o caso base, e a estrutura recursiva para escrever toda a implementação recursiva do problema discutido anteriormente.

Qual é o ponto de utilização da recursividade?

A recursividade brilha frequentemente em situações com problemas complexos. Seria mesmo justo dizer que se eleva às ocasiões em que o problema é mais complicado do que o habitual. Além disso, é possível aplicar a recorrência com quase todos os problemas. Contudo, há cenários particulares em que a recorrência será especialmente útil. Aqui está uma situação em que a recursividade é a que mais brilha.

Gráficos, Redes, Hierarquias

Quando discutimos algoritmos e falamos de gráficos, normalmente não estamos a conversar sobre o gráfico destacando a relação entre variáveis, tais como o gráfico de classificação do Top Coder (Centra-se na relação entre a sua classificação e o tempo.)Em vez disso, estamos sobretudo a falar de uma teia de pessoas, coisas, e conceitos ligados de várias maneiras.

Por exemplo, pode-se imaginar um mapa de estradas como um gráfico que mostra as cidades e as suas ligações com as estradas. Os gráficos podem ser massivos, complicados, e complicados de lidar, programados. Além disso, são bastante semelhantes em concursos de algoritmos e na teoria dos algoritmos. Felizmente, pode-se usar a recorrência quando se trabalha com elementos complicados como redes e gráficos.

Como resolver problemas usando a recursividade?

Ficaria surpreendido se soubesse o quanto precisará de utilizar o seu processo de pensamento para resolver problemas recursivamente. Aqui está um método eficaz que deve considerar, uma vez que o ajudará a decidir os casos base e a estrutura recursiva com facilidade:

• Como posso resolver se encontrar uma solução, encontrando sub-problemas de uma questão mais significativa?
• Não vale a pena preocupar-se com o problema do sub-problema, uma vez que a recursividade irá lidar com ele
• Anotar uma estrutura recursiva com as condições de contorno e o parâmetro de função correctos
• Determinar os casos base. Como mencionado anteriormente, eles são a versão mais pequena do problema maior. Já está ciente das soluções. Pense também nas consequências de não escrever uma base ou escolher a base incorrecta.

A compreensão dos sub-problemas e da sua natureza são essenciais em soluções recorrentes. Aqui estão alguns exemplos:

Programação dinâmica

Resolução de problemas através de múltiplos sub-problemas, mas os sub-problemas são dependentes.

Dividir e Conquistar

Usando outros elementos para além dos sub-problemas, onde existem sub-problemas independentes.

Onde é que as pessoas aplicam a Recurssão

• Algoritmos de aproximação relacionados com o desenho
• Algoritmos de classificação bem reconhecidos, tais como Merge Sort ou Quick Sort
• Resolução de problemas via retrocesso e busca exaustiva
• Resolução de problemas com a ajuda de programação dinâmica
• Usando uma abordagem de dividir e conquistar para resolver problemas
• Encontrar soluções para problemas gráficos
• À procura de respostas para os problemas das árvores
• Resolução de questões ligadas e de listagem de matrizes

Porque é que a Recurssão é Essencial

Eis algumas excelentes razões pelas quais a recorrência é benéfica para programadores e programadores:

1. As soluções recursivas são na sua maioria mais limpas em comparação com uma solução iterativa. Há casos em que se pode reduzir uma linha de 50 para5 a 10 linhas de recorrência.
2. Pensar recursivamente vem mais naturalmente em alguns casos. A recursividade é sem dúvida a forma mais simples e transparente de resolver problemas de estrutura de dados, por exemplo, árvores com estruturas recursivas simples.
3. Alguns problemas são bastante complicados, e em alguns casos, impossíveis de resolver através do uso da Iteração.
4. A recorrência é uma excelente opção, uma vez que divide os problemas em sub-problemas independentes e mais pequenos, tornando mais simples a sua paralelização.

Conceitos de Recurssão Vital que é preciso explorar

• Comparação de recorrência vs. iteração
• Diferentes tipos de recorrência e suas propriedades
• Utilização do método da árvore de recorrência para analisar a recorrência
• Utilização do Teorema do Mestre para analisar a recorrência
• Prós e contras da programação recursiva
• Compreender como converter conde iterativo em código recursivo e vice-versa

Porque é que a repetição ocorre com erros de transbordo de pilha?

Temos de ter uma compreensão abrangente de cada função para tirar partido da recursividade. Caso contrário, poderíamos ter toneladas de erros de depuração complicados. É claro que o tempo pode ser apertado por vezes, mas é melhor começar por escrever precisamente qual o papel de uma determinada função.

A recorrência será imensamente útil no mundo real e na programação do Top Coder. Ficaria surpreendido ao ver quantos programadores experientes consideram a recursividade ameaçadora. A sua prática irá ajudá-lo a pensar recursivamente e acabará por resolver problemas de programação complicados.