Recursividade

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.

Um exemplo clássico de recursão é a definição do cálculo do fatorial de um número, dada aqui no algoritmo a seguir:

1:  ALGORITMO: Fatorial(n)   
2:  ENTRADA: inteiro n  
3:  SAÍDA: fatorial de n  
4:  REQUISITOS: n >= 0  
5:  SE n <= 1  
6:    RETORNE 1  
7:  SENÃO  
8:    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.