Recursividade em estrutura de dados

Recursividade em Estrutura de Dados

Em estrutura de dados, recursivo é a função que chama a si mesmo.
Uma função recursiva é definida em termos dela mesma.

A recursividade é uma estratégia que pode ser utilizada sempre que o cálculo de uma função para o valor n, pode ser descrita a partir do cálculo desta mesma função para o termo anterior (n-1).
Definição: dentro do corpo de uma função, chamar novamente a própria função:

•recursão direta: a função A chama a própria função A
•recursão indireta: a função A chama uma função B que, por sua vez, chama A.
Existem vantagens e desvantagens na utilização de recursividade em programação. Algumas das vantagens do uso de recursão são:
•A clareza na interpretação do código
• Simplicidade e elegância na implementação.
Algumas das desvantagens são:
• Dificuldade para encontrar erros.
• Podem ser ineficientes.
A principal preocupação na implementação de algoritmos recursivos é a questão de eficiência tanto de espaço quanto de tempo.

Espaço :A chamada de uma função requer espaço para os parâmetros, variáveis locais e endereço de retorno. No caso de chamadas recursivas, todas estas informações são armazenadas em uma pilha e depois retiradas. Desta forma, a quantidade de informação armazenada pode ser proporcional ao número de chamadas.
Tempo: Todas as operações envolvidas na recursividade contribuem para um gasto maior de tempo, pois alocar e liberar memória, copiar informações, etc. envolvem tempo computacional.

Outro ponto importante de algoritmos recursivos é o critério de parada. Se os critérios de parada da recursividade não estiverem bem definidos, pode ocorrer uma infinidade de chamadas preenchendo toda a memória disponível.

Referencia:
DECOM –