Apostila Resumo Recursividade e Alocação de Memória

Prévia do material em texto

ALGORITMOS E ESTRUTURAS DE DADOS 
– RECURSIVIDADE E ALOCAÇÃO DE MEMÓRIA – 
 
 
 
Resumo para estudos gerais feito por 
Mirla Rocha de Oliveira Ferreira 
 
 
 
SUMÁRIO 
 
RECURSIVIDADE ..................................................................................................................... 1 
O que é? ................................................................................................................................................ 1 
Exercícios .............................................................................................................................................. 3 
ALOCAÇÃO DE MEMÓRIA ..................................................................................................... 4 
Alocação de memória estática .............................................................................................................. 4 
Alocação de memória dinâmica ............................................................................................................ 4 
Exercicios .................................................................................................... Erro! Indicador não definido. 
ESTRUTURAS DE DADOS ...................................................................................................... 8 
Exercícios .............................................................................................................................................. 9 
REFERÊNCIAS BIBLIOGRÁFICAS ..................................................................................... 11 
 
 
FIGURAS 
 
FIGURA 1 ............................................................................................................................................................................. 4 
 
 
 
TABELAS 
 
 
TABELA 1 ............................................................................................................................................................................. 4 
TABELA 2 ............................................................................................................................................................................. 5 
TABELA 3 ............................................................................................................................................................................. 5 
TABELA 4 ............................................................................................................................................................................. 5 
 
 
1 
RECURSIVIDADE 
 
O que é? 
A recursividade é uma forma de resolver problemas dividindo os mesmos em 
problemas menores (subproblemas) que sejam da mesma natureza. 
Pode ser considerada uma estratégia de redução do problema até que ele se torne 
passível de entendimento e solução. 
Dessa forma, a recursividade permite que um programa chame a si mesmo, dentro do 
próprio programa para resolver o problema em questão. 
 
Por exemplo: 
 
Uma função fatorial, onde o cálculo de n é feito através de n-1 e assim por diante. 
 
 
 
 
Então, 
 
 
 
A recursividade pode ser: 
 
 Recursão direta, onde uma função chama a si mesma dentro da própria 
função. 
 Recursão indireta, onde uma função chama outra função e esta última chama 
novamente a primeira. 
 
Sendo assim, a recursividade gera um loop infinito de execução da função. Para tanto, 
será preciso usar uma condição de parada que finalize o procedimento iniciado. 
Para cada execução de uma recursividade, os parâmetros e variáveis são empilhados 
na pilha de execução. 
 
Exemplo: 
O cálculo de um número fatorial usando recursividade: 
 
 
 
A execução deste código ficaria assim: 
 
 
 
 
 
 
 
 
 
2 
 
 
 
Por isso, vale lembrar que o uso da recursividade em algum programa nem sempre é 
a melhor opção, pois pode gerar complexidade na execução do programa. Porém, para algoritmos 
que já possuem a implementação complexa e necessitam do uso de uma pilha, o uso da 
recursividade ajuda na implementação. 
 
 Em algoritmos que precisam de divisão para minimizar o problema. 
 Em algoritmos que precisam gerar pesquisa, caminho entre árvores. 
 
Nunca em problemas que: 
 
 Repetem excessivamente a recursividade. 
 Ou reduzem o problema de forma muito simples. 
 
Exemplo: 
A implementação de uma função que classifica os elementos de um vetor em ordem 
crescente. 
A descrição do que deve ser feito ficaria assim: 
 
m é o elemento central do vetor 
i e j são a indicação do primeiro e último elemento do vetor, respectivamente 
enquanto i for menor ou igual a j: 
 o valor de i deve crescer até encontrar um elemento maior que m, 
 o valor de j deve diminuir até encontrar um elemento menor que m 
 e ocorre uma troca entre os elementos que ocupam as posições i e j. 
 
 Esses passos se tratam do algoritmo quicksort. 
 
 
 
 
 
3 
Exercícios 
1. Escreva uma função recursiva que calcule a soma dos primeiros n cubos: S = 1³ + 
2³ + … + n³ 
2. Escreva um procedimento recursivo para imprimir todos os números naturais de 0 
até N em ordem crescente. 
3. Escreva um procedimento recursivo para imprimir todos os números naturais de 0 
até N em ordem decrescente. 
4. Escreva uma função recursiva que receba um valor inteiro x e o retorne invertido. 
Exemplo: se x = 123, a função deve retornar 321. 
 
 
 
 
4 
ALOCAÇÃO DE MEMÓRIA 
 
Alocação de memória estática 
O espaço na memória reservado para as variáveis é definido no início, não podendo 
ser mudado depois. 
Alocação de memória dinâmica 
O espaço na memória é alocado dinamicamente durante a execução do programa. 
Sendo assim, temos os apontadores ou pointers que são as variáveis alocadas 
dinamicamente, que armazenam (apontam) o endereço de memória de uma variável. 
 
 
 
Figura 1 
 
Para um apontador, na linguagem C, a declaração é feita com *p para identificar o 
conteúdo da variável apontado por p, enquanto a alocação de uma memória para p é (Tipo*) 
malloc(sizeof(Tipo)) da biblioteca <stdlib.h>, onde free(p) libera a memória, null declara nulo o 
valor do apontador, &a é a representação de um endereço da variável a. Lembrando que 
printf(“%p”, p) imprime o endereço da memória enquanto printf(“%p”, *p) imprime o conteúdo 
armazenado no endereço. 
 
Exemplo de como acontece a alocação dinâmica: 
Para 
 
int *a, b; 
//... 
b = 10; 
a = (int *) malloc(sizeof(int)); 
*a = 20; 
a = &b; 
*a = 30; // qual o valor de b? 
 
Temos: 
 
Memória atribuída (estática) Heap (memória na qual a memória dinâmica faz parte) 
#e01 #h01 0 
#e02 #h02 0 
Tabela 1 
 
5 
Enquanto o conteúdo da Heap permanecer em 0, significa que a memória ainda não 
foi alocada. 
Seguindo o programa, primeiramente será declarado na memória estática as variáveis 
inteiras a e b. 
Logo depois o conteúdo de b já recebe o valor 10. A tabela ficaria assim: 
 
Memória atribuída (estática) Heap (memória na qual a memória dinâmica faz parte) 
#e01 a #h01 0 
#e02 b 10 #h02 0 
Tabela 2 
 
A variável a logo receberá alocação na memória Heap, o que passará a ter o valor 1. E 
depois o valor do conteúdo da memória heap receberá 20. 
 
Memória atribuída (estática) Heap (memória na qual a memória dinâmica faz parte) 
#e01 a #h01 #h01 1 20 
#e02 b 10 #h02 0 
Tabela 3 
 
Então, logo em seguida, há a troca da referência de endereçamento para a variável a, 
que não mais terá #h01 como apontador e sim #e02, que é o endereço de b. Então, quando o 
valor do endereçamento de a recebe o valor 30, é em #e02 que esse valor é atribuído. 
 
Memória atribuída (estática) Heap (memória na qual a memória dinâmica faz parte) 
#e01 a #e02 #h01 1 20 
#e02 b 30 #h02 0 
Tabela 4 
 
Observe que no código não há nenhuma liberação da memória alocada. É preciso 
acrescentar um free(a) para liberar a memória Heap, mudando #h01 para 0. Porém, como no final 
do código a variável a aponta para a memória #e02, o comando free precisará ser colocado antes 
da troca de referência de endereçamento.int *a, b; 
//... 
b = 10; 
a = (int *) malloc(sizeof(int)); 
*a = 20; 
free(a); 
a = &b; 
*a = 30; 
 
Ao desenvolver algum programa usando alocação dinâmica de memória, é preciso 
lembrar-se de: 
 alocar a memória, 
 copiar o valor que o apontador se refere (*p) e não o endereço do apontador 
em si (&p) ou o conteúdo do apontador (p), 
 liberar a memória (depois de liberada o seu conteúdo não poderá mais ser 
acessado). 
 
Exemplo: 
De acordo com o código abaixo, serão impressos os seguintes valores: 
 
6 
 
 
Exemplo do desenvolvimento de um programa usando alocação dinâmica: 
Um programa que leia um valor n, crie dinamicamente um vetor de n elementos e 
passe esse vetor para uma função que vai ler os elementos desse vetor. 
 
 
Exercícios 
1. Mostre as saídas para os códigos abaixo: 
 
a) 
 
#include <iostream> 
using namespace std; 
int main () 
{ 
int value1 = 5, value2 = 15; 
int *p1, *p2; 
p1 = &value1; 
p2 = &value2; 
*p1 = 10; 
*p2 = *p1; 
p1 = p2; 
*p1 = 20; 
return 0; 
} 
 
Conteúdo de a: 10 
Endereço de a: 0028FF14 
 
 
Conteúdo de p1: 0028FF14 
Endereço de p1: 0028FF1C 
Valor apontado por p1: 10 
 
 
Conteúdo de p2: 003E2B50 
Endereço de p2: 0028FF18 
Valor apontado por p2: 10 
 
7 
b) 
 
#include <iostream> 
using namespace std; 
 
int main(){ 
 float taxa = 5.3, valor=3.0; 
 float *ptaxa = &taxa; 
 
 valor *= (*ptaxa); 
 *ptaxa = 3.3; 
 
 cout<<”A taxa = “<< taxa << “ e o valor = “ << valor<< endl; 
 system(“PAUSE”); 
 return 0; 
} 
 
 
 
 
8 
ESTRUTURAS DE DADOS 
 
Modos de organização de dados, de tal forma que otimizem o processamento desses 
dados. Qualquer que seja a estrutura, deve sempre gerar os seguintes processamentos dentro da 
estrutura: 
 Busca de dados 
 Inserção de dados 
 Remoção de dados 
 
Exemplo: 
Para implementar um programa que faz as operações de uma calculadora para 
frações, ficaria da seguinte forma: 
 
 
 
Observe as declarações com muitos parâmetros. A estrutura de dados permite 
implementar da seguinte forma: 
 
 
9 
 
 
O struct serve para se criar uma nova estrutura que agrupará variáveis de diversos 
tipos em uma só variável. O typedef determina um novo nome para a estrutura 
especificada. Para utilizar as variáveis dessa estrutura insira um ponto entre a variável 
e o campo desejado. 
 
Exercícios 
1. Crie uma estrutura para representar as coordenadas de um ponto no plano 
cartesiano nas posições X e Y. Declare e leia do teclado dois pontos, exibindo a 
distância entre eles. 
2. Crie uma estrutura chamada Retangulo. Essa estrutura deverá conter o ponto 
superior esquerdo e o ponto inferior direito do retângulo. Cada ponto é definido por 
uma estrutura Ponto, criada no exercício anterior. Faça um programa que declare 
e leia uma estrutura Retangulo e exiba a área, o comprimento da diagonal e o 
perímetro desse retângulo. 
3. Crie uma estrutura Aluno representando um aluno de uma disciplina. Essa estrutura 
deve conter o número de matrícula do aluno, seu nome e as notas de três provas. 
Agora, escreva um programa que leia os dados de cinco alunos e os armazena 
nessa estrutura. Em seguida, exiba o nome e as notas do aluno que possui a 
maior média geral dentre os cinco. 
4. Estude o código abaixo e explique o que ele faz. Dê exemplo de inserção de 
variáveis e mostre a saída de acordo com as as variáveis de entrada. 
#include <iostream.h> 
#include <stdlib.h> 
#define N_MOVIES 5 
struct movies_t { 
char title [50]; 
int year; 
} films [N_MOVIES]; 
void printmovie (movies_t movie) { 
cout << movie.title; 
 
10 
cout << " (" << movie.year << ")\n"; 
} 
int main () 
{ 
char buffer [50]; 
int n; 
for (n=0; n<N_MOVIES; n++) { 
cout << "Enter title: "; 
cin.getline (films[n].title,50); 
cout << "Enter year: "; 
cin.getline (buffer,50); 
films[n].year = atoi (buffer); 
} 
cout << "\nYou have entered these movies:\n"; 
for (n=0; n<N_MOVIES; n++) 
printmovie (films[n]); 
return 0; 
} 
 
11 
REFERÊNCIAS BIBLIOGRÁFICAS 
ASCENIO, Ana Fernanda Gomes, CAMPOS, Edilene Aparecida Veneruchi de. 
Fundamentos da Programação de computadores. PEARSON. Prentice Hall. São Paulo. 
CELES, Waldemar; CERQUEIRA, Renato; RANGEL, José Lucas. Introdução a 
estruturas de dados com técnicas de programação em C. Editora Campus. 
FORBELLONE, André Luiz Villar; EBERSPACHER, Henri Frederico. Lógica de 
Programação. A construção de algoritmos e estruturas de dados. 3ª Edição. 2005. 
LAUREANO, Marcos. Estrutura de Dados com Algoritmos e C. BRASPORT Livros 
e Multimídia Ltda. 2008. 
LUCCHESI, Cláudio; KOWALTOWSKI, Tomasz. Estruturas de Dados e Técnicas de 
Programação. UNICAMP. Versão 1.12. 2004. 
MARTIN, Daniel M. Aulas. Algoritmos e Estrutura de Dados I. UFABC. 
MELO, Pedro Olmo Stancioli Vaz de. Aulas. Algoritmos e Estrutura de Dados I. DCC – 
UFMG. 
MENOTTI, David. Aulas. Algoritmos e Estrutura de Dados I. DECOM – UFOP. 
TENENBAUM, Aaron. Estruturas de Dados Usando C. MAKRON Books do Brasil 
Editora Ltda.