Aula02-Recursividade

Prévia do material em texto

Algoritmos Recursivos
Antonio Felicio Netto
4º Semestre Ciência da Computação
Recursão
• Recursão é o processo pelo qual uma função chama a si 
mesma, repetidamente, um numero finito de vezes ;
• A recursividade é um dos elementos da programação que 
pode causar um certo impacto inicialmente ;
• Porém, se bem utilizado, torna os programas mais simples 
e elegantes;
Conceito de Recursividade
• Classificamos um programa como recursivo quando ele 
possui rotinas que chamam 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;
• É definido um ponto de parada para função que permite o 
seu retorno; 
• 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;
Implementação de Fatorial 
Recursivo X Não Recursivo
public int FatorialNaoRecursivo (int n)
{
int resultado = 1;
for (int i = 1; i<= n ; i++){
resultado = resultado *i;
}
return resultado;
}
Implementação não Recursiva
public int FatorialRecursivo (int n)
{
if (n == 0){
return 1;
}
else{
return n*FatorialRecursivo(n-1);
}
}
Implementação Recursiva
Resultado da Implementação
Fatorial := 3 * (Fatorial(2))
Fatorial := 4 * (Fatorial(3)) 
Fatorial := 2 * (Fatorial(1))
Fatorial := 1 * (Fatorial(0))
Fatorial := 1
1 Fatorial = 1
1 Fatorial = 2
2 Fatorial = 6
6 Fatorial = 24
1º Chamada
2º Chamada
5º Chamada
3º Chamada
4º Chamada
Problema com terminação de 
Procedimentos Recursivos
• Procedimentos recursivos introduzem a possibilidade de 
iterações que podem não terminar: existe a necessidade de 
considerar o problema de terminação.
• É fundamental que a chamada recursiva a um procedimento P 
esteja sujeita a uma condição A, a qual se torna satisfeita em 
algum momento da computação.
– Ex.: Se não existisse a condição n=0, quando o 
procedimento terminaria?
• Condição de terminação
– Permite que o procedimento deixe de ser executado
– O procedimento deve ter pelo menos um caso básico para 
cada caso recursivo, o que significa a finalização do 
procedimento
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...
Exercícios
1) Elabore um algoritmo que de forma recursiva realize o cálculo 
da progressão aritmética (PA) de um número informado pelo 
usuário;
2) Elabore um algoritmo que de forma recursiva realize a 
potenciação de um número X por um outro número Y;
Referências
• Thales Castelo Branco de Castro – Unifacs 
http://www.nuperc.unifacs.br/Members/thales.
castro/arquivos/aulas/Recursividade.ppt
• Carlos Alberto Teixeira Batista – FACAPE 
www.facape.br/carlos/ed/12_Recursividade.ppt
• David Menotti - DECOM