44
INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE GRANDE DO NORTE Algoritmos e Técnicas de Programação Programação É Docente: Éberton da Silva Marinho e-mail: [email protected] [email protected] Curso de Tecnologia em Sistemas para Internet 03/09/2013

Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

  • Upload
    others

  • View
    0

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO

GRANDE DO NORTEGRANDE DO NORTE

Algoritmos e Técnicas de ProgramaçãoProgramação

ÉDocente: Éberton da Silva Marinhoe-mail: [email protected]@ifrn.edu.br

Curso de Tecnologia em Sistemas para Internet

03/09/2013

Page 2: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

SUMÁRIOFunçõesBiblioteca padrão do C++Recursividade

2222

Page 3: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

FUNÇÕES

Page 4: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

FUNÇÕESTrecho de código com uma finalidade específica, bem determinadaP d t dif t d d d d li d Pode ter diferentes nomes dependendo da linguagem de programação: sub-rotinas, procedimentosVantagensVantagens

Reutilização de códigoEconomia de espaçoEconomia de espaçoEconomia de tempoMelhor isolamento do códigogDeixa o código mais organizado e fácil de manipular

44

Page 5: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

FUNÇÕESUma função é um trecho de código que pode ser chamada de qualquer parte de um programaE t t d f ãEstrutura de uma funçãotipo_de_retorno nomeFunção ( lista_de_Parâmetros ){

//corpo da função//corpo da função

return expressão

}

tipo_retorno: tipo de retorno devolvido pela função ou a palavra void para indicar que nenhum valor é devolvidonomeFunção: identifica a funçãonomeFunção: identifica a funçãolista_de_Parâmetros: lista de parâmetros, separados por vírgula, que a função poderá utilizar

ã V l d l id l f ã d h l 5expressão: Valor devolvido pela função, quando houver valor a retornar

5

Page 6: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

FUNÇÕES

66

Page 7: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

FUNÇÕESNome de uma função

Começa com uma letra ou um sublinhado (_) e pode conter letras números ou outros sublinhadosconter letras, números ou outros sublinhadosLembrem-se que C++ é sensível ao caso

77

Page 8: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

FUNÇÕESChamada a uma função

A chamada a uma função de um programa é feita primeiramente a partir da função mainprimeiramente a partir da função main.

88

Page 9: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

FUNÇÕESProtótipos das funções

C++ requer que uma função seja declarada ou definida antes de seu uso O modelo de uma função é definida antes de seu uso. O modelo de uma função é chamada de protótipoUm protótipo de função possui o mesmo cabeçalho da implementação, porém terminando com ‘;’Em um protótipo de função o nome dos parâmetros pode ser omitido deixando apenas os tipos dos pode ser omitido, deixando apenas os tipos dos parâmetros.

Exemploint max( int, int);

99

Page 10: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

PARÂMETROS DE UMA FUNÇÃOPassagem de parâmetros por valor

A função recebe uma cópia dos valores dos de quem chama a funçãochama a funçãoSe o valor de um parâmetro variável local é mudado, a mudança afeta apenas a função e não tem efeito fora dela

1010

Page 11: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

PARÂMETROS DE UMA FUNÇÃO

1111

Page 12: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

PARÂMETROS DE UMA FUNÇÃOUtiliza-se a passagem de parâmetro por referência quando se deseja que uma função modifique o valor do parâmetro passado e devolva modifique o valor do parâmetro passado e devolva este valor para a função de chamadaUm parâmetro passado por referência tem o Um parâmetro passado por referência tem o símbolo ‘&’ precedido do nome da variável

1212

Page 13: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

PARÂMETROS DE UMA FUNÇÃO

1313

Page 14: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

EXERCÍCIOFaça um programa um caixa eletrônico que dado um valor x a ser sacado pelo usuário, o programa informe quantas notas de cada valor abaixo serão emitidasquantas notas de cada valor abaixo serão emitidas

Notas de 1:Notas de 1:Notas de 5:N t d 20Notas de 20:Notas de 100:

Para cada uma das notas, faca uma função que receba um valor e retorne a quantidade de notas que devem 14um valor e retorne a quantidade de notas que devem ser emitidas

14

Page 15: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

EXERCÍCIO RESOLVIDO#include <iostream> void intercambio1(int pri, int

void intercambio1(int, int);

void intercambio2(int&, int&);

seg){

int aux;

aux = pri;

i

int main(){

int a, b;

pri = seg;

seg = aux;

}

a= 10; b = 20;

intercambio1(a, b);

std::cout << "chamada a

void intercambio2(int& pri, int& seg){

int aux;std::cout << "chamada a intercambio1 a=" << a << " e b=" << b << endl;

aux = pri;

pri = seg;

seg = aux;

intercambio2(a, b);

std::cout << "chamada a intercambio2 a=" << a << " e

}

15intercambio2 a a e b=" << b << endl;

return 0;

}

15

Page 16: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

ESCOPOE é d l iá l é i í lEscopo é a zona de um programa na qual uma variável é visível.Tipos de escopo

Escopo de programaEscopo de programaEscopo de arquivo-fonteEscopo de funçãop çEscopo de bloco

