Recursividade
577 palavras
3 páginas
Estrutura de Dados 2Recursividade
2011
1 / 32
O que é recursividade?
É a propriedade de algo ser definido em termos de si mesmo.
Exemplo
Árvore Binária (string de bits)
2011
0.
1, seguido de dois strings de bits.
2 / 32
Ao Infinito e Além
A recursividade permite
2011
a definição de “um conjuto infinito de objetos por meio de uma formulação finita”. (Wirth) escrever programas que realiza infinitas computações com um número finito de instruções.
3 / 32
Recursividade em Programas
Um algoritmo é recursivo quando ele
“chama” a si mesmo.
Exemplo
int xyz (int n)
{
if (n == 0) return 0; return n + xyz (n-1);
}
O que o programa faz?
A recursividade pode ser direta ou indireta.
2011
4 / 32
Recursividade: como é possível?
Por meio de uma pilha.
int mdc (int m, int n)
{
if (n == 0) return m; return mdc (n, m % n);
}
2011
5 / 32
Recursividade: como é possível? int mdc (int m, int n)
{
if (n == 0) return m; return mdc (n, m % n);
}
2011
6 / 32
Recursividade: como é possível? int mdc (int m, int n)
{
if (n == 0) return m; return mdc (n, m % n);
}
2011
7 / 32
Recursividade: como é possível? int mdc (int m, int n)
{
if (n == 0) return m; return mdc (n, m % n);
}
2011
8 / 32
Recursividade: como é possível? int mdc (int m, int n)
{
if (n == 0) return m; return mdc (n, m % n);
}
2011
9 / 32
Recursividade: como é possível? int mdc (int m, int n)
{
if (n == 0) return m; return mdc (n, m % n);
}
2011
10 / 32
Por que usar recursividade em programas?
Compaticidade
Código com menos instruções.
2011
Menos variáveis.
Controle implícito.
Elegância.
Contudo, recursividade demanda cuidados. 11 / 32
Cuidados com a
Recursividade (1)
Existência da condição de parada.
Deve haver um caso base a partir do