Estrutura de dados II
Carlos Oberdan Rolim
Ciência da Computação
Sistemas de Informação
Recursividade
Conceito de Recursividade
• Um programa recursivo é um programa que chama
a si mesmo, direta ou indiretamente
• Conceito poderoso
– Define conjuntos infinitos com comandos finitos
• Vantagens
– Redução do tamanho do código fonte
– Permite descrever algoritmos de forma mais clara e concisa
• Desvantagens
– Redução do desempenho de execução devido ao tempo para
gerenciamento de chamadas
– Dificuldades na depuração de programas recursivos,
especialmente se a recursão for muito profunda
Implementação da Recursividade
• Usa-se uma pilha para armazenar os dados
usados em cada chamada de um procedimento /
função que não terminou
• Todos os dados não globais são armazenados na
pilha, informando o resultado corrente
• Quando uma ativação anterior prossegue, os
dados da pilha são recuperados
Exemplo – Função Fatorial
• Definição de uma Função Fatorial
a) Não Recursiva:
– N! = 1, para N=0;
– N! = 1 x 2 x 3 x ... x N, para N>=1;
b) Recursiva:
– N! = 1, para N=0;
– N! = N x (N – 1), para N>=1;
Fatorial de N – Definição Iterativa
Se n = 0
Então Fat(n) = 1
Se n > 0
Então Fat(n) = 1 x 2 x 3 x …N
int fat(int fatorial){
int i;
int resposta = 1;
if (fatorial == 0)
resposta = 1;
else if (fatorial > 0)
for(i=1;i <= fatorial; i++)
resposta = resposta * i;
return resposta;
}
Fatorial de N – Definição Recursiva
Se n = 0
Então Fat(n) = 1
Se n > 0
Então Fat(n) = n x Fat(n – 1)
Fatorial de N – Definição Recursiva
Ex: 4!
4! = 4 x 3! = 24
3! = 3 x 2! =
6
2! = 2 x 1! =
2
1! = 1 x 0! =
1
0! = 1
int fat_recursivo(int fatorial){
int i;
int resposta = 1;
if (fatorial == 0)
resposta = 1;
else if (fatorial > 0)
for(i=1;i <= fatorial; i++)
resposta = fatorial *
fat_recursivo(fatorial-1);
return resposta;
}
Sequência de Fibonacci – Definição
Iterativa
0 1 1 2 3 5 8 13 …
Simulação:
Anterior = 0
Anterior = 1
Anterior = 1
Anterior = 2
Anterior = 3
….
atual = 1
atual = 1
atual = 2
atual = 3
atual = 5
seguinte = 1
seguinte = 2
seguinte = 3
seguinte = 5
seguinte = 8
int fib(int fibonacci){
int i;
int anterior, atual, seguinte;
if (fibonacci == 1)
return 0;
else if (fibonacci == 2)
return 1;
else {
anterior = 0;
atual = 1;
for(i=3;i <= fibonacci; i++) {
seguinte = atual + anterior;
anterior = atual;
atual = seguinte;
}
return atual;
}
}
Sequência de Fibonacci – Definição
Recursiva
fib(1) = 0
fib(2) = 1
fib(3) = fib(2) + fib(1)
fib(4) = fib(3) + fib(2)
Fib(n) = fib(n-1) + fib(n - 2)
Sequência de Fibonacci – Definição
Recursiva
fib(5)
3
fib(4) 2
Fib(2)
fib(3) 1
+
fib(3) 1
+
fib(1)
0
1
Fib(2)
1
+
fib(1)
0
+
fib(2)
1
int fib_recursivo(int fibonacci){
int i;
int anterior, atual, seguinte;
if (fibonacci == 1)
return 0;
else if (fibonacci == 2)
return 1;
else return fib_recursivo(fibonacci - 1) +
fib_recursivo(fibonacci - 2);
}
MDC(a,b): Iterativo
int mdc(int a, int b){
int resto;
while (b != 0) {
resto = (a % b);
a = b;
b = resto;
}
return a;
}
MDC(a,b): Recursivo
int mdc_recursivo(int a, int b){
if (b == 0)
return a;
else return mdc_recursivo(b, a % b);
}
Potência: Definição Recursiva
4 = 23 * 2 = 16
2
3 = 22 * 2 = 8
2
2 = 21 * 2 = 4
2
1 = 20 * 2 = 2
2
0=1
2
Potência: Definição Recursiva
int pot_recursivo(int a, int b){
if (b == 0)
return 1;
else return (pot_recursivo(a, b-1) * a);
}
Torres de Hannoi
O objetivo deste jogo é mover todas as peças da coluna
esquerda para a coluna da direita
Você só pode mover uma haste de cada vez
As peças devem ser empilhadas obedecendo o tamanho das
mesmas, ficando as menores sobre as maiores.
Torres de Hannoi em Java
Dicas
• Não se aprende recursividade sem praticar
• Para montar um algoritmo recursivo
– Defina pelo menos um caso básico (condição de
terminação);
– Quebre o problema em problemas menores,
definindo o(s) caso(s) com recursão(ões)
– Fazer o teste de finitude, isto é, certificar-se de
que as sucessivas chamadas recursivas levam
obrigatoriamente, e numa quantidade finita de
vezes, ao(s) caso(s) básico(s)
Finalizando
• Recursividade é um tópico fundamental
• Algoritmos recursivos aparecem bastante na
prática
• Dividir e conquistar é uma técnica naturalmente
recursiva para solução de problemas
• Mais recursividade no nosso futuro, principalmente
na implementação de árvores...