PROGRAMAÇÃO
ESTRUTURADA II
Profª. Noeli
Ciência da Computação
1
RECURSIVIDADE
CIÊNCIA DA COMPUTAÇÃO
FUNÇÕES RECURSIVAS
• Funções recursivas são caracterizadas
por possuírem “auto-chamadas”.
•Estas “auto-chamadas” geram uma
seqüência de execuções da função
recursivamente até que a função pare de
efetuar a “auto-chamada”.
CIÊNCIA DA COMPUTAÇÃO
FUNÇÕES RECURSIVAS
Em toda a função recursiva, existem os
componentes:
• Um passo básico (ou mais) cujo o
resultado é imediatamente conhecido;
• Um passo recursivo (ou mais) em
que se tenta resolver um subproblema do problema inicial.
CIÊNCIA DA COMPUTAÇÃO
FUNÇÕES RECURSIVAS
•Geralmente possui expressão
condicional;
•Sua execução consiste em ir resolvendo
sub-problemas mais simples, até se
atingir o mais simples de todos
(resultado conhecido de imediato)
CIÊNCIA DA COMPUTAÇÃO
RECURSIVIDADE
Estudo de Caso:
FATORIAL
CIÊNCIA DA COMPUTAÇÃO
FATORIAL NÃO RECURSIVO
int fat(int n)
{
int i, f = 1;
for(i= n; i >= 1; i--)
{
f = f * i;
}
return f;
}
CIÊNCIA DA COMPUTAÇÃO
FATORIAL RECURSIVO
int fat(int n)
{
if (n <= 1)
Condição de Parada
return 1;
else
Chamada
return n * fat(n -1);
Recursiva
}
CIÊNCIA DA COMPUTAÇÃO
VANTAGEM
• Os algoritmos recursivos
normalmente são mais compactos,
mais legíveis e mais fáceis de serem
compreendidos.
• Algoritmos para resolver problemas
de natureza recursiva são fáceis de
serem implementados em linguagens
de programação de alto nível.
CIÊNCIA DA COMPUTAÇÃO
DESVANTAGEM
• Por usarem intensivamente a pilha de
execução, o que requer alocações e
desalocações de memória, os algoritmos
recursivos tendem a ser mais lentos que os
equivalentes iterativos, mas, em muitos casos,
pode valer a pena sacrificar a eficiência em
benefício da clareza.
• Algoritmos recursivos são mais difíceis de
serem depurados durante a fase de
desenvolvimento.
CIÊNCIA DA COMPUTAÇÃO
EXERCÍCIOS
• Lista de Exercícios na sala Virtual.
•
CIÊNCIA DA COMPUTAÇÃO