Buscar

02.Recursividade

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 48 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 48 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 48 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

Aula 02
Algoritmos e Recursividade
Rodolfo Carneiro Cavalcante
Universidade Federal de Alagoas – UFAL
Campus Arapiraca
2 de Abril de 2015
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 1 / 47
Suma´rio
1 Introduc¸a˜o
2 Medida de Tempo de Execuc¸a˜o de um Algoritmo
3 Recursividade
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 2 / 47
Introduc¸a˜o
Suma´rio
1 Introduc¸a˜o
2 Medida de Tempo de Execuc¸a˜o de um Algoritmo
3 Recursividade
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 3 / 47
Introduc¸a˜o
Algoritmos
Algoritmos fazem parte do dia-a-dia das pessoas
instruc¸o˜es para o uso de medicamentos
indicac¸o˜es de como montar um aparelho
uma receita de culina´ria
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 4 / 47
Introduc¸a˜o
Algoritmos
Sequeˆncia de ac¸o˜es executa´veis para a obtenc¸a˜o de uma soluc¸a˜o para
determinado tipo de problema
Descric¸a˜o de um padra˜o de comportamento, expresso em termos de
um conjunto finito de ac¸o˜es (Dijkstra)
Conjunto finito de instruc¸o˜es precisas para executar uma computac¸a˜o
Ferramenta para resolver um problema computacional bem
especificado
Pode receber como entrada um conjunto de valores e pode produzir
como sa´ıda um outro conjunto de valores
Descreve uma sequeˆncia de passos computacionais que transforma a
entrada numa sa´ıda – uma relac¸a˜o entrada/sa´ıda
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 5 / 47
Introduc¸a˜o
Estruturas de Dados
Algoritmos e estruturas de dados esta˜o intimamente ligados
Na˜o se pode estudar estruturas de dados sem considerar os algoritmos
associados a elas
A escolha de um algoritmo em geral depende da estrutura de dados a
ser utilizada
Para resolver um problema e´ necessa´rio escolher uma abstrac¸a˜o da
realidade – definic¸a˜o de um conjunto de dados que representa a
situac¸a˜o real
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 6 / 47
Introduc¸a˜o
Programas
Programar e´ basicamente estruturar dados e construir algoritmos
Programas – formulac¸o˜es concretas de algoritmos abstratos, baseados
em representac¸o˜es e estruturas espec´ıficas de dados
Programas – classe especial de algoritmos capazes de serem seguidos
por computadores
Um computador so´ e´ capaz de seguir programas em linguagem de
ma´quina (sequeˆncia de instruc¸o˜es obscuras e desconforta´veis)
E´ necessa´rio construir linguagens mais adequadas, que facilitem a
tarefa de programar um computador
Linguagem de programac¸a˜o – te´cnica de notac¸a˜o para programar
Servir de ve´ıculo tanto para a expressa˜o do racioc´ınio algor´ıtmico
quanto para a execuc¸a˜o automa´tica de um algoritmo por um
computador
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 7 / 47
Introduc¸a˜o
Tipos de Dados
Em linguagens de programac¸a˜o e´ importante classificar constantes,
varia´veis, expresso˜es e func¸o˜es de acordo com certas caracter´ısticas,
que indicam o seu tipo de dados
Tipo de dado – conjunto de valores a que uma constante pertence,
que podem ser assumidos por uma varia´vel ou expressa˜o, que podem
ser gerados por uma func¸a˜o
Tipos simples de dados – grupos de valores indivis´ıveis (int, bool,
char, float)
Exemplo: uma varia´vel do tipo boolean pode assumir o valor
verdadeiro ou o valor falso, e nenhum outro valor
Os tipos estruturados – colec¸a˜o de valores simples, ou um agregado
de valores de tipos diferentes
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 8 / 47
Introduc¸a˜o
Tipos Abstratos de Dados (TAD)
Modelo matema´tico, acompanhado das operac¸o˜es definidas sobre o
modelo
Exemplo: o conjunto dos inteiros acompanhado das operac¸o˜es de
adic¸a˜o, subtrac¸a˜o e multiplicac¸a˜o
TADs sa˜o generalizac¸o˜es de tipos primitivos e procedimentos sa˜o
generalizac¸o˜es de operac¸o˜es primitivas
TADs podem ser usados para encapsular tipos de dados
A definic¸a˜o do tipo e todas as operac¸o˜es ficam localizadas numa
sec¸a˜o do programa
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 9 / 47
Introduc¸a˜o
Implementac¸a˜o de TADs
Exemplo: aplicac¸a˜o que utilize uma lista de nu´meros inteiros – TAD lista
Operac¸o˜es do TAD:
1 fac¸a a lista vazia;
2 obtenha o primeiro elemento da lista; se a lista estiver vazia, enta˜o
retorne nulo;
3 Insira um elemento na lista
Cada operac¸a˜o do TAD e´ implementada por um procedimento
Qualquer alterac¸a˜o na implementac¸a˜o do TAD fica restrita a` parte
encapsulada, sem causar impactos em outras partes do co´digo
Cada operac¸a˜o do TAD e´ implementada por um procedimento
Qualquer alterac¸a˜o na implementac¸a˜o do TAD fica restrita a` parte
encapsulada, sem causar impactos em outras partes do co´digo
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 10 / 47
Medida de Tempo de Execuc¸a˜o de um Algoritmo
Suma´rio
1 Introduc¸a˜o
2 Medida de Tempo de Execuc¸a˜o de um Algoritmo
3 Recursividade
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 11 / 47
Medida de Tempo de Execuc¸a˜o de um Algoritmo
Medida de Tempo de Execuc¸a˜o
Algoritmos sa˜o utilizados para resolver problemas de forma
automa´tica
Um mesmo problema pode ser resolvido por diversos algoritmos
diferentes
Bom programador – capaz de decidir quando utilizar um ou outro
algoritmo
A pergunta que surge:
qual o custo de usar um determinado algoritmo para resolver o
problema?
complexidade de algoritmos – teoria da computac¸a˜o!
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 12 / 47
Medida de Tempo de Execuc¸a˜o de um Algoritmo
Medida de Tempo de Execuc¸a˜o
Caracter´ısticas que devem ser investigadas:
Ana´lise do nu´mero de vezes que determinada parte do algoritmo e´
executada
Quantidade de memo´ria necessa´ria
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 13 / 47
Medida de Tempo de Execuc¸a˜o de um Algoritmo
Medida de Tempo de Execuc¸a˜o
Ana´lise do nu´mero de vezes que uma parte do algoritmo e´ executada:
Algoritmo 1: Loop simples
for(int i = 0; i<n; i++){
cout<<i<<endl;
}
Esse lac¸o acima executara´ n vezes.
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 14 / 47
Medida de Tempo de Execuc¸a˜o de um Algoritmo
Medida de Tempo de Execuc¸a˜o
O pro´ximo loop executara´ n × n = n2 vezes:
Algoritmo 2: Loop aninhado
for(int i = 0; i<n; i++){
for(int j = 0; j<n; j++){
cout<<i*j<<endl;
}
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 15 / 47
Medida de Tempo de Execuc¸a˜o de um Algoritmo
Medida de Tempo de Execuc¸a˜o
O projeto de algoritmos e´ fortemente influenciado pelo estudo de seus
comportamentos
Resoluc¸a˜o de um problema – escolha dos algoritmos a serem utilizados
Considerando os aspectos de tempo de execuc¸a˜o e espac¸o ocupado
Qual e´ o algoritmo de menor custo poss´ıvel para resolver um
problema particular?
Toda uma fam´ılia de algoritmos e´ investigada.
Procura-se identificar um que seja o melhor poss´ıvel.
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 16 / 47
Medida de Tempo de Execuc¸a˜o de um Algoritmo
Medida de Tempo de Execuc¸a˜o
Pensem em um algoritmo para obter o ma´ximo de um conjunto
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 17 / 47
Medida de Tempo de Execuc¸a˜o de um Algoritmo
Medida de Tempo de Execuc¸a˜o
Algoritmo3: Algoritmo para obter o ma´ximo de um conjunto
int maxElemento(int elementos[], int n){
int max = elementos[0];
for(int i = 1; i< n;i++){
if(max<elementos[i])
max = elementos[i];
}
return max;
}
Qual o custo computacional desse algoritmo?
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 18 / 47
Medida de Tempo de Execuc¸a˜o de um Algoritmo
Medida de Tempo de Execuc¸a˜o
Qual o custo computacional desse algoritmo?
Resposta: n − 1, pois e´ o nu´mero de comparac¸o˜es necessa´rias
Existe um algoritmo melhor para resolver esse problema?
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 19 / 47
Medida de Tempo de Execuc¸a˜o de um Algoritmo
Medida de Tempo de Execuc¸a˜o
Existe um algoritmo melhor para resolver esse problema?
na˜o, esse algoritmo e´ o´timo
para este problema, e´ preciso fazer no m´ınimo n − 1 comparac¸o˜es para
saber quem e´ o maior elemento
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 20 / 47
Medida de Tempo de Execuc¸a˜o de um Algoritmo
Medida de Tempo de Execuc¸a˜o
Algoritmo 4: Algoritmo para obter o ma´ximo e o m´ınimo de um conjunto
int* maxMinElemento(int elementos[], int n){
int max = elementos[0];
int min = elementos[0];
for(int i = 1; i<n;i++){
if(max<elementos[i])
max = elementos[i];
if(min>elementos[i])
min = elementos[i];
}
int * maxMin = new int[2];
maxMin[0] = max;
maxMin[1] = min;
return maxMin;
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 21 / 47
Medida de Tempo de Execuc¸a˜o de um Algoritmo
Medida de Tempo de Execuc¸a˜o
Quantas comparac¸o˜es sa˜o feitas nesse algoritmo?
Esse algoritmo e´ similar ao anterior, pore´m faz uma comparac¸a˜o para o
ma´ximo e outra para o m´ınimo
Resposta: 2 ∗ (n − 1)
Esse algoritmo e´ o´timo?
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 22 / 47
Medida de Tempo de Execuc¸a˜o de um Algoritmo
Medida de Tempo de Execuc¸a˜o
Esse algoritmo e´ o´timo?
Na˜o. Se o valor comparado e´ maior, enta˜o na˜o precisa comparar se o
mesmo valor e´ o menor
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 23 / 47
Medida de Tempo de Execuc¸a˜o de um Algoritmo
Medida de Tempo de Execuc¸a˜o
Melhoramento
Algoritmo 5: Algoritmo para obter o ma´ximo e o m´ınimo de um conjunto
int* maxMinElemento(int elementos[], int n){
int max = elementos[0];
int min = elementos[0];
for(int i = 1; i<n;i++){
if(max<elementos[i])
max = elementos[i];
else if(min>elementos[i])
min = elementos[i];
}
int * maxMin = new int[2];
maxMin[0] = max;
maxMin[1] = min;
return maxMin;
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 24 / 47
Medida de Tempo de Execuc¸a˜o de um Algoritmo
Medida de Tempo de Execuc¸a˜o
O que melhorou:
No melhor caso, onde os elementos esta˜o em ordem crescente: n − 1
comparac¸o˜es
No pior caso, onde os elementos esta˜o em ordem decrescente: 2(n − 1)
comparac¸o˜es
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 25 / 47
Medida de Tempo de Execuc¸a˜o de um Algoritmo
Medida de Tempo de Execuc¸a˜o
Como analisar o tempo de execuc¸a˜o de algoritmos
Podemos abstrair essa ana´lise da seguinte forma:
comandos de atribuic¸a˜o, leitura ou escrita tem custo 1
comandos de decisa˜o tem custo 1
lac¸os: custo da execuc¸a˜o do corpo do lac¸o multiplicado pelo nu´mero de
iterac¸o˜es do lac¸o
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 26 / 47
Medida de Tempo de Execuc¸a˜o de um Algoritmo
Medida de Tempo de Execuc¸a˜o
Como analisar o tempo de execuc¸a˜o de algoritmos
Podemos abstrair essa ana´lise da seguinte forma:
comandos de atribuic¸a˜o, leitura ou escrita tem custo 1
comandos de decisa˜o tem custo 1
lac¸os: custo da execuc¸a˜o do corpo do lac¸o multiplicado pelo nu´mero de
iterac¸o˜es do lac¸o
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 27 / 47
Medida de Tempo de Execuc¸a˜o de um Algoritmo
Medida de Tempo de Execuc¸a˜o
Moral da histo´ria:
Voceˆs tera˜o uma disciplina inteiramente dedicada a ana´lise de
algoritmos (6o per´ıodo), onde se estuda o comportamento e o custo de
va´rios algoritmos
Mostrei essa diferenc¸a porque e´ importante durante o aprendizado de
algoritmos e estruturas de dados, ja´ pensar em construir algoritmos
mais eficientes
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 28 / 47
Recursividade
Suma´rio
1 Introduc¸a˜o
2 Medida de Tempo de Execuc¸a˜o de um Algoritmo
3 Recursividade
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 29 / 47
Recursividade
Recursividade
Um me´todo ou procedimento que chama a si mesmo, direta ou
indiretamente, e´ dito ser recursivo.
Resoluc¸a˜o de problemas utilizada para gerar soluc¸o˜es simples a certos
tipos de problemas que seriam dif´ıceis de resolver de outra forma
Problema original dividido em um ou mais verso˜es simples de si
mesmo
O problema original que envolve n itens e´ divido em um problema
com n − 1 itens e outro envolvendo um u´nico item
O problema com n − 1 e´ dividido novamente ate´ encontrar uma
soluc¸a˜o trivial
A partir da´ı constro´i-se a soluc¸a˜o original a partir das soluc¸o˜es mais
simples
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 30 / 47
Recursividade
Recursividade
Ex: Sequeˆncia de Fibonacci
uma sequeˆncia de nu´meros inteiros, na qual, cada termo subsequente
(numero de Fibonacci) corresponde a soma dos dois anteriores
0 1 1 2 3 5 8 13 21 34...
Fn = Fn−1 + F n − 2
F0 = 0
F1 = 1
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 31 / 47
Recursividade
Quando na˜o Usar Recursividade
Algoritmo 6: Algoritmo de Fibonacci recursivo
int fib(int n){
if(n == 0||n == 1)
return n;
else
return fib(n-1) + fib(n-2);
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 32 / 47
Recursividade
Implementando recursividade
SO implementa um me´todo recursivo por meio de uma pilha,
armazenar dados usados em cada chamada de um procedimento que
ainda na˜o terminou
Dados na˜o globais va˜o para a pilha, registrando o estado corrente da
computac¸a˜o
Quando uma ativac¸a˜o anterior prossegue, os dados da pilha sa˜o
recuperados
No caso do caminhamento central:
Para cada chamada recursiva, o valor de p e o enderec¸o de retorno da
chamada recursiva sa˜o armazenados na pilha.
Quando p == NULL, o procedimento retorna para quem chamou
utilizando o enderec¸o de retorno que esta´ no topo da pilha
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 33 / 47
Recursividade
Problema da terminac¸a˜o
Possibilidade de iterac¸o˜es que podem na˜o terminar
Necessidade de considerar o problema de terminac¸a˜o
Chamada recursiva a um procedimento P sujeita a uma condic¸a˜o B, a
qual se torna na˜o-satisfeita em algum momento da computac¸a˜o
Caso base – valor pequeno que pode ser resolvido diretamente
O n´ıvel mais profundo de recursa˜o deve ser finito e pequeno
Pois cada ativac¸a˜o recursiva usa uma parcela de memo´ria para
acomodar as varia´veis.
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 34 / 47
Recursividade
Problema da terminac¸a˜o
Algoritmo 7: Algoritmo Fatorial
int fat(int n){
if(n == 1)
return n;
else
return n*fat(n-1);
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 35 / 47
Recursividade
Corretudede uma Recursa˜o
Caracter´ısticas de soluc¸a˜o recursiva:
1 Existeˆncia de pelo menos um caso – valor pequeno de n – resolvido
diretamente (caso base)
2 Um problema de tamanho n pode ser dividido em uma ou mais
verso˜es menores do problema. (caso recursivo)
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 36 / 47
Recursividade
Corretude de uma Recursa˜o
Etapas do projeto de uma soluc¸a˜o recursiva
1 Reconhecer o caso base e formular soluc¸a˜o
2 Criar estrate´gia de divisa˜o do problema ıtem Combinar as soluc¸o˜es
dos problemas menores para formar a soluc¸a˜o do problema maior de
forma correta
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 37 / 47
Recursividade
Corretude de uma Recursa˜o
E´ preciso provar que o algoritmo recursivo esta´ correto
Verificar a corretude das etapas do projeto
Prova por induc¸a˜o – prova matema´tica da corretude de teoremas:
1 prove que o teorema e´ verdadeiro para o caso base – tipicamente n ==
0 ou n == 1 (passo base)
2 formule uma hipo´tese indutiva (passo indutivo)
3 mostre que se o teorema e´ verdadeiro para um k qualquer, enta˜o o e´
para k + 1
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 38 / 47
Recursividade
Prova por Induc¸a˜o
Prove que para todos os inteiros n ≥ 1,
1 + 2 + ...+ n = n(n + 1)2
1 Passo base: P(n0) = P(1)
n0 = 1, 1 =
1(1 + 1)
2 = 1
a fo´rmula e´ verdadeira para n0 = 1
2 Passo indutivo: se a formula e´ verdadeira para n = k, enta˜o deve ser
verdadeira para n = k + 1: P(k)→ P(k + 1)
hipo´tese indutiva
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 39 / 47
Recursividade
Prova por Induc¸a˜o
Deve-se mostrar que:
P(k + 1) = 1 + 2 + ...+ (k + 1) = (k + 1)(k + 1 + 1)2 =
(k + 1)(k + 2)
2
Sabe-se que:
1 + 2 + ...+ k + (k + 1) = k(k + 1)2 + (k + 1)
=
k(k + 1)
2 +
2(k + 1)
2
=
(k + 1)(k + 2)
2
Logo, esta´ provada a corretude da induc¸a˜o
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 40 / 47
Recursividade
Prova por Induc¸a˜o
Prove que para todos os inteiros n ≥ 0,
0 + 1 + 2 + ...+ n = n(n + 2)2
1 Passo base: P(n0) = P(0)
n0 = 0, 0 =
0(0 + 2)
2 = 0
a fo´rmula e´ verdadeira para n0 = 0
2 Passo indutivo: se a formula e´ verdadeira para n = k, enta˜o deve ser
verdadeira para n = k + 1: P(k)→ P(k + 1)
hipo´tese indutiva
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 41 / 47
Recursividade
Prova por Induc¸a˜o
Deve-se mostrar que:
P(k + 1) = 0 + 1 + 2 + ...+ (k + 1) = (k + 1)(k + 3)2 =
k2 + 4k + 3
2
Sabe-se que:
0 + 1 + 2 + ...+ k + (k + 1) = k(k + 2)2 + (k + 1)
=
k2 + 2k
2 +
2(k + 1)
2
=
k2 + 2k + 2k + 2
2 =
k2 + 4k + 2
2
Como na˜o foi poss´ıvel derivar a conclusa˜o a partir da hipo´tese, conclui-se
que o predicado original e´ falso
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 42 / 47
Recursividade
Prova por Induc¸a˜o
Prove que para todos os inteiros n ≥ 0,
P(n) : 20 + 21 + 22 + ...+ 2n = 2n+1 − 1
1 Passo base: P(n0) = P(0)
n0 = 20 = 1, 21 − 1 = 1
a fo´rmula e´ verdadeira para n0 = 0
2 Passo indutivo: se a formula e´ verdadeira para n = k, enta˜o deve ser
verdadeira para n = k + 1: P(k)→ P(k + 1)
hipo´tese indutiva
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 43 / 47
Recursividade
Prova por Induc¸a˜o
Deve-se mostrar que:
P(k + 1) = 20 + 21 + 22 + ...+ 2k + 2k+1 = 2k+2 − 1
Sabe-se que:
20 + 21 + 22 + ...+ 2k + 2k+1 = (2k+1 − 1) + 2k+1
= 2.2k+1 − 1
= 2k+2 − 1
Logo, esta´ provada a corretude da induc¸a˜o
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 44 / 47
Recursividade
Quando na˜o Usar Recursividade
A Sequeˆncia de Fibonacci apresenta claramente uma natureza
recursiva
Nem todo problema de natureza recursiva deve ser resolvido com um
algoritmo recursivo
Existe uma forma mais eficiente de implementar Fibonacci
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 45 / 47
Recursividade
Quando na˜o Usar Recursividade
Forma mais eficiente – iteratividade
Algoritmo 8: Algoritmo de Fibonacci iterativo
int fibIte(int n){
if(n == 0||n == 1)
return n;
else{
int aux1 = 0, aux2 = 1;
int fib;
for(int i = 1; i<n;i++){
fib = aux2 + aux1;
aux1 = aux2;
aux2 = fib;
}
return fib;
}
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 46 / 47
Recursividade
Recursividade
Considerac¸o˜es finais sobre recursividade
Te´cnica bastante adequada para expressar algoritmos que sa˜o
definidos recursivamente
No entanto, deve ser usada com muito cuidado
Na maior parte dos casos funciona como uma te´cnica conceitual ao
inve´s de uma te´cnica computacional
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 47 / 47
Recursividade
Recursividade
Exerc´ıcio
A func¸a˜o f (x , n) = xn pode ser implementada de forma recursiva?
Como seria a implementac¸a˜o desse algoritmo?
Rodolfo Carneiro Cavalcante (UFAL) Aula 02Algoritmos e Recursividade 2 de Abril de 2015 48 / 47
	Introdução
	Medida de Tempo de Execução de um Algoritmo
	Recursividade

Outros materiais