estudante

matéria

ESTRUTURAS DE DADOS I
Celso Roberto Maroso

Estruturas de Dados I
RECURSIVIDADE
• As funções podem ser chamadas recursivamente, isto é, dentro do corpo de uma função podemos chamar novamente a própria função.
• Se uma função A chama a própria função A, dizemos que ocorre uma recursão direta.
• Se uma função A chama uma função B que, por sua vez, chama A, temos uma recursão indireta.

Estruturas de Dados I
RECURSIVIDADE
• Diversas implementações ficam muito mais fáceis usando recursividade. • Por outro lado, implementações não recursivas tendem a ser mais eficientes.

Estruturas de Dados I
RECURSIVIDADE
• Para cada chamada de uma função, recursiva ou não, os parâmetros e as variáveis locais são empilhados na pilha de execução.
• Assim, mesmo quando uma função é chamada recursivamente, cria-se um ambiente local para cada chamada. • As variáveis locais de chamadas recursivas são independentes entre si, como se estivéssemos chamando funções diferentes.

Estruturas de Dados I
RECURSIVIDADE

Estruturas de Dados I
RECURSIVIDADE
• As implementações recursivas devem ser pensadas considerando-se a definição recursiva do problema que desejamos resolver.
• Por exemplo, o valor do fatorial de um número pode ser definido de forma recursiva:

Estruturas de Dados I
RECURSIVIDADE
• Considerando a definição acima, é simples pensar na implementação recursiva de uma função que calcula e retorna o fatorial de um número n qualquer.
/* Função recursiva para calculo do fatorial */ int fat (int n)
{
if (n==0) return 1; else return n*fat(n-1);
}

Estruturas de Dados I
RECURSIVIDADE
• Enquanto n for maior que 0, a função fat chama a si mesma, decrementando o valor de n em uma unidade a cada chamada • n=0 é critério de parada para esta chamada recursiva

Estruturas de Dados I
RECURSIVIDADE
Recursividade X Iteração
• Quando se aborda recursividade algumas duvidas surgem, como: – Porque não usar