ALG2-04

Prévia do material em texto

ricardo.marcacini@ufms.br
Prof. Ricardo M. Marcacini
Curso:
Algoritmos e Programação IIAlgoritmos e Programação II
Sistemas de Informação
2º Semestre / 2013
http://www.marcacini.com.br/ufms/
Aula 4
 Algoritmos Recursivos
 Aplicação: Fractais
 Exemplos de Algoritmos Recursivos
 Complexidade de Algoritmos Recursivos
 Comparação: Iterativo VS Recursivo
ALG2-04 2
Recursividade
 Um programa recursivo é um programa que 
chama a si mesmo
 Dentro do corpo de uma função (ou procedimento), 
chamar novamente a própria função (ou procedimento)
ALG2-04 3
Recursividade
 Um programa recursivo é um programa que 
chama a si mesmo
 Dentro do corpo de uma função (ou procedimento), 
chamar novamente a própria função (ou procedimento)
 Um programa recursivo “mal formulado” 
realiza um loop infinito
ALG2-04 4
Recursividade
 Um programa recursivo é um programa que 
chama a si mesmo
 Dentro do corpo de uma função (ou procedimento), 
chamar novamente a própria função (ou procedimento)
 Um programa recursivo “mal formulado” 
realiza um loop infinito
 Necessário uma condição de parada
 A condição de parada depende do problema
ALG2-04 5
Recursividade
 O que acontece com os parâmetros e 
variáveis locais durante a recursão?
 Cada chamada da função tem seu próprio “escopo”
 Variáveis locais
 Parâmetros
ALG2-04 6
Recursividade
 Como funciona a execução de algoritmos 
recursivos?
ALG2-04 7
Recursividade
 Como funciona a execução de algoritmos 
recursivos?
 Cada chamada da função é tratada como um 
programa independente
 Quando uma função filha é chamada, a função pai é 
“congelada” e espera a execução
 Quando a função filha termina, a execução volta 
para a função pai
 Processo chamado de “Pilha de Execução”
ALG2-04 8
Algoritmos Recursivos
 Vamos estudar em aula alguns exemplos 
implementados usando recursão
 Fatorial
 Somar elementos de um vetor
 Série de Fibonacci
 Divisão Recursiva
 Busca Sequencial Recursiva
ALG2-04 9
Fatorial (recursivo)
 Entrada:
 Inteiro n
 Saída:
 Inteiro n! = n*(n-1)*(n-2)*(n-2)* … * 1
DUZAIR
Typewritten text
3
ALG2-04 10
Fatorial (recursivo)
 Entrada:
 Inteiro n
 Saída:
 Inteiro n! = n*(n-1)*(n-2)*(n-2)* … * 1
Função int fatorial_recursivo(int n){
se(n <= 0) retornar 1;
senão retornar n * fatorial_recursivo(n-1);
}
DUZAIR
Typewritten text
3
ALG2-04 11
Soma recursiva de elementos do vetor
 Entrada:
 Inteiro n (tamanho do vetor)
 Vetor de inteiros v
 Saída:
 Inteiro (soma)
ALG2-04 12
Soma recursiva de elementos do vetor
 Entrada:
 Inteiro n (tamanho do vetor)
 Vetor de inteiros v
 Saída:
 Inteiro (soma)
Função int soma_recursiva(int n, int v[]){
se(n < 0) retornar 0;
senão
 retornar v[n-1] + soma_recursiva(n-1,v);
}
DUZAIR
Typewritten text
=
ALG2-04 13
Série de Fibonacci
ALG2-04 14
Série de Fibonacci
 Função naturalmente recursiva...
ALG2-04 15
Série de Fibonacci
 Função naturalmente recursiva...
Função int fib(int n){
se(n < 2) retornar n;
senão retornar fib(n-1)+fib(n-2);
}
ALG2-04 16
Divisão Recursiva
 Implementar e estudar o seguinte 
programa:
ALG2-04 17
Busca Sequencial Recursiva
 Entrada:
 Número inteiro n≥0 (tamanho do vetor)
 Vetor v[0..n−1] com n números inteiros
 Um inteiro x (que desejamos buscar)
 Saída
 k no intervalo [0, n-1] tal que v[k] = x
 Obs: Se tal k não existe, devolve -1
ALG2-04 18
Busca Sequencial Recursiva
ALG2-04 19
Complexidade de Algoritmos Recursivos
 Necessário verificar complexidade de 
espaço (memória)
 Pilha de execução
 Número de chamadas recursivas
 Exemplo: Fatorial
ALG2-04 20
Complexidade de Algoritmos Recursivos
 Necessário verificar complexidade de 
espaço (memória)
 Pilha de execução
 Número de chamadas recursivas
 Exemplo: Fatorial
 Versão recursiva
 Tempo: O(n) Espaço: O(n)
 Versão iterativa
 Tempo: O(n) Espaço: O(1)
ALG2-04 21
Complexidade de Algoritmos Recursivos
 Equação de recorrência T(n) é utilizada 
para ajudar na análise da complexidade
 Qual a equação de recorrência que descreve a 
complexidade da função fatorial?
ALG2-04 22
Complexidade de Algoritmos Recursivos
 Equação de recorrência T(n) é utilizada 
para ajudar na análise da complexidade
 Qual a equação de recorrência que descreve a 
complexidade da função fatorial?
T(n) = 1 + T(n-1)
T(1) = 1
T(n) = 1 + T(n-1)
T(n-1) = 1 + T(n-2)
T(n-2) = 1 + T(n-3)
...
T(2) = 1 + T(1) 
ALG2-04 23
Quando usar recursão?
 Paradigma: dividir para conquistar
 Duas chamadas recursivas
 Cada uma resolve metade do problema
 Solução eficiente na prática
 Em muitas situações, recursividade é 
ineficiente
 Compare as versões iterativas e
recursivas do Fibonacci!
ALG2-04 24
Bibliografia
ZIVIANI, N. Projeto de algoritmos com implementações em 
Java e C++. 1. ed. São Paulo: Thomson Learning, 2006.
Projeto de Algoritmos – Cap.2 Paradigmas de Projeto de Algoritmos – Seção 2.2.2
	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