A recursão pode ser vista por muitos como um bicho de sete cabeça, porem muitas vezes a recursividade pode ser a melhor maneira de resolver um determinado problema, também pode ser a forma mais legível e simples do que a forma interativa.
Na programação a recursividade é um método que invoca a si próprio, ou seja uma função que se invoca recursivamente. De forma geral o problema é dividido em outros problemas menores até não existir mas nenhum problema para ser resolvido, para isso o compilador precisa armazenar as instruções, ponteiros e endereçamento na memoria Stack para cada chamada de método recursivo. Enquanto a recursividade ocorre a instrução atual, (antes da chamada recursiva), é congelada para dar vez ao próximo método recursivo, isso continua ocorrendo até que o próximo método recursivo termine.
Funcionamento
Conforme uma pilha, cada método fica aguardando o próximo terminar. O estado atual de cada método recursivo é guardado na memoria conforme a imagem a seguir.
Enquanto a chamada recursiva continua a memoria é consumida ate sua exaustão, quando isso ocorre um erro de StackOverflow é lançado. Por este motivo a recursão tradicional é menos eficiente que a iteração.
É possível aumentar a memoria alocada para as chamadas recursivas, no Java basta adicionar na vm o parametro -Xss256m, mas o problema continuará porem será postergado.
O estado do processamento dos métodos anteriores ficam na memoria até o fim de cada método recursivo.
Existe uma técnica chamada de Tail Recursion para evitar o consumo excessivo da memória Stack, que apresentarei no próximo post.
Felipe Priuli 