int i; // Escopo de programa

static int j; // Escopo de arquivo

func(int k){ // Escopo de programa, k escopo de blocofunc(int k){ // Escopo de programa, k escopo de bloco

int m; // Escopo de bloco

... // Escopo de função16

}16

Page 17: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

ESCOPO DE PROGRAMAVariáveis deste tipo podem ser referenciadas por qualquer função no programa completo; também chamadas de variáveis globaischamadas de variáveis globais

int g h; // Variáveis globaisint g, h; // Variáveis globais

main(){

// ...

}

1717

Page 18: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

ESCOPO DE ARQUIVOVariável declarada fora de qualquer função, cujo modelo contém a palavra reservada static, tem escopo de arquivo fonte Tais variáveis podem ser escopo de arquivo-fonte. Tais variáveis podem ser referenciadas em qualquer ponto do arquivo onde a mesma foi declarada.

static int i;

void func(){

...

}}

1818

Page 19: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

ESCOPO DE FUNÇÃOUma variável declarada dentro de uma função pode ser acessada apenas dentro dela.

func(int k){ // k tem Escopo de função

int m; // Escopo de funçãoint m; // Escopo de função

... // Escopo de função

}

1919

Page 20: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

ESCOPO DE BLOCOVariável declarada dentro de um bloco

void funcdemo(){

for(int i = 0; i<10; i++){

std::cout << “i” << “\n”;

}

// Aqui a variável i não é visível

}}

2020

Page 21: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

VARIÁVEIS LOCAISAlém de um escopo restrito, elas só ficam na memória enquanto a execução do programa estiver no escopo da variávelestiver no escopo da variável

Economia de memóriaSegurança, pois apenas uma parte do código pode Segurança, pois apenas uma parte do código pode manipular a variável localMelhor organização do código

2121

Page 22: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

CONCEITO E USO DE CONCEITO E USO DE FUNÇÕES DE BIBLIOTECA

Page 23: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

BIBLIOTECA C++C++ vem com uma biblioteca de funções para suporte a algumas operações que são mais realizadas pelos usuáriosrealizadas pelos usuáriosAs funções que desempenham papéis semelhantes são organizados em grupo através semelhantes são organizados em grupo através de bibliotecas (arquivo com a declaração das funções – arquivo de cabeçalho)

2323

Page 24: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

BIBLIOTECA C++Bibli i dBibliotecas mais usadas

E/S padrãoMatemáticaRotinas-padrãoVisualizar janela de textoDe conversãoDe diagnósticoDe manipulação de memóriaControle de processoClassificaçãoDiretóriosData e horaDe interfaceDiversasBusca 24Manipulação de cadeiasgráficos

24

Page 25: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

FUNÇÕES DE CARACTERE (CCTYPE)

2525

Page 26: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

FUNÇÕES NUMÉRICAS (CMATH, Ç ( ,CSTDLIB)

Funções Matemáticas

2626

Page 27: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

FUNÇÕES NUMÉRICAS (CMATH, Ç ( ,CSTDLIB)

Funções Trigonométricas

2727

Page 28: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

FUNÇÕES NUMÉRICAS (CMATH, Ç ( ,CSTDLIB)o Funções Logarítmicas e Exponenciais

2828

Page 29: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

EXERCÍCIOS COM BIB. MATEMÁTICA

C i l i ifi li 1. Crie um programa calc_cientifica para realizar as operações listadas abaixo. Inicialmente deve ser apresentado ao usuário uma interface com as opções que ele pode escolher. Depois o programa deve ler o(s) valor(es) correspondentes a opção escolhida e apresentar o resultado ao usuário

• Exemplo• ExemploDigite uma das opções entre colchetes[P] : pow(x, y)[ ] p ( , y)[S] : sqrt(x)[E] : exp(x)[L] : log(x)Opção: _

2929

Page 30: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

NÚMERO ALEATÓRIOS E PSEUDO-ALEATÓRIOS

E b lh ú l ó i i Em computação não trabalhamos com números aleatórios pois não há como gerar um número realmente aleatórioEm computação, geramos números pseudo-aleatórios com base em Em computação, geramos números pseudo aleatórios com base em fórmulas que fazem parecer a série de números gerados aleatório.Características de uma boa fórmula

não repetição: a sequncia não pode estar em ciclo e nem se repetir;boa distribuição numérica: se a fórmula está gerando boa distribuição numérica: se a fórmula está gerando números aleatórios entre 0 e 9, o número de zeros, uns, dois, etc. que ela gera devem ser aproximadamente iguais depois de um longo período de tempo;um longo período de tempo;ausência de previsões: você não tem como prever qual será o próximo número, a não ser que conheça a fórmula e

30a origem (o valor inicial). 30

Page 31: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

FUNÇÕES NUMÉRICAS - NÚMEROS ÇALEATÓRIOS

Principais funções: rand, random, randomize e srand. Tais funções estão na biblioteca cstdlib

d() t ú d l tó i t 0 rand(): retorna um número pseudo-aleatório entre 0 e um valor máximo definido em C++randomize(): inicializa o gerador de números pseudo-() g paleatórios com base no tempo (semente), logo a biblioteca ctime deve ser incluída no programa

d( t ) i i i li d d ú srand(semente): inicializa o gerador de números pseudo-aleatórios com uma semente. random(número): gera um número aleatório dentro ( ) gde um intervalo especificadoSe utilizarmos as funções rand ou random sem usar

d d i t 31srand ou randomize, sempre teremos a mesma sequência de números aleatórios

31

Page 32: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

EXEMPLOS

#i l d i#include <iostream>

#include <cstdlib>

#include <ctime>

int main(){

srand(100);

std::cout << “Número aleatório menor que 10 ”

<< rand() % 10;<< rand() % 10;

return 0;

}

3232

Page 33: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

EXERCÍCIOSCrie um programa que gere 15 números aleatórios entre 1 e 100 utilizando as funções dadas anteriormentedadas anteriormente.

Crie um programa que gere 10 000 números Crie um programa que gere 10.000 números aleatórios entre 1 e 10 e guarde em variáveis quantas vezes cada um apareceu. Exiba estes quantas vezes cada um apareceu. Exiba estes números. Qual a conclusão que podemos chegar sobre a função aleatória de tais números?

3333

Page 34: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

RECURSIVIDADE

Page 35: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

RECURSIVIDADE

DefiniçãoFunção que chama a si mesma diretamente (na mesma função) ou indiretamente (através de outra(s) mesma função) ou indiretamente (através de outra(s) função(ões)).

ExemplospAnalisadores sintáticos recursivosEstratégia dividir para conquistarProgramação dinâmicaFatorial

3535

Page 36: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

RECURSIVIDADE

Fatorialn! = n * (n-1) * (n-2) * ... * 2 * 1

! n! = n * (n-1)!n * (n-1) * (n-2)!( ) ( )n * (n-1) * (n-2) * ... * 2!n * (n-1) * (n-2) * ... * 2 * 1!

Critério de paradaQuando n for igual a 1Quando n for igual a 1

3636

Page 37: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

RECURSIVIDADE

Fatorial de um número usando a recursividade

3737

Page 38: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

RECURSIVIDADE

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çãoempilhados na pilha de execução.

3838

Page 39: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

RECURSIVIDADE

Toda função que puder ser produzida por um computador pode ser escrita como função recursiva sem o uso de iteração; reciprocamente recursiva sem o uso de iteração; reciprocamente, qualquer função recursiva pode ser descrita através de iterações sucessivas.çAlgumas linguagens desenvolvidas para programação lógica e programação funcional permitem recursões como única estrutura de repetição, tais como o map e Scheme.

3939

Page 40: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

RECURSÃO VERSUS ITERAÇÃO

N l d f t i l i l t ã No exemplo do fatorial, a implementação iterativa tende a ser ligeiramente mais rápida na prática do que a implementação recursiva, uma p á ca o q e a p e e ação ec s va, a vez que uma implementação recursiva precisa registrar o estado atual do processamento de maneira que ela possa continuar de onde parou maneira que ela possa continuar de onde parou após a conclusão de cada nova execução subordinada do procedimento recursivo. Esta ação consome tempo e memória. Existem outros tipos de problemas cujas soluções são inerentemente recursivas já que elas são inerentemente recursivas, já que elas precisam manter registros de estados anteriores.

Percurso de uma árvore; 40;Algoritmos de divisão e conquista,

40

Page 41: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

RECURSIVIDADEVantagensVantagens

Os algoritmos recursivos normalmente são mais compactos, mais legíveis e mais fáceis de serem compreendidos. Algoritmos para resolver problemas de natureza recursiva são fáceis de serem implementados em linguagens de

ã d l í lprogramação de alto nível.Desvantagens

Por usarem intensivamente a pilha, o que requer alocações e desalocações de memória os algoritmos recursivos tendem a ser mais lentos que os memória, os algoritmos recursivos tendem a ser mais lentos que os equivalentes iterativos, porém pode valer a pena sacrificar a eficiência em benefício da clareza. Algoritmos recursivos são mais difíceis de serem depurados durante a fase de desenvolvimento.

A li õAplicaçõesNem sempre a natureza recursiva do problema garante que um algoritmo recursivo seja a melhor opção para resolvê-lo. O algoritmo recursivo para obter a seqüência de Fibonacci é um ótimo exemplo disso.Algoritmos recursivos são aplicados em diversas situações como em: i) problemas envolvendo manipulações de árvores; ii) analisadores léxicos recursivos de compiladores; e iii) problemas que envolvem tentativa e erro ("Backtracking"). 41( g ) 41

Page 42: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

EXERCÍCIO

Crie uma função recursiva que dado um número, a função deva imprimir recursivamente os antecessores do número até que chegue a 0antecessores do número até que chegue a 0.

4242

Page 43: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

EXERCÍCIOSLista de exercícios

4343

Page 44: Algoritmos e Técnicas de Programação - IFRN...INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO RIO GRANDE DO NORTE Algoritmos e Técnicas

DÚVIDAS

e-mail:[email protected]@ifrn.edu.br

Endereço eletrônico da disciplina: http://docente.ifrn.edu.br/ebertonmarinho

44444444