Esta página foi escrita para os alunos do BCC e não pretende ser uma fonte de consulta para leitores de fora, apesar de que várias informações podem ser úteis a terceiros.
Se você olhar em qualquer bom dicionário, verá alguma coisa como "recursão é o ato de recorrer". Mas recorrer é uma palavra de vários significados...
Se você
buscar recursion no Google [ver imagem], ele vai sugerir que você busque recursion.
Alguns glossários
definem recursão como: veja recursão. Por fim, existe aquele "dito popular": para entender o que é recursão,
você primeiro precisa entender o que é recursão
.
Para quem deseja aprender, no entanto, a definição de recursão no MathWorld é bem formal e completa:
um processo recursivo é aquele em que objetos são definidos em termos de outros objetos do mesmo tipo. Usando alguma forma de relação de recorrência, toda a classe de objetos pode ser definida a partir de alguns valores iniciais e de um pequeno número de regras.
Embora boa, uma definição como a do MathWorld tende a ser classificada como difícil e, em geral, não ajuda os alunos na hora de usar recursão. Dessa forma, eu prefiro dizer que recursão é a definição, descrição ou implementação que faz uso de si mesma, num caso mais simples (esta definição é minha mesmo).
Pode-se dizer que o tal "ato de recorrer" está no fato da definição, descrição ou implementação recorrer a si própria para formalizar alguma coisa. A recursão é uma ótima ferramenta nas mãos de um programador. As pessoas usam intuitivamente recursão, e por isto é geralmente mais fácil resolver um grande problema usando recursão do que usando iteração.
A recursão também está intimamente ligada à indução matemática e a matemática é a fonte de todo o formalismo necessário em computação. A recursão também ligada à recorrência. Costuma-se dizer que uma definição é recorrente, um certo algoritmo é recursivo e um raciocínio é indutivo (uma demonstração usa indução).
Em todos os casos, estamos enfatizado lados da mesma moeda. Recursão e indução matemática já foram definidos e usados em disciplinas anteriores.
A recursão é tratada como qualquer outra chamada de sub-rotina. Isso envolve guardar o estado atual do processamento de maneira que ele possa continuar de onde parou, quando a sub-rotina estiver terminada. Guardar o estado de um processamento consome tempo e memória, por isso a recursão é usualmente tida como menos eficiente que a iteração.
As informações usadas para continuar o processamento depois de encerrada a chamada recursiva (ou pelo menos parte delas) ficam numa região de memória denominada pilha de execução. Este espaço de memória é estatico e de tamanho determinado em tempo de compilação. Se for reservada uma área grande para um programa, deverá haver um desperdício de memória. Se for reservada uma área pequena, pode ser que não haja espaço suficiente para executar um número suficientemente grande de recursões para resolver um problema. Nessa situação, acontece o chamado estouro de pilha (stack overflow), conhecido de qualquer programador.
Para proporcionar uma alternativa a estes "problemas" da recursão, as linguagens em que não existe iteração costumam exigir uso de compiladores ou interpretadores que reconheçem e tratam corretamente a recursão de cauda.
A recursão de cauda é um tipo especial de recursão, no qual não existe processamento a ser feito depois de encerrada a chamada recursiva. Sendo assim, não é necessário guardar o estado do processamento no momento da chamada recursiva. Um compilador ou interpretador pode (se for construído assim) detectar a ocorrência de recursão de cauda e gerar código em que a chamada recursiva é implementada como um mero desvio do fluxo de instruções.
Desta forma é possível executar código recursivo de forma tão eficiente quanto é possível executar código iterativo. Cabe ao programador encontrar uma forma de descrever a solução de seu problema através de recursão de cauda. Por outro lado, usar recursão de cauda geralmente envolve trabalhar num nível mais baixo de abstração o que prejudica a legibilidade e a manutenção do código.
Esta página é mantida por Bruno Schneider
