ALGORITMOS AULA 03

Prévia do material em texto

Protocolos de Redes e de Computadores
AULA 02
ALGORITMOS AVANÇADOS – AULA 03
Prof. Msc. Alexandre José Braga da Silva
alex.professor@gmail.com
CCT0312 – Algoritmos Avançados
Objetivos da Aula:
 Conhecer as definições recursivas
 Aprender como implementar recursividade
 Aprender quando não usar recursividade
 Desenvolver algoritmos com recursividade
CCT0312 – Algoritmos Avançados
Recursividade:
Recursividade não é um comando, mas uma habilidade de uma 
função chamar a si mesma. 
Isto não é privilégio apenas da linguagem C++, muitas outras 
linguagens como Java, Visual Basic, entre outras também possui esta 
habilidade.
Mas é importante entender este conceito, pois ele é muito útil e pode 
ajudar a deixar seu algoritmo muito mais simples.
CCT0312 – Algoritmos Avançados
Recursividade - Implementação:
Para criar uma função recursiva, basta escrever no código da função, a 
função que está sendo criada como se ela já tivesse sido criada antes. 
Vejamos um exemplo simples: temos um programa e sabemos que o 
código do programa está todo dentro da função principal (MAIN). Se 
quisermos reiniciar o programa basta chamarmos a função MAIN 
novamente.
CCT0312 – Algoritmos Avançados
Recursividade - Implementação:
Para criar uma função recursiva, basta escrever no código da função, a 
função que está sendo criada como se ela já tivesse sido criada antes. 
Vejamos um exemplo simples: temos um programa e sabemos que o 
código do programa está todo dentro da função principal (MAIN). Se 
quisermos reiniciar o programa basta chamarmos a função MAIN 
novamente.
CCT0312 – Algoritmos Avançados
Recursividade - Implementação:
#include <iostream>
#include <cstdlib>
using namespace std;
int main(){
int a, b, c, opcao;
cout<<"Digite o valor de A: ";
cin>>a;
cin.ignore();
cout<<"Digite o valor de B: ";
cin>>b;
cin.ignore();
CCT0312 – Algoritmos Avançados
Recursividade - Implementação:
c=a+b;
cout<<"O resultado de A+B: "<<c;
cout<<"\n\nDeseja reiniciar o programa? \n1. Sim\t2. Nao\n\n=> 
";
cin>>opcao;
if (opcao==1)
main();
else
return EXIT_SUCCESS;
}
CCT0312 – Algoritmos Avançados
Recursividade – Quando não usar:
Quando o loop recursivo é muito grande é consumida muita memória 
nas chamadas a diversos níveis de recursão, pois cada chamada 
recursiva aloca memória para os parâmetros, variáveis locais e de 
controle.
Em muitos casos uma solução iterativa gasta menos memória, e 
torna-se mais eficiente em termos de performance do que usar 
recursão.
CCT0312 – Algoritmos Avançados
Análise de Algoritmo Recursivo - Exemplo:
Algoritmo recursivo que calcule a soma dos números entre 1 e n.
int somaNum(int n){
 if (n == 1) // melhor caso
 return 1;
 else // pior caso
 return (n + somaNum(n – 1);
}
Qual o tempo gasto pelo algoritmo no pior caso?
O(log n)
n 
(n n) 
CCT0312 – Algoritmos Avançados
Recursividade – Exemplo simples:
#include <iostream>
using namespace std;
void contador (int num, int cont=1);
int main(){
contador(60);
return 0;
}
void contador (int num, int cont){
cout<<cont<<"\n";
if(num > cont){
contador(num, ++cont);
}
}
CCT0312 – Algoritmos Avançados
Recursividade – Exercício:
Sequência de Fibonacci. Essa sequência consiste em o 1o e o 2o termos são 1, 
e os termos seguintes são a soma dos dois termos anteriores. Ou seja, o 3o 
termo é a soma de 1+1 que é 2; o 4o termo é a soma de 1+2 que é 3; o 5o 
termo é a soma de 2+3 que é 5…
Desenvolver um programa em C++ para gerar esta Sequência de Fibonacci.
CCT0312 – Algoritmos Avançados
Recursividade – Exercício:
#include <iostream>
using namespace std;
int fibonacci(int numero);
int main() {
int a = 20;
cout<<"Numero: "<<a<<endl;
cout<<"Fibonacci: "<<fibonacci(a);
return 0;
}
int fibonacci(int numero) {
 if(numero == 0)
 return 0;
 if(numero > 1)
 return fibonacci(numero-
1)+fibonacci(numero-2);
 else
 return 1;
}
CCT0312 – Algoritmos Avançados
Recursividade – Exercício:
Como inverter uma cadeia de caracteres digitada pelo usuário? 
De um modo recursivo, poderíamos fazer assim:
1. Repartir a cadeia em dois pedaços, A e B, de tamanhos quaisquer;
2. Recursivamente, inverter A e B, obtendo AT e BT;
3. Concatenar BT com AT nessa ordem.
CCT0312 – Algoritmos Avançados
Recursividade – Exercício:
Criar um programa em C++ que inverta um texto digitado pelo usuário de 
forma recursiva.
CCT0312 – Algoritmos Avançados
Recursividade – Exercício:
#include <stdio.h>
void inverte(char *string){
 if(*string){
 inverte(string+1);
 putchar(*string);
 }
}
int main(){
 char texto[20];
 printf("Escreva o texto a ser invertido: ");
 scanf("%s", texto);
 inverte(texto);
}
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15