2014820_103435_alex-ed1-semana4-1-recursividade

Prévia do material em texto

Estrutura de Estrutura de 
Dados IDados IDados IDados I
Prof. Alex Salgado
Curso: Sistemas de Informação
8/20/2014 1
AgendaAgenda
• Introdução a recursividade
• Algoritmos de ordernação
• Algoritmos de pesquisa
• Introdução complexidade de algoritmos
2
RecursividadeRecursividade
• As funções podem ser chamadas 
recursivamente, isto é, dentro do 
corpo de uma função podemos 
chamar novamente a própria 
função. 
• Diversas implementações ficam 
muito mais fáceis usando muito mais fáceis usando 
recursividade. Por outro lado, 
implementações não recursivas 
tendem a ser mais eficientes.
3
RecursividadeRecursividade
• Para cada chamada de uma 
função, recursiva ou não, os 
parâmetros e as variáveis locais 
são empilhados na pilha de 
execução. 
• Assim, mesmo quando uma 
função é chamada função é chamada 
recursivamente, cria-se um 
ambiente local para cada 
chamada. As variáveis locais de 
chamadas recursivas são 
independentes entre si, como se 
estivéssemos chamando funções 
diferentes
4
RecursividadeRecursividade
• Função Sigma
• Calcula a soma nos 
inteiros de 0 até um 
número n
• Ex.: sigma = n+(n-1) + (n-2) 
+ (n-3+...+0
8/20/2014Footer Text 5
• Se n = 5
• Sigma = 5 + 4 + 3 + 2 +1+0
• Sigma = 15
RecursividadeRecursividade
0, Se m <= 0 
(m + sigma ( m – 1), se m>0
sigma {
8/20/2014Footer Text 6
11--ExercícioExercício
1 - Como ficaria a função fatorial fat(n), implementada de 
forma recursiva ?
• Lembrando que:
fat(n) = n * (n-1) * (n-2) * (n-3) * ... * 1
7
11--Exercício Exercício -- respostaresposta
8
22--ExercícioExercício
2 – Sabendo que a sequencia de Fibonacci é uma sequência de 
números inteiros, começando normalmente por 1, na qual, cada termo 
subsequente (número de Fibonacci) corresponde a soma dos dois 
anteriores, na forma:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, …
2.1- Crie uma função recursiva int 
9
2.1- Crie uma função recursiva int 
fibo(int n) que retorne o número de 
Fibonacci do termo n.
2.2- Crie um programa para 
imprimir a sequencia de Fibonnaci 
até o termo n (entrada por teclado).
Algoritmos de buscaAlgoritmos de busca
• Imagine que há 7 portas com números por trás 
delas e pretende-se encontrar o número 50. Se 
você não sabe nada sobre os números, você só 
tem de abrir as portas, uma de cada vez até 
encontrar 50 ou até que todas as portas estejam 
abertas. 
8/20/2014Footer Text 10
Algoritmos de buscaAlgoritmos de busca
50
• Isto significa que seria necessário sete passos, ou mais 
em geral, n passos, onde n é o número de portas. 
Podemos chamar isso de um algoritmo linear.
8/20/2014Footer Text 11
Algoritmos de buscaAlgoritmos de busca
• Como pode a nossa abordagem mudar, se 
sabemos que os números são ordenados? 
• Podemos dividir continuamente o problema pela 
metade! Primeiro, abra a porta do meio. Vamos 
dizer que seja 16. dizer que seja 16. 
8/20/2014Footer Text 12
Algoritmos de buscaAlgoritmos de busca
16 502 4 10 23 33
• Então sabemos que 50 devem estar nas portas para 
a direita do meio, para que possamos jogar fora a 
esquerda. Em seguida, olhar para a porta do meio 
na metade direita e assim por diante até que nós 
encontramos 50! Este algoritmo tem tempo de 
execução logarítmica, a linha verde no gráfico 
abaixo:
8/20/2014 13
Algoritmos de buscaAlgoritmos de busca
8/20/2014Footer Text 14
Introdução a Complexidade Introdução a Complexidade 
de algoritmosde algoritmos
8/20/2014 15
Introdução a Complexidade de algoritmosIntrodução a Complexidade de algoritmos
8/20/2014 16
Introdução a Complexidade de algoritmosIntrodução a Complexidade de algoritmos
8/20/2014 17
Introdução a Complexidade de algoritmosIntrodução a Complexidade de algoritmos
Análise assintótica
8/20/2014 18
Introdução a Complexidade de algoritmosIntrodução a Complexidade de algoritmos
Notação O (ou Big Oh)
8/20/2014 19
Introdução a Complexidade de algoritmosIntrodução a Complexidade de algoritmos
8/20/2014 20