Baixe o app para aproveitar ainda mais
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
Compartilhar