Recursividade slide

Prévia do material em texto

Algoritmos Recursivos
Annabell D.R. Tamariz
Informações da matéria
Algoritmos Recursivos
Conceito de Recursividade
Características
Exercícios
Aplicações
Exercícios em Sala de
aula
Próxima Aula....
4.1
Capítulo 4
Algoritmos Recursivos
Recursividade
Aulas de Estrutura de Dados I
Annabell D.R. Tamariz
LCMAT-CCI
www.lcmat.uenf.br/professores/annabell
Universidade Estadual do Norte Fluminense - UENF
Algoritmos Recursivos
Annabell D.R. Tamariz
Informações da matéria
Algoritmos Recursivos
Conceito de Recursividade
Características
Exercícios
Aplicações
Exercícios em Sala de
aula
Próxima Aula....
4.2
Ementa
• Abstração de Dados.
• Alocação Estática e Dinâmica.
• Listas lineares.
• Pilhas e Filas:
• Algoritmos Recursivos.
• Conceito de Recursividade.
• Características.
• Exercícios.
• Aplicações
• Matrizes esparsas. Listas Generalizadas.
• Algoritmos de classificação e busca.
Algoritmos Recursivos
Annabell D.R. Tamariz
Informações da matéria
Algoritmos Recursivos
Conceito de Recursividade
Características
Exercícios
Aplicações
Exercícios em Sala de
aula
Próxima Aula....
4.3
Conteúdo Programático
1 Algoritmos Recursivos
Conceito de Recursividade
Características
Exercícios
Aplicações
2 Exercícios em Sala de aula
3 Próxima Aula....
Algoritmos Recursivos
Annabell D.R. Tamariz
Informações da matéria
Algoritmos Recursivos
Conceito de Recursividade
Características
Exercícios
Aplicações
Exercícios em Sala de
aula
Próxima Aula....
4.4
Introdução
Recursividade
• Vamos entender por algoritmo recursivo, aquele
algoritmo que para resolver um problema divide-o em
subproblemas mais simples, cujas soluções requerem a
aplicação dele mesmo.
• A linguagem C permite que um programador escreva
funções que chamem a si mesmas. Tais rotinas são
denominada recursivas.
• Processo de resolução(de uma equação, de um
problema) mediante uma seqüencia finita de operações
em que o objeto de cada uma é o resultado da que a
precede
Algoritmos Recursivos
Annabell D.R. Tamariz
Informações da matéria
Algoritmos Recursivos
Conceito de Recursividade
Características
Exercícios
Aplicações
Exercícios em Sala de
aula
Próxima Aula....
4.5
Introdução
Recursividade
• Em termos de programação, uma rotina é recursiva
quando ela chama a si mesma, seja de forma direta ou
indireta.
• Podemos expressar uma rotina recursiva como uma
composição formada por um conjunto de comandos C e
uma chamada à rotina R:
• R = [C, R] Recursão direta
Algoritmos Recursivos
Annabell D.R. Tamariz
Informações da matéria
Algoritmos Recursivos
Conceito de Recursividade
Características
Exercícios
Aplicações
Exercícios em Sala de
aula
Próxima Aula....
4.6
Introdução
Recursividade
• Entretanto, pode-se ter também uma forma indireta de
recursão, na qual as rotinas são conectadas através de
uma cadeia de chamadas sucessivas que acaba
retornando à primeira que foi chamada:
R1 = [C1, R2]
R2 = [C2, R3]
R3 = [C3, R4]
.......
Rn = [Cn, R1]
Algoritmos Recursivos
Annabell D.R. Tamariz
Informações da matéria
Algoritmos Recursivos
Conceito de Recursividade
Características
Exercícios
Aplicações
Exercícios em Sala de
aula
Próxima Aula....
4.7
Recursividade
Algoritmos Recursivos
Annabell D.R. Tamariz
Informações da matéria
Algoritmos Recursivos
Conceito de Recursividade
Características
Exercícios
Aplicações
Exercícios em Sala de
aula
Próxima Aula....
4.8
Introdução
O que é um problema recursivo?
• Alguma coisa é recursiva quando é definida em termos
dela própria.
• Exemplo da aritmética que dá a definição dos números
naturais:
• primeiro natural é o zero.
• sucessor de um número natural é um número natural.
Algoritmos Recursivos
Annabell D.R. Tamariz
Informações da matéria
Algoritmos Recursivos
Conceito de Recursividade
Características
Exercícios
Aplicações
Exercícios em Sala de
aula
Próxima Aula....
4.9
Recursividade - Exemplo
Tarefa: subir as escadas
1 Se se atingiu o cimo das escadas, a tarefa subir as
escadas está, obviamente terminada;
2 Caso contrário, se o cimo não tiver sido atingido:
1 Avançar um degrau, na direção do cimo das escadas e
2 Retomar a tarefa subir as escadas.
3 Notar que ao retomar a tarefa, a dimensão do problema
diminuiu, pois já se avanço mais um degrau.
Algoritmos Recursivos
Annabell D.R. Tamariz
Informações da matéria
Algoritmos Recursivos
Conceito de Recursividade
Características
Exercícios
Aplicações
Exercícios em Sala de
aula
Próxima Aula....
4.10
Recursividade - Exemplo
Algoritmo Iterativo
1 Tarefa subir escadas:
• Enquanto não atingir o topo
• Subir um degrau
Exercício
Seguindo a idéia de subir as escadas, como ficaria uma
função em C para somar os números menores do que 10?
(Fazer em forma recursiva e iterativa)
Algoritmos Recursivos
Annabell D.R. Tamariz
Informações da matéria
Algoritmos Recursivos
Conceito de Recursividade
Características
Exercícios
Aplicações
Exercícios em Sala de
aula
Próxima Aula....
4.11
Recursividade
Algoritmo Iterativo/Recursivo
#include<stdio.h>
int iterativa(int i){
int total=0;
while i<10 {
total += i;
i++ }
return total; }
int recursiva(int i){
if i<10
return i+recursiva(i+1);
return 0;}
Algoritmos Recursivos
Annabell D.R. Tamariz
Informações da matéria
Algoritmos Recursivos
Conceito de Recursividade
Características
Exercícios
Aplicações
Exercícios em Sala de
aula
Próxima Aula....
4.12
Recursividade
Algoritmo Iterativo/Recursivo
int main() {
printf(" $nIterativa :%i $nRecursiva: %i",iterativa(0),recursiva(0));
getchar();
return 0;}
Algoritmos Recursivos
Annabell D.R. Tamariz
Informações da matéria
Algoritmos Recursivos
Conceito de Recursividade
Características
Exercícios
Aplicações
Exercícios em Sala de
aula
Próxima Aula....
4.13
Recursividade
Características
• Toda vez que uma função é iniciada recursivamente, um
novo conjunto de variáveis locais e de parâmetros é
alocado, e somente esse novo conjunto pode ser
referenciado dentro dessa chamada.
• Quando ocorre um retorno de uma função recursiva
para um ponto numa chamada anterior, a alocação mais
recente dessas variáveis é liberada, e a cópia anterior é
reativada.
Algoritmos Recursivos
Annabell D.R. Tamariz
Informações da matéria
Algoritmos Recursivos
Conceito de Recursividade
Características
Exercícios
Aplicações
Exercícios em Sala de
aula
Próxima Aula....
4.14
Recursividade
Condições da Recursividade
• Todo algoritmo deve ser executado em tempo finito, isto
é, deve terminar após ter executado uma quantidade
finita de passos.
• Para garantir que uma chamada recursiva não criará um
looping que será executado infinitamente, é necessário
que ela esteja condicionada a uma expressão lógica (T)
que, em algum instante, tornar-se-á falsa e permitirá
que a recursão termine.
Algoritmos Recursivos
Annabell D.R. Tamariz
Informações da matéria
Algoritmos Recursivos
Conceito de Recursividade
Características
Exercícios
Aplicações
Exercícios em Sala de
aula
Próxima Aula....
4.15
Recursividade
Definição
• Na prática, ao definir uma rotina recursiva, dividimos o
problema da seguinte maneira:
• Solução trivial : dada por definição; isto é, não necessita
da recursão para ser obtida.
• Solução geral : parte do problema que em essência é
igual ao problema original, sendo, porém menor. A
solução, neste caso, pode ser obtida por uma chamada
recursiva R(x-1).
Algoritmos Recursivos
Annabell D.R. Tamariz
Informações da matéria
Algoritmos Recursivos
Conceito de Recursividade
Características
Exercícios
Aplicações
Exercícios em Sala de
aula
Próxima Aula....
4.16
Recursividade - Exemplo
Fatorial de um número natural
1 Solução trivial : 0! = 1 (dada por definição);
2 Solução geral : n! = n * (n-1)! (requer reaplicação da
rotina para (n-1)!)
3 Considerando f(n) = n, então n=0 implica numa
condição de parada do mecanismo recursivo, garantindo
o término do algoritmo que calcula o fatorial.
Algoritmos Recursivos
Annabell D.R. Tamariz
Informações da matériaAlgoritmos Recursivos
Conceito de Recursividade
Características
Exercícios
Aplicações
Exercícios em Sala de
aula
Próxima Aula....
4.17
Recursividade
O algoritmo recursivo para computar n! Pode ser
diretamente traduzido numa função em C.
Algoritmo Recursivo do Factorial
#include<stdio.h>
int fatorial(n) {
if (n==0)
return 1;
return n*fatorial(n-1);}
int main(){
printf("%i",fatorial(4));
getchar();}
Algoritmos Recursivos
Annabell D.R. Tamariz
Informações da matéria
Algoritmos Recursivos
Conceito de Recursividade
Características
Exercícios
Aplicações
Exercícios em Sala de
aula
Próxima Aula....
4.18
Recursividade
Algoritmos Recursivos
Annabell D.R. Tamariz
Informações da matéria
Algoritmos Recursivos
Conceito de Recursividade
Características
Exercícios
Aplicações
Exercícios em Sala de
aula
Próxima Aula....
4.19
Recursividade
Algoritmos Recursivos
Annabell D.R. Tamariz
Informações da matéria
Algoritmos Recursivos
Conceito de Recursividade
Características
Exercícios
Aplicações
Exercícios em Sala de
aula
Próxima Aula....
4.20
Exercícios no Computador
Vide arquivo "Recursividade.pdf"
Algoritmos Recursivos
Annabell D.R. Tamariz
Informações da matéria
Algoritmos Recursivos
Conceito de Recursividade
Características
Exercícios
Aplicações
Exercícios em Sala de
aula
Próxima Aula....
4.21
Aplicações
Quando aplicar recursão?
• Está pergunta é bastante difícil de responder, pois
teríamos que comparar as possíveis soluções: recursiva
e iterativa!!!.
• Enquanto alguns problemas têm solução imediata com
o uso da recursão, outros ao praticamente impossíveis
de se resolver de forma recursiva.
• É preciso analisar o problema e verificar se realmente
vale a pena tentar encontrar uma solução recursiva.
Algoritmos Recursivos
Annabell D.R. Tamariz
Informações da matéria
Algoritmos Recursivos
Conceito de Recursividade
Características
Exercícios
Aplicações
Exercícios em Sala de
aula
Próxima Aula....
4.22
Aplicações
Pilhas e rotinas recursivas
• O controle de chamadas e retornos de rotinas é feito
através de uma pilha criada e mantida,
automaticamente, pelo sistema (como visto na definição
de pilhas).
• Na verdade quando uma rotina é evocada, não apenas
o endereço de retorno é empilhado, mas todas as suas
variáveis locais são também recriadas na pilha.
• Para compreender a relação existente entre recursão e
o uso de pilhas, vamos definir uma rotina recursiva para
imprimir em ordem decrescente uma lista que foi
ordenada de forma crescente.
Algoritmos Recursivos
Annabell D.R. Tamariz
Informações da matéria
Algoritmos Recursivos
Conceito de Recursividade
Características
Exercícios
Aplicações
Exercícios em Sala de
aula
Próxima Aula....
4.23
Recursividade
Algoritmos Recursivos
Annabell D.R. Tamariz
Informações da matéria
Algoritmos Recursivos
Conceito de Recursividade
Características
Exercícios
Aplicações
Exercícios em Sala de
aula
Próxima Aula....
4.24
Aplicações
Pilhas e rotinas recursivas
• Perceba que, para imprimir de forma decrescente uma
lista ordenada, basta imprimir em ordem decrescente
todos os seus elementos, exceto o primeiro deles; que
será impresso logo em seguida.
• Cada vez que uma chamada recursiva à função Show()
é executada, uma nova versão da varíavel L é criada
para armazenar o valor e Lˆ.prox.
• Assim, a chamada recursiva faz com que sejam
guardados na pilha os endereços de todos os nodos da
lista, até que não haja mais nodos (lista vazia).
• Neste momento, as chamadas recursivas começam a
retornar o controle para a instrução writeln(...), que vai
imprimindo os elementos da lista, um a um, em ordem
inversa.
Algoritmos Recursivos
Annabell D.R. Tamariz
Informações da matéria
Algoritmos Recursivos
Conceito de Recursividade
Características
Exercícios
Aplicações
Exercícios em Sala de
aula
Próxima Aula....
4.25
Aplicações
Pilhas e rotinas recursivas
• É fácil perceber que a recursão na rotina Show() tem
como único objetivo simular uma pilha, onde os
endereços dos nodos devem aguardar até que os
elementos possam ser impressos.
• Agora vamos obter o mesmo efeito da rotina Show(),
usando uma pilha no lugar da recursão
• Qualquer tipo de recursão pode ser eliminado se
utilizarmos no seu lugar comandos de repetição e,
eventualmente, pilhas.
Algoritmos Recursivos
Annabell D.R. Tamariz
Informações da matéria
Algoritmos Recursivos
Conceito de Recursividade
Características
Exercícios
Aplicações
Exercícios em Sala de
aula
Próxima Aula....
4.26
Aplicações
Algoritmos Recursivos
Annabell D.R. Tamariz
Informações da matéria
Algoritmos Recursivos
Conceito de Recursividade
Características
Exercícios
Aplicações
Exercícios em Sala de
aula
Próxima Aula....
4.27
Aplicações
Exemplo da Pilha
Vamos mostrar o que acontece com a chamada fatorial de 4:
Algoritmos Recursivos
Annabell D.R. Tamariz
Informações da matéria
Algoritmos Recursivos
Conceito de Recursividade
Características
Exercícios
Aplicações
Exercícios em Sala de
aula
Próxima Aula....
4.28
Aplicações
Conclusões
• Normalmente, as rotinas assim modificadas serão mais
rápidas que suas correspondentes em versão recursiva.
• Entretanto, se o uso de muitos comandos de repetição e
várias pilhas for necessário para realizar a conversão da
versão recursiva para a iterativa, talvez seja melhor
permanecer com a rotina recursiva.
• Um algoritmo claro, simples e conciso vale mais que
qualquer algoritmo envenenado que rode um pouquinho
mais rápido.
Algoritmos Recursivos
Annabell D.R. Tamariz
Informações da matéria
Algoritmos Recursivos
Conceito de Recursividade
Características
Exercícios
Aplicações
Exercícios em Sala de
aula
Próxima Aula....
4.29
Exercícios em Sala
1 Implementar em C um algoritmo para preencher
recursivamente um vetor de inteiros de 10 posições com
o valor 1
2 Implementar em C um algoritmo para imprimir
recursivamente o vetor de inteiros de 10 posições
Algoritmos Recursivos
Annabell D.R. Tamariz
Informações da matéria
Algoritmos Recursivos
Conceito de Recursividade
Características
Exercícios
Aplicações
Exercícios em Sala de
aula
Próxima Aula....
4.30
Exercícios em Sala
Solução
#include<stdio.h>
intvetor[10 ;]
void preencheVetor(int indice) {
if(indice<10) {
vetor[indice ++ =1;]
preencheVetor(indice);
}
}
void imprimeVetor(int indice) {
If (indice<10) {
printf("%i ",vetor[indice++ );]
imprimeVetor(indice);
}
}
Algoritmos Recursivos
Annabell D.R. Tamariz
Informações da matéria
Algoritmos Recursivos
Conceito de Recursividade
Características
Exercícios
Aplicações
Exercícios em Sala de
aula
Próxima Aula....
4.31
Exercícios em Sala
Solução - Continuação
int main() {
preencheVetor(0);
imprimeVetor(0);
getchar();
return 0; }
Algoritmos Recursivos
Annabell D.R. Tamariz
Informações da matéria
Algoritmos Recursivos
Conceito de Recursividade
Características
Exercícios
Aplicações
Exercícios em Sala de
aula
Próxima Aula....
4.32
Próxima aula ...
1 Listas Generalizadas.
2 Matrizes Esparsas.
	Informações da matéria
	Algoritmos Recursivos
	Conceito de Recursividade
	Características
	Exercícios
	Aplicações
	Exercícios em Sala de aula
	Próxima Aula....