Algoritmos e Estruturas de Dados/Recursividade: diferenças entre revisões
| [edição não verificada] | [edição não verificada] |
Conteúdo apagado Conteúdo adicionado
m recat |
Sem resumo de edição |
||
Linha 1:
{{Navegação|[[Algoritmos e Estruturas de Dados|Índice]]|[[Algoritmos e Estruturas de Dados/Sintaxe|1.3 - Sintaxe]]|[[Algoritmos e Estruturas de Dados/Corretude|Corretude]]}}
'''Recursão''' é um método de programação no qual uma função pode chamar a si mesma. O termo é usado de maneira mais geral para descrever o processo de repetição de um objeto de um jeito similar ao que já fora mostrado. Muitos problemas em computação tem a propriedade de que cada instância sua contém uma instância menor do mesmo problema.
A chamada à função proveniente de um meio externo a ela é denominada ''chamada externa'' e cada uma das chamadas internas a si mesma é denominada ''chamada recursiva''.▼
Um método comum de simplificação é dividir o problema em subproblemas do mesmo tipo. Como técnica de programação, este método é conhecido como dividir e conquistar e é a chave para a construção de muitos algoritmos importantes, bem como uma parte fundamental da programação dinâmica.
A recursão na programação é bem exemplificada quando uma função é definida em termos de si mesma. Um exemplo da aplicação da recursão são os parsers (analisadores gramaticais) para linguagens de programação. Uma grande vantagem da recursão é que um conjunto infinito de sentenças possíveis, designs ou outros dados podem ser definidos, analisados ou produzidos por um programa de computador finito.
Relações de recorrência são equações que definem uma ou mais seqüências recursivamente. Alguns tipos específicos de relações de recorrência podem ser “resolvidos” para que se obtenha uma definição não-recursiva.
▲A chamada à função proveniente de um meio externo a ela é denominada ''chamada externa'' e cada uma das chamadas internas a si mesma é denominada ''chamada recursiva''.
Um exemplo clássico de recursão é a definição da função fatorial, dada aqui em pseudocódigo:
função fatorial(n)
{
se (n <= 1)
retorne 1;
senão
retorne n * fatorial(n-1);
}
A função chama a si mesma recursivamente em uma versão menor da entrada (n - 1) e multiplica o resultado da chamada por n, até que alcance o caso base, de modo análogo à definição matemática de fatorial.
Como pode-se notar pela primeira condição, todo processo recursivo necessita de uma '''condição de parada''' para evitar um ''loop'' infinito. Neste caso, quando a função fatorial atinge o valor menor ou igual a 1 ele passa a retornar o valor de volta para a função.
No entanto, a recursão não é sempre a melhor opção. Como pode-se ver na questão acima, um laço comum resolve o problema iterativamente. Desta forma, quando o problema é pequeno tente resolvê-lo diretamente e utilizar a recursão apenas quando o problema for grande, consumindo tempo demais em um laço.
==Resumo==
*Uma '''recursão''' em computação é uma função que chama a si mesma.
*Para evitar um ''loop'' infinito é necessário estabelecer uma condição de parada.
==Bibliografia==
*[[w:Recursividade|Recursividade na Wikipédia]]
*[http://www.ime.usp.br/~pf/algoritmos/aulas/recu.html Recursão e algoritmos recursivos-Paulo Feofiloff]
[[Categoria:Algoritmos e Estruturas de Dados|{{SUBPAGENAME}}]]
| |||