06. Recursividade e Referencias

Prévia do material em texto

RECURSIVIDADE E REFERÊNCIAS
Estrutura de Dados I
Recursividade
 Em C++ uma função pode ser chamada a 
partir de qualquer outra função
int main()
{
cout << "Iniciando na função principal!" << endl;
simples(); // chamada da função simples
...
}
void simples()
{
cout << "Esta função é simples!" << endl;
complicada(); // chamada da função complicada
}
void complicada()
{
cout << "Esta função não é complicada!" << endl;
}
Recursividade
 Uma função pode ser chamada até a partir 
dela mesma, uma chamada recursiva
int main()
{
cout << "Iniciando na função principal!" << endl;
simples(); // chamada da função simples
...
}
void simples()
{
cout << "Esta função é simples!" << endl;
complicada(); // chamada da função complicada
}
void complicada()
{
cout << "Agora esta função é complicada!" << endl;
complicada(); // chamada recursiva
} 
Recursividade
 A função main() é uma exceção, ela não pode 
conter uma chamada recursiva (em C++)†
 Uma função que chama a si mesma deve 
possuir algum mecanismo de parada para 
encerrar a seqüência de chamadas
void complicada(int n)
{
cout << "Agora esta função é complicada!" << endl;
if (n > 0) // mecanismo de parada da recursão
{
n = n – 1;
complicada(n); // chamada recursiva
}
} 
Recursividade
 Sempre que uma chamada recursiva é 
encontrada o programa reinicia a execução 
da função
void complicada(int n)
{
cout << "Agora esta função é complicada!" << endl;
if (n > 0) // mecanismo de parada da recursão
{
n = n – 1;
complicada(n); // chamada recursiva
}
// executada somente ao final das chamadas recursivas
cout << "Não é verdade?" << endl; 
} 
Recursividade
 Cada execução cria seu próprio ambiente 
com um conjunto de variáveis independentes
void complicada(int n)
{
cout << "Entrada " << n << endl; 
if (n > 0)
complicada(n-1); 
cout << "Saída " << n << endl;
} 
Complicada
n = 3
Saída 3
Entrada 3
complicada(2)
Complicada
n = 2
Saída 2
Entrada 2
complicada(1)
Complicada
n = 1
Saída 1
Entrada 1
complicada(0)
Complicada
n = 0
Saída 0
Entrada 0
complicada(3);
Recursividade
// regressiva.cpp – entrando e saindo dos níveis de recursão
#include <iostream>
using namespace std;
void regressiva(int n); // protótipo da função
int main()
{
regressiva(4); // chamada da função
system("pause"); 
return 0;
}
void regressiva(int n)
{
cout << "Contagem regressiva... " << n << endl;
if (n > 0)
regressiva(n-1); // chamada recursiva
cout << n << " : Kaboom!\n"; 
}
Recursividade
 Saída do Programa:
Contagem regressiva... 4
Contagem regressiva... 3
Contagem regressiva... 2
Contagem regressiva... 1
Contagem regressiva... 0
0 : Kaboom!
1 : Kaboom!
2 : Kaboom!
3 : Kaboom!
4 : Kaboom! 
Recursividade Múltipla
 Recursão é particularmente útil para dividir 
uma tarefa grande em tarefas menores
 Técnica conhecida por dividir para conquistar
 Desenhar uma régua é uma tarefa grande que 
pode ser subdividida:
 Marque as extremidades
 Encontre e marque o ponto médio
 Repita o processo para as metades esquerda e 
direita
Recursividade Múltipla
// regua.cpp - usando recursão para subdividir uma régua
#include <iostream>
using namespace std;
const int Tam = 66;
const int Div = 6;
void subdivide(char vet[], int low, int high, int nivel); 
int main()
{
char regua[Tam];
for (int i = 1; i < Tam-2; i++)
regua[i] = ' ';
regua[Tam-1] = '\0';
int max = Tam – 2;
int min = 0;
regua[min] = regua[max] = '|'; 
cout << regua << endl;
...
Recursividade Múltipla
for (int i = 1; i <= Div; i++)
{
subdivide(regua, min, max, i);
cout << regua << endl;
for (int j = 1; j < Tam-2; j++)
regua[j] = ' '; // volta para a régua em branco 
}
system("pause"); 
return 0;
}
void subdivide(char vet[], int low, int high, int nivel)
{
if (nivel > 0)
{
int mid = (high + low) / 2;
vet[mid] = '|';
subdivide(vet, low, mid, nivel – 1);
subdivide(vet, mid, high, nivel – 1);
}
}
Recursividade Múltipla
 Saída do Programa:
 As chamadas crescem geometricamente 
 É uma solução elegante para o problema mas para 
um grande número de subdivisões é ineficiente no 
uso da memória
| |
| | |
| | | | |
| | | | | | | | |
| | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Referências
 Uma referência é um nome que atua como 
um apelido para uma variável previamente 
definida
 O símbolo & é usado para declarar uma 
referência
 Neste contexto, & não é o operador de endereço
int rato;
int & roedor = rato; // roedor é um apelido para rato
int * pt = &rato; // ponteiro para int
int & rf = rato; // referência para int
Referências
 A referência permite usar ambos os nomes 
para acessar o mesmo valor e a mesma 
posição de memória
int rato = 25;
int & roedor = rato; // roedor é um apelido para rato
00000000
00000000
00000000
00011001
25
0xCB20 = rato = roedor
0xCB21
0xCB22
0xCB23
0xCB24
0xCB25
0xCB26
0xCB27
Referências
 O principal uso de referências é como 
parâmetro de funções
 Ela representa uma alternativa ao uso de 
ponteiros
 A função trabalha com os dados originais se eles 
forem recebido em uma variável referência
00000000
00000000
00000000
00011001
25
0xCB20 = rato = roedor
0xCB21
0xCB22
0xCB23
0xCB24
0xCB25
0xCB26
0xCB27
void pragas(int & roedor); 
...
int rato = 25;
pragas(rato);
Referências
// roedores.cpp - definindo e usando uma referência
#include <iostream>
using namespace std;
int main()
{
int ratos = 101;
int & roedores = ratos; // roedores é uma referência
cout << "ratos = " << ratos;
cout << ", roedores = " << roedores << endl;
roedores++;
cout << "ratos = " << ratos;
cout << ", roedores = " << roedores << endl;
cout << "endereço de ratos = " << &ratos << endl;
cout << "endereço de roedores = " << &roedores << endl;
system("pause"); 
return 0;
}
Referências
 Saída do Programa:
 Observe a diferença entre o uso de & como 
referência e como operador de endereço
ratos = 101, roedores = 101
ratos = 102, roedores = 102
endereço de ratos = 0x0065fd48
endereço de roedores = 0x0065fd48
int & roedores = ratos; // roedores é uma referência
cout << "endereço de roedores = " << &roedores << endl;
Referências e Ponteiros
 Uma referência parece muito com um 
ponteiro:
 O valor 101 pode ser acessado usando 
ratos, roedores ou *pragas 
 O endereço de 101 pode ser obtido com 
&ratos, &roedores ou pragas
int ratos = 101;
int & roedores = ratos; // roedores é uma referência
int * pragas = &ratos; // pragas é um ponteiro
Referências e Ponteiros
 Mas internamente a linguagem C++ trata 
referências e ponteiros de forma diferente
int ratos = 101;
int & roedores = ratos; // roedores é uma referência
int * pragas = &ratos; // pragas é um ponteiro
00000000
00000000
00000000
01100101
0xCB20
101
= ratos = roedores
0xCB21
0xCB22
0xCB23
0xCB24
0xCB25
0xCB26
0xCB27
= pragas
0xCB20
Referências e Ponteiros
 Existem também diferenças no uso de 
referências e ponteiros:
 Uma referência deve ser sempre inicializada
 Ponteiros podem receber valores a qualquer 
momento
int ratos = 101;
int & roedores; // roedores é uma referência
roedores = ratos; // inválido
int ratos = 101;
int * pragas; // pragas é um ponteiro
pragas = &ratos; // ok
Referências e Ponteiros
// coelhos.cpp - definindo e usandouma referência
#include <iostream>
using namespace std;
int main()
{
int ratos = 101;
int & roedores = ratos; // roedores é uma referência
cout << "ratos = " << ratos;
cout << ", roedores = " << roedores << endl;
cout << "endereço de ratos = " << &ratos << endl;
cout << "endereço de roedores = " << &roedores << endl;
int coelhos = 50;
roedores = coelhos; // podemos mudar a referência?
cout << "coelhos = " << coelhos;
cout << ", ratos = " << ratos;
cout << ", roedores = " << roedores << endl;
cout << "endereço de coelhos = " << &coelhos << endl;
cout << "endereço de roedores = " << &roedores << endl;
system("pause"); 
return 0;
}
Referências e Ponteiros
 Saída do Programa:
 A instrução causou uma atribuição de valor 
mas não redefiniu a referência
ratos = 101, roedores = 101
endereço de ratos = 0x0065fd44
endereço de roedores = 0x0065fd44
coelhos = 50, ratos = 50, roedores = 50
endereço de coelhos = 0x0065fd48
endereço de roedores = 0x0065fd44
int coelhos = 50;
roedores = coelhos; // podemos mudar a referência? NÃO
Referências e Funções
 Freqüentemente referências são usadas 
como parâmetros de funções
 Cria um apelido dentro da função chamada para 
uma variável da função chamadora
 Este método de passagem de argumentos é 
chamado de passagem por referência
00000000
00000000
00000000
00011001
25
0xCB20 = rato = roedor
0xCB21
0xCB22
0xCB23
0xCB24
0xCB25
0xCB26
0xCB27
void pragas(int & roedor); 
...
int rato = 25;
pragas(rato);
Referências e Funções
 Passagem de argumentos por valor
void cubo(int x); 
int main()
{
...
int lado = 5;
cubo (lado);
...
}
void cubo(int x)
{
...
}
Cria variável 
lado e atribui 
o valor 5 a ela
5
lado
valor 
original
Duas variáveis, 
dois nomes
Cria variável x
e atribui o valor 
recebido
5
x valor 
copiado
Referências e Funções
 Passagem de argumentos por referência
Cria variável 
lado e atribui 
o valor 5 a ela
5
x
Uma variável, 
dois nomes
Torna x um 
apelido para a 
variável lado
void cubo(int & x); 
int main()
{
...
int lado = 5;
cubo (lado);
...
}
void cubo(int & x)
{
...
}
lado
Referências e Funções
 Vamos comparar o uso de referências e 
ponteiros em um problema comum:
 Construir uma função para trocar o valor de duas 
variáveis
 A passagem por valor não funciona porque a 
função vai trocar os valores de cópias
void trocav(int a, int b) // passagem por valor
{
int temp;
temp = a;
a = b;
b = temp;
}
Referências e Funções
 Construir uma função para trocar o valor de 
duas variáveis
 Uma função de troca tem que ser capaz de alterar 
os valores das variáveis no programa chamador
 Passando os argumento por referência ou com 
ponteiros os dados originais podem ser acessados
//usando referências
void trocar(int & a, int & b)
{
int temp;
temp = a;
a = b;
b = temp;
}
// usando ponteiros
void trocap(int * pa, int * pb)
{
int temp;
temp = *pa;
*pa = *pb;
*pb = temp;
}
Referências e Funções
// trocar.cpp - trocando valores com referências e ponteiros
#include <iostream>
using namespace std;
void trocar(int & a, int & b); // a e b são apelidos para ints
void tracap(int * pa, int * pb); // pa e pb são ponteiros para ints
void trocav(int a, int b); // a e b são novas variáveis
int main()
{
int carteira1 = 300;
int carteira2 = 500; 
cout << "carteira1 = R$" << carteira1;
cout << " carteira2 = R$" << carteira2 << endl;
cout << "\nUsando referências para trocar o conteúdo:" << endl;
trocar(carteira1, carteira2); // passa variáveis
cout << "carteira1 = R$" << carteira1;
cout << " carteira2 = R$" << carteira2 << endl;
...
Referências e Funções
...
cout << "\nUsando ponteiros para trocar novamente o conteúdo:" << endl;
trocap(&carteira1, &carteira2); // passa endereços das variáveis
cout << "carteira1 = R$" << carteira1;
cout << " carteira2 = R$" << carteira2 << endl;
cout << "\nTentando usar passagem por valor:" << endl;
trocav(carteira1, carteira2); // passa valores das variáveis
cout << "carteira1 = R$" << carteira1;
cout << " carteira2 = R$" << carteira2 << endl;
system("pause"); 
return 0;
}
 Saída do Programa:
 A passagem por valor e por referência parecem 
idênticas, a não ser pelos protótipos das funções
Referências e Funções
carteira1 = R$300 carteira2 = R$500
Usando referências para trocar o conteúdo:
carteira1 = R$500 carteira2 = R$300
Usando ponteiros para trocar novamente o conteúdo:
carteira1 = R$300 carteira2 = R$500
Tentando usar passagem por valor:
carteira1 = R$300 carteira2 = R$500
void trocar(int & a, int & b); // a e b são apelidos para ints
void trocav(int a, int b); // a e b são novas variáveis
Referências com Registros
 Referências foram inicialmente criadas para 
trabalhar com registros e objetos (POO)
struct operador
{
char nome[26];
char slogan[64];
int usado;
};
operador rick = 
{ 
"Rick \"Fortran\" Looper", 
"Goto é comigo mesmo.",
0
};
operador & ref = rick;
Registro operador
Variável rick do tipo operador
Referência para a variável rick
Referências com Registros
// usando referências registros
#include <iostream>
using namespace std;
struct operador
{
char nome[26];
char lema[64];
int usado;
};
const operador & usar(operador & ref); // a função retorna uma referência
int main()
{
operador rick = 
{ 
"Rick \"Fortran\" Looper", 
"Goto é comigo mesmo.",
0
};
...
Referências com Registros
...
usar(rick); // rick é do tipo operador
cout << "Rick: " << rick.usado << " uso(s)\n\n";
operador copia;
copia = usar(rick);
cout << "Rick: " << rick.usado << " uso(s)\n";
cout << "Copia: " << copia.usado << " uso(s)\n\n";
cout << "usar(rick): " << usar(rick).usado << " uso(s)\n";
system("pause");
return 0;
}
const operador & usar(operador & ref)
{
cout << ref.nome << " diz:\n";
cout << ref.lema << endl;
ref.usado++;
return ref; // retorna uma referência ao registro utilizado
}
 Saída do Programa:
 A chamada da função usar() passa rick por 
referência:
Referências com Registros
Rick "Fortran" Looper diz:
Goto é comigo mesmo.
Rick: 1 uso(s)
Rick "Fortran" Looper diz:
Goto é comigo mesmo.
Rick: 2 uso(s)
Copia: 2 uso(s)
Rick "Fortran" Looper diz:
Goto é comigo mesmo.
Rick: 3 uso(s)
usar(rick); // rick é do tipo operador
 A função usar() retorna uma referência:
 A variável copia recebe o conteúdo da 
referência ref (apelido da variável rick)
Referências com Registros
operador copia;
copia = usar(rick);
...
const operador & usar(operador & ref)
{
cout << ref.nome << " diz:\n";
cout << ref.lema << endl;
ref.usado++;
return ref;
}
 O programa usa uma chamada de função 
para acessar um membro do registro
 Isso é possível porque a função usar() retorna 
uma referência para um registro operador
 Tem o mesmo efeito que as instruções: 
Referências com Registros
const operador & usar(operador & ref);
usar(rick);
cout << "usar(rick): " << rick.usado << " uso(s)\n";
cout << "usar(rick): " << usar(rick).usado << " uso(s)\n";
 Ao retornar uma referência é preciso tomar 
cuidado para não retornar uma referência 
para uma variável que deixará de existir
 A variável novo deixará de existir ao final da 
função usar(), invalidando o retorno
Retorno de Referências
// nunca faça isso
const operador & usar(operador & ref)
{
operador novo; // primeiro passo para grande erro
novo = ref; // copia informação
return novo; // retorna uma referência para a cópia
}
 Usando const para o valor de retorno proíbe a 
modificação da variável usando areferência 
retornada 
 Sem o const, isso seria possível:
 Ou ainda pior:
Retorno de Referências
const operador & usar(operador & ref);
usar(rick).usado = 10;
operador polly = {"Polly Morf", "Não sou hacker.", 0};
usar(rick) = polly;
Conclusão
 Existem duas razões para usar referências em 
parâmetros de funções:
 Para permitir a alteração dos argumentos (dados 
originais) dentro da função chamada
 Para acelerar o programa, evitando a cópia de 
uma grande quantidade de dados
 Essas também são as razões para se usar 
ponteiros como parâmetros de funções
Conclusão
 Se uma função usa dados sem modificá-los:
 Se o dado é pequeno, como os de tipo básico, 
passe por valor
 Se é um vetor, use um ponteiro porque é a sua 
única escolha. Use const para o ponteiro.
 Se o dado é um registro, use um ponteiro ou uma 
referência. Use const para evitar modificação.
double soma(double a, double b);
void mostraVetor(const double vet[], int tam);
void usar(const operador & op);
Conclusão
 Se a função modifica os dados originais:
 Se o dado é tipo básico, use um ponteiro. Isso 
deixa claro a intenção de modificá-lo. 
 Se é um vetor, use um ponteiro porque é a sua 
única escolha.
 Se o dado é um registro, use um ponteiro ou uma 
referência.
void atualiza(int * num);
void mostraVetor(int vet[], int tam);
void usar(operador & val);