aula-recursao

Prévia do material em texto

CEFET-MG – Engenharia de Computação
Recursão e 
Análise de Complexidade de 
Algoritmos Recursivos
Algoritmos e Estruturas de Dados I
2015/1
 
Sumário
 Conceito matemático de recursão
 Conceito computacional de recursão
 Vantagens e desvantagens da recursão
 Aplicações da recursão
 Análise de complexidade de algoritmos recursivos
 Resolução de relações de recorrência
 
Recursão
Um objeto recursivo 
é descrito 
em termos de si mesmo
 
Objetos recursivos
 
Conceito matemático de recursão
 Uma função recursiva é uma função parcialmente definida em 
termos de si mesma
Função fatorial Série de Fibonacci: 0,1,1,2,3,5,8,13,21,
34,55,89,144,233,377,610,987,1597, ...
Soma dos primeiros números naturais
O próprio elemento 
definido aparece na 
definição...
 
Conceito matemático de recursão
Função fatorial
Série de Fibonacci
Soma dos primeiros números naturais
Condição de 
terminação
parte fundamental 
da definição
 
Conceito computacional de recursão
 Um procedimento recursivo é aquele que chama a si mesmo 
direta ou indiretamente
int abc() {
 ......
 ......
 abc ();
 ......
}
int abc() {
 ......
 ......
 xyz ();
 ......
}
int xyz() {
 ......
 ......
 abc ();
 ......
}
Recursão direta
Recursão indireta
 
Conceito computacional de recursão
 Recursão indireta
 
 Função fatorial recursiva – recursão direta
/* entrada:  inteiro n não negativo
   resultado: retorna o fatorial de n 
*/
long fatorial(int n) {
   if ((n == 0) || (n == 1))   // condição de terminação
      return 1;
   else                        // caso recursivo
      return (n * fatorial(n ­ 1));
}
 
 Função fatorial recursiva – execução
/* 
entrada:  inteiro n não negativo
resultado: retorna o fatorial de n 
*/
long fatorial(int n) {
   if ((n == 0) || (n == 1))  
      return 1;
   else                        
      return (n * fatorial(n ­ 1));
}
Exemplo: fatorial de 5
5! = 5 * 4!
 4! = 4 * 3!
 3! = 3 * 2!
 2! = 2 *1!
 1! = 1
 
Função fatorial recursiva – execução
 Chamadas de função e uso da memória
temp= 5*4!
fat(5)
temp= 5*4!
fat(5)
temp= 4*3!
fat(4)
temp= 5*4!
fat(5)
temp= 4*3!
fat(4)
temp= 3*2!
fat(3)
temp= 4*3!
fat(4)
temp= 5*4!
fat(5)
temp= 3*2!
fat(3)
temp= 2*1!
fat(2)
Uso de 
memória
e
chamadas 
de 
função
Tempo de execução
temp= 4*3!
fat(4)
temp= 5*4!
fat(5)
temp= 3*2!
fat(3)
temp= 2*1!
fat(2)
retorna 1
fat(1)
Cada chamada de função é denominada ATIVAÇÃO da função
 
Conceito computacional de recursão
 Um procedimento recursivo é aquele que chama a si mesmo 
direta ou indiretamente - ou, de forma equivalente:
 Uma função é recursiva se uma nova ativação pode começar 
antes que uma ativação anterior da mesma função tenha 
terminado
 
Ativação de função e pilha de memória
 Toda vez que uma função é ativada:
 ela é carregada na memória e espaço é reservado para variáveis locais, 
parâmetros da função, variáveis temporárias criadas automaticamente 
pelo sistema para armazenar cálculos intermediários, endereço de 
retorno (quem chamou?)
 o estado corrente da computação deve ser armazenado para permitir a 
volta da chamada recursiva: prosseguimento da execução do programa
 requer uma chamada de sistema (sistema operacional)
=> maior tempo de execução
 No caso da função recursiva:
 Para cada chamada, um novo espaço é alocado na memória!
 pilha de recursão: cada ativação é empilhada na memória
 O custo das chamadas é elevado: custo da recursão
 tempo de execução e espaço em memória
 
Condição de parada ou terminação
 Deve ser cuidadosamente explicitada para evitar 
infinitas chamadas recursivas 
 na prática: o programa finalizaria por falta de memória
 Análise do número de chamadas recursivas
 Profundidade da recursão: número máximo de 
chamadas de função empilhadas durante a execução 
da função
 Exemplo: fatorial (n): n chamadas da função empilhadas temp= 4*3!
fat(4)
temp= 5*4!
fat(5)
temp= 3*2!
fat(3)
temp= 2*1!
fat(2)
retorna 1
fat(1)
 
Série de Fibonacci: versão iterativa
unsigned long fib (int n) {
 unsigned long atual, menos1=1, menos2=0;
 if (n <=1) return n;
 else 
 for (int i=2; i <= n; i++) {
 atual = menos1 + menos2;
 menos2 = menos1; 
 menos1 = atual;
 } 
 return atual;
}
Série de Fibonacci: 
0,1,1,2,3,5,8,13, 21,34,55,89,144 ...
 
Série de Fibonacci: versão recursiva
unsigned long fibrec(int n) {
 if (n <= 1)
 return n;
 else 
 return fibrec(n-1) + fibrec(n-2);
}
Árvore de recursão
Observem a 
repetição de 
cálculos de 
termos
 
Fibonacci recursivo:
número de chamadas e profundidade da recursão
0, 1, 1, 2, 3, 5
chamada # 1 
chamada # 2 
chamada # 3 
chamada # 4 
chamada # 5 
chamada # 6 
chamada # 7 
chamada # 8 
chamada # 9 
chamada # 10 
chamada # 11 
chamada # 12 
chamada # 13 
chamada # 14 
chamada # 15 
O valor final e' 5
 
Série de Fibonacci: número de somas
termo valor #somas #somas rec 
 0 0 = 0 0 0
 1 1 = 1 0 0
 2 1 = 1 1 1
 3 2 = 2 2 2
 4 3 = 3 3 4
 5 5 = 5 4 7
 6 8 = 8 5 12
 7 13 = 13 6 20
 8 21 = 21 7 33
 9 34 = 34 8 54
10 55 = 55 9 88
11 89 = 89 10 143
12 144 = 144 11 232
13 233 = 233 12 376
14 377 = 377 13 609
15 610 = 610 14 986
16 987 = 987 15 1596
17 1597 = 1597 16 2583
18 2584 = 2584 17 4180
19 4181 = 4181 18 6764
20 6765 = 6765 19 10945
...
37 24157817 = 24157817 36 39088168
38 39088169 = 39088169 37 63245985
39 63245986 = 63245986 38 102334154
40 102334155 = 102334155 39 165580140
Número de somas 
executadas nas 
versões recursiva e 
não recursiva da 
função
 
Vantagens e desvantagens da recursão
Vantagens
 técnica de programação versátil e 
poderosa
 permite definir um conjunto infinito 
de objetos com um comando finito
 ajuda a descrever estruturas de 
dados eficientes e elegantes
 pode oferecer uma maneira 
elegante e concisa para expressar 
uma solução recursiva para um 
problema
 a versão recursiva de um 
programa pode ser muito mais 
simples do que a versão não 
recursiva
Desvantagens
 custo: chamadas de função 
são demoradas
 se a recursão for eliminada o 
programa pode executar mais 
rápido
 custo: gasto adicional de 
memória
 o programa pode terminar por 
falta de memória
 condição de terminação pode 
ser causa de erros
 um algoritmo recursivo pode 
ser terrivelmente ineficiente
 
 Aplicação da recursão
 aplicação: para problemas e/ou estruturas de dados de natureza 
recursiva, que não tenham implementação simples não recursiva
 nunca deve ser usada no lugar de um laço simples
 ajuda a descrever algoritmos e estruturas de dados de natureza 
recursiva, de maneira eficiente e elegante
 ex: árvores – estruturasde dados e algoritmos
 muitos algoritmos interessantes são expressos de forma bastante 
simples usando a recursão
 ex: quicksort
 
Implementação da recursão
 Para evitar laços infinitos
 definir bem as condições de finalização da recursão
 Problema da terminação: como garantir a finalização da recursão
 definir uma condição de terminação
 em geral, um procedimento recursivo P recebe um parâmetro n e é 
chamado recursivamente para P(m) onde m < n 
 deve-se garantir que a condição de terminação será alcançada
 Estimar o número de chamadas recursivas
 o número de vezes que a função recursiva será chamada deve ser um número 
pequeno e conhecido
 
Conclusão: prefira iteração sempre que possível
long fatorial(int n) {
   int k;
   long resultado = 1;
   for (k = 2; k <= n; k++)
      resultado = resultado * k;
   return resultado;
}
As funções fatorial e Fibonacci 
NUNCA devem ser 
implementadas de maneira 
recursiva
As implementações recursivas de fatorial e Fibonacci são usadas somente para fins didáticos
Quando não usar a recursão
 quando um laço pode 
substitui-la perfeitamente
 exemplos: função fatorial e 
função de Fibonacci
 atenção para recursão de 
cabeça e cauda
 a chamada recursiva vem 
no início ou no fim do 
código: pode ser facilmente 
transformada em laço
 
Análise de complexidade de algoritmos recursivos
 O tempo de execução de um algoritmo recursivo pode ser expresso 
por uma relação de recorrência
 Uma relação de recorrência é uma equação ou inequação que 
descreve uma função em termos de seus valores sobre entradas 
menores
 Uma relação de recorrência é composta por duas partes
 caso base
 expressa a condição de terminação da definição recursiva
 é o resultado da relação para valores pequenos de n, quando nenhuma 
chamada recursiva é feita
 caso indutivo
 parte em que os termos da sequência são definidos em função dos termos 
menores
 expressa as chamadas recursivas da função
 
Expressando o custo em relações de recorrência
 O tempo de execução de um algoritmo recursivo é usualmente 
denominado T(n)
 Exemplo: para a função fatorial
 seja T(n) o número de multiplicações executado pela função 
fatorial recursiva
 o custo da execução é expresso pela relação de recorrência
 
 
Mais exemplos de relações de recorrência
 
Analisando algoritmos recursivos
 Etapas da análise de complexidade de algoritmos recursivos
1) defina T(n) como a função de complexidade de tempo do algoritmo, para 
uma entrada de tamanho n
2) analise o algoritmo e encontre o custo para o caso base
3) analise o algoritmo e encontre o custo para a parte recursiva
4) apresente a relação de recorrência
5) resolva a relação de recorrência
 A solução de uma relação de recorrência é uma fórmula fechada
 para qualquer valor de n, o custo pode ser calculado com um número fixo 
de operações elementares
 há várias técnicas para resolver relações de recorrência
 ex: método da iteração: expandir T(n) até identificar um padrão
 
Exemplo de solução 1
Somar os 
termos lado 
a lado
Fórmula fechada
 
Exemplo de solução 2
 
Exemplo de solução 3
 
Exemplo de solução 4
 
Recursão em jogos
Jogo das Torres de Hanói
 
Sites sobre recursão: divirta-se
Veja algoritmos animados 
de recursão e páginas 
sobre recursão na Web 
e no Youtube
Recursion
Animated recursion
Animation of recursion
Recursive functions
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32