Unidade 3: Estruturas de Dados com Orientação a Objetos - Filas, Pilhas e Recursividade

30052023 0004 Unidade 3 Estrutura de dados com orientação a objetos httpsambienteacademicocombrmodurlviewphpid784410 132 ESTRUTURA DE ESTRUTURA DE DADOS COM DADOS COM ORIENTAÇÃO A ORIENTAÇÃO A OBJETOS OBJETOS UNIDADE 3 ESTRUTURAS UNIDADE 3 ESTRUTURAS DE DADOS FILAS PILHAS E DE DADOS FILAS PILHAS E RECURSIVIDADE RECURSIVIDADE Autora Ana Lucia Pegetti Autora Ana Lucia Pegetti Revisor Marcos Paulo Lobo De Candia Revisor Marcos Paulo Lobo De Candia INICIAR Introdução Caroa estudante Nesta unidade daremos continuidade ao estudo das estruturas de dados com a linguagem Java trabalhando com as filas e as pilhas nos seus aspectos estáticos e dinâmicos que têm características semelhantes de estruturas já estudadas na Unidade 2 como os arrays e as listas A recursividade também será estudada como um importante mecanismo de programação e que também resolve vários problemas clássicos de programação Veremos as várias aplicações computacionais e reais destas estruturas como o atendimento a solicitações em um único recurso compartilhado em uma impressora por exemplo ou o agendamento de tarefas da CPU promovidos pelas filas e os recursos de fazer e desfazer encontrados em vários programas editores como 30052023 0004 Unidade 3 Estrutura de dados com orientação a objetos httpsambienteacademicocombrmodurlviewphpid784410 232 31 Fila em estrutura estática e dinâmica Como foi visto anteriormente estruturas de dados dinâmicas são projetadas para facilitar a mudança de estruturas de dados em tempo de execução e estruturas de dados estáticas têm tamanho de memória fixo Nas estruturas de dados estáticas a memória alocada tem tamanho predefinido Mesmo que nada seja armazenado o espaço reservado não poderá ser utilizado para armazenar outras informações Caso seja necessária alocação de mais espaço isso não será possível de forma que somente reprogramar ou recompilar o programa viabilizaria esse processo BIANCHI et al 2014 Já nas estruturas de dados dinâmicas a memória é alocada conforme vai sendo necessária para armazenar os dados ou seja é alocada em tempo de execução Neste contexto uma fila é uma estrutura linear que segue uma ordem particular na qual as operações são realizadas podendo ser implementada com auxílio de estruturas de dados estáticas ou dinâmicas Neste tópico abordaremos os principais tipos de filas suas características operações e formas de implementação Visão geral das filas Clique nas setas ou arraste para visualizar o conteúdo o MS Word ou Photoshop e o recurso de avanço e retrocesso em navegadores da web promovido pelas pilhas Bons estudos parte superior Uma fila é semelhante a uma fila de caixa em um supermercado a primeira pessoa é atendida primeiro e os outros clientes entram apenas no final e esperam ser atendidos NÓS DAS FILAS Só são removidos a partir da cabeça da fila e só são inseridos na cauda Por essa razão uma fila é referida como uma estrutura de dados primeiro a entrar primeiro a sair firstin firstout FIFO INSERÇÃO E REMOÇÃO 30052023 0004 Unidade 3 Estrutura de dados com orientação a objetos httpsambienteacademicocombrmodurlviewphpid784410 332 Fonte DEITEL H M DEITEL P J 2017 Puga e Rissetti 2004 sobre filas na área de programação afirmam que estas têm o mesmo conceito que no mundo real Quando se entra na fila de um supermercado para pagar pelos produtos o primeiro elemento a entrar na fila será o primeiro elemento a sair A esse conceito dáse o nome de First In First Out ou FIFO expressão conhecida em português como PEPS ou Primeiro Que Entra Primeiro Que Sai Então no conceito de fila os elementos são atendidos ou utilizados sequencialmente na ordem em que são armazenados Na fila a inserção é feita de uma extremidade conhecida como extremidade traseira ou cauda da fila enquanto a exclusão é feita da outra extremidade conhecida como extremidade dianteira ou cabeça da fila Em outras palavras a fila é uma lista ou coleção em cuja inserção só pode ser realizada em uma extremidade chamada extremidade traseira ou final da fila e a exclusão em outra extremidade chamada de extremidade dianteira ou chefe da fila Veja a representação de uma fila na Figura 1 abaixo As operações de inserção e remoção para uma fila são conhecidas como enqueue e dequeue USO EM SISTEMAS DE COMPUTADOR A maioria dos computadores tem apenas um processador então somente um usuário por vez pode ser servido As entradas para os outros aplicativos são colocadas em uma fila A entrada na frente da fila é a próxima a receber o serviço 30052023 0004 Unidade 3 Estrutura de dados com orientação a objetos httpsambienteacademicocombrmodurlviewphpid784410 432 Figura 1 Representação de uma fila Fonte Elaborada pela autora 2020 Existem várias utilizações de filas em sistemas de computador como o atendimento da CPU às chamadas dos aplicativos ou para dar suporte a spooling de impressão DEITEL H M DEITEL P J 2017 311 Operações na fila De forma geral podese fazer as seguintes operações em uma fila criar a fila ou seja informar a capacidade no caso de implementação sequencial vetor enfileirar enqueue sendo o elemento um parâmetro nesta operação desenfileirar dequeue mostrar a fila todos os elementos verificar se a fila está vazia isEmpty verificar se a fila está cheia isFull implementação sequencial vetor obter o elemento na frente da fila sem removêlo peek e contar os nós para saber o tamanho da fila size A partir das operações realizadas toda informação que chega à fila é adicionada ao seu fim e toda informação a ser consumida pelo recurso é retirada do início da fila 312 Implementação de fila Existem duas maneiras de implementar a fila com alocação sequencial e com alocação de lista encadeada Na alocação sequencial a fila pode ser implementada usando um vetor Neste caso é necessário construir um registro que contenha as informações da fila e cada um dos elementos da fila será representado por uma posição no vetor Nessa implementação segundo Bianchi 2014 devese ter atenção para estipular um tamanho para o vetor quantidade máxima de informações guardadas nele verificar se não chegou ao final do vetor ou seja se não o estourou 30052023 0004 Unidade 3 Estrutura de dados com orientação a objetos httpsambienteacademicocombrmodurlviewphpid784410 532 ter duas variáveis início e fim para controlar as posições do vetor onde estão essas posições a posição para a qual a variável início aponta tem a informação para ser consumida assim como a variável fim aponta para a última posição que tenha informação armazenada Uma fila estática é definida antecipadamente e a definição da fila persiste no ambiente É implementada com um array para que todas as operações da fila sejam baseadas em índice o que torna mais rápidas todas as operações exceto a exclusão pois requer o deslocamento de todos os elementos restantes para a frente em uma posição Observe o exemplo de aplicação de fila estática import javautil classe para criação da fila class Fila private int arr array para armazenar os elementos da fila private int inicio ponteiros de início para o início da fila private int fim ponteiro finail que indica o último elemento da fila private int capacidade capacidade máxima da fila private int contar tamanho atual da fila construtor para inicializar a fila Fila int tamanho arr new inttamanho capacidade tamanho inicio 0 fim 1 contador 0 função para excluir elemento da fila public void dequeue 30052023 0004 Unidade 3 Estrutura de dados com orientação a objetos httpsambienteacademicocombrmodurlviewphpid784410 632 verifica se a fila está vazia if isEmpty SystemoutprintlnFila vazia Programa finalizado Systemexit1 SystemoutprintlnRemovendo arrinicio inicio inicio 1 capacidade operação matemática para garantir que o índice fique dentro do range permitido simulando uma lista circular para não ter que mexer na posição de todos os outros elementos é uma otimização contador função para incluir elemento na lista public void enqueue int item verifica se a fila está cheia if isFull SystemoutprintlnFila cheia Programa finalizado Systemexit1 SystemoutprintlnIncluindo item fim fim 1 capacidade operação matemática para garantir que o índice fica dentro do range permitido simulando uma lista circular para não ter que mexer na posição de todos os outros elementos é uma otimização arrfim item contador função para retornar o elemento do início da fila public int peek if isEmpty 30052023 0004 Unidade 3 Estrutura de dados com orientação a objetos httpsambienteacademicocombrmodurlviewphpid784410 732 SystemoutprintlnVazia Programa Finalizado Systemexit1 return arrinicio função para retornar o tamanho da fila public int size return contador função para verificar se a fila está vazia ou não public Boolean isEmpty return size 0 função para verificar se a fila está cheia ou não public Boolean isFull return size capacidade implementação da fila em Java após a definição da classe Fila e de suas operações e atributos específicos desta forma na classe Fila foram declarados os métodos para enfileirar desenfileirar recuperar o primeiro elemento e verificar o tamanho da fila public static void main String args cria uma fila com 5 elementos Fila q new Fila5 cria uma fila chamada q com capacidade de 5 elementos qenqueue1 insere os valores de 1 a 3 com o método enqueue qenqueue2 qenqueue3 SystemoutprintlnO elemento do início é qpeek mostra o primeiro elemento qdequeue remove elemento do início da fila SystemoutprintlnO elemento do início é qpeek mostra o primeiro elemento 30052023 0004 Unidade 3 Estrutura de dados com orientação a objetos httpsambienteacademicocombrmodurlviewphpid784410 832 que agora é o 2 SystemoutprintlnO tamanho da fila é qsize apresenta o tamanho da fila qdequeue remove do início da fila ou seja o 2 qdequeue remove do início da fila ou seja o 3 if qisEmpty verifica se a lista está vazia e neste caso está vazia SystemoutprintlnA fila está vazia else SystemoutprintlnA fila não está vazia Já na alocação dinâmica uma fila pode ser facilmente implementada usando uma lista encadeada É essa estrutura que confere dinamicidade para a fila Na implementação de lista simplesmente encadeada o enfileiramento acontece no final da lista e o desenfileiramento dos elementos ocorre no início da lista Uma lista duplamente encadeada oferece inserção e exclusão em ambas as extremidades e pode ser usada caso se deseje que o enfileiramento ocorra no início e o desenfileiramento ocorra no final da lista encadeada Podese adicionar um elemento em qualquer lugar da lista alterar um elemento em qualquer lugar da lista ou remover um elemento de qualquer posição na lista Observe a implementação da fila com uma lista encadeada import javautil Classe para criação do nó da lista encadeada class No int dado inteiro dado No próximo ponteiro para o próximo nó public Noint dado coloca dado no nó alocado e retorna o nó 30052023 0004 Unidade 3 Estrutura de dados com orientação a objetos httpsambienteacademicocombrmodurlviewphpid784410 932 thisdado dado thisproximo null class Fila declaração da classe Fila com seus atributos e métodos que serão manipulados na classe main private static No fim null inicio null Função para remover o elemento da frente da fila public static int dequeue exclui no início if inicio null Systemoutprint Fila vazia Systemexit1 No temp inicio SystemoutprintfExcluindo d tempdado avança para o próximo nó início inicio inicioproximo se a lista ficar vazia if inicio null fim null desalocar memória do nó removido e opcionalmente retornar o item removido int item tempdado return item Função para incluir um item na fila public static void enqueueint item inclusão no fim 30052023 0004 Unidade 3 Estrutura de dados com orientação a objetos httpsambienteacademicocombrmodurlviewphpid784410 1032 Aloca um novo nó no heap No no new Noitem SystemoutprintfIncluindo d item caso especial fila vazia if inicio null inicializa início e fim inicio no fim no else atualiza fim fimproximo no fim no Função para retornar o elemento do início da fila na frente da fila public static int peek verifica se a lista está vazia if inicio null return iniciodado else Systemexit1 return 1 função para verificar se a fila está vazia ou não public static boolean isEmpty return fim null inicio null Implementação da fila em Java após definição da classe Fila e suas operações e atributos específicos neste programa como a fila é implementada com lista encadeada a classe nó foi 30052023 0004 Unidade 3 Estrutura de dados com orientação a objetos httpsambienteacademicocombrmodurlviewphpid784410 1132 criada para manipulação dos ponteiros da estrutura a classe Fila foi definida com funções para enfileirar desenfileirar verificar o elemento da frente e verificar se a fila está vazia esta estrutura representa a implementação FIFO FirstIn FirstOut public static void mainString args Fila q new Fila cria uma fila chamada q qenqueue1 insere os valores de 1 a 4 com o método enqueue qenqueue2 qenqueue3 qenqueue4 SystemoutprintfElemento do inicio é d qpeek mostra o primeiro elemento qdequeue remove do início da fila ou seja 1 qdequeue remove do início da fila ou seja 2 qdequeue remove do início da fila ou seja 3 qdequeue remove do início da fila ou seja 4 if qisEmpty verifica se a lista está vazia e está vazia SystemoutprintA fila está vazia else SystemoutprintA fila não está vazia VAMOS PRATICAR 30052023 0004 Unidade 3 Estrutura de dados com orientação a objetos httpsambienteacademicocombrmodurlviewphpid784410 1232 Para conhecer um pouco mais sobre a teoria das filas acesse o conteúdo disponível em httpwikiinfufprbrmazierodokuphp idsobibliotecadefilas e assista ao vídeo comentado sobre o projeto proposto Aproveite e acesse também os simuladores de fila existentes httpstranslategooglecomtranslate slentlptuhttpsqueueingsystemsenslyonfr Após isso elabore um código com filas de acordo com os conceitos aprendidos 313 Filas de prioridade Filas de prioridade são uma extensão da fila em que cada item tem uma prioridade associada a ele e onde um elemento com alta prioridade é retirado da fila antes de um elemento com baixa prioridade Neste tipo de fila se dois elementos tiverem a mesma prioridade eles serão atendidos de acordo com sua ordem na fila Ela pode ser implementada utilizandose um array ou uma lista encadeada de forma que as características relacionadas à performance de todas as operações são semelhantes à implementação com a array A vantagem da lista encadeada é que a exclusão pode ser mais eficiente pois não é necessário mover itens Outra forma de se implementar as filas de prioridade é através do heap que é geralmente o tipo de implementação preferida porque fornece melhor desempenho em comparação com arrays ou listas encadeadas Dicas de como se tornar um desenvolvedor melhor 30052023 0004 Unidade 3 Estrutura de dados com orientação a objetos httpsambienteacademicocombrmodurlviewphpid784410 1332 Fonte Elaborado pela autora 2020 Teste seus conhecimentos Atividade não pontuada 32 Pilha em estrutura estática e dinâmica Na ciência da computação as pilhas são uma das estruturas de dados mais populares e mais fáceis de aprender mas dependendo de como seus conceitos são apresentados podem parecer de pouca utilidade De forma semelhante ao que ocorre nas filas as pilhas também são uma lista na qual é aplicada uma disciplina de acesso antagônica chamada UEPS onde o último que entra é primeiro que sai LIFO Last in First Out Isto significa que qualquer elemento que entrar na pilha somente sairá quando todos os que entraram depois dele saíram Portanto pilha é uma lista na qual todas as inclusões e exclusões de elementos são feitas no final e possui como finalidade tornar disponíveis os 30052023 0004 Unidade 3 Estrutura de dados com orientação a objetos httpsambienteacademicocombrmodurlviewphpid784410 1432 elementos mais recentes FORBELLONE EBERSPACHER 2000 São blocos estruturantes para chamadas de funções e também para a implementação de funções recursivas que serão vistas mais adiante Veja a representação de uma pilha na Figura 2 Figura 2 Representação de uma pilha Fonte Elaborada pela autora 2020 Cada vez que uma função é chamada parte da memória é reservada para ela na pilha de chamadas e quando ela retorna a memória é desalocada Todas as ações executadas em um computador são colocadas em uma pilha e sempre que se desfaz algo a ação mais recente é interrompida A quantidade de undos que se pode fazer é determinada pelo tamanho da pilha 30052023 0004 Unidade 3 Estrutura de dados com orientação a objetos httpsambienteacademicocombrmodurlviewphpid784410 1532 VOCÊ QUER LER Neves 2016 em seu artigo Pilha Estática Uma estrutura leve para sistemas embarcados discorre sobre a aplicação de pilhas estáticas como pequenas estruturas de dados estáticas e eficientes para uso em sistemas embarcados Para ler acesse httpswwwembarcadoscombrpilhaestaticasistemas embarcados As pilhas também são utilizadas em análise de expressões matemáticas para uso em calculadoras e para aumentar a eficiência de algoritmos que fazem uso da estrutura de dados das pilhas e suas propriedades 321 Operações na pilha As operações que ocorrem em uma pilha podem ser comparadas a uma pilha de pratos em um restaurante ou a um jogo com as cartas de um baralho De forma geral podese fazer as seguintes operações em uma pilha criação da pilha informar a capacidade no caso de implementação sequencial vetor empilhar push o elemento é o parâmetro nesta operação desempilhar pop mostrar o elemento no topo da pilha peek sem removêlo da pilha ou modificar a pilha de qualquer forma verificar se a pilha está vazia isEmpty verificar se a pilha está cheia isFull implementação sequencial vetor contar os nós para saber o tamanho da fila size Em uma pilha os elementos são manipulados em apenas umas das extremidades chamada de topo em oposição a outra extremidade que é chamada de base 30052023 0004 Unidade 3 Estrutura de dados com orientação a objetos httpsambienteacademicocombrmodurlviewphpid784410 1632 As abas a seguir trazem um resumo dos conceitos que englobam as operações com as pilhas Clique nas abas para saber mais sobre o assunto Fonte BIANCHI FREITAS JUNIOR 2014 322 Implementação de pilha Existem duas maneiras de implementar a pilha através de vetor a alocação do espaço de memória para os elementos é contígua ou através de listas encadeadas Na estrutura estática vetor a pilha é uma variante que utiliza da alocação estática para reservar a memória que será utilizada para armazenar dados ou seja não é necessário o uso de funções para reservar memória durante a execução Toda a memória utilizada pela estrutura será reservada em tempo de compilação Uma pilha pode ser facilmente implementada como um array Observe o exemplo a seguir de implementação da pilha com um vetor import javautil class Pilha definição da classe Pilha com seus atributos e métodos que serão manipulados na classe main private int arr guarda a representação interna dos valores private int topo indica qual índice é o topo da pilha private int capacidade capacidade máxima da pilha construtor para inicializar a pilha Pilha int tamanho arr new inttamanho capacidade tamanho topo 1 PUSH POP PEEK isFull isEmpty 30052023 0004 Unidade 3 Estrutura de dados com orientação a objetos httpsambienteacademicocombrmodurlviewphpid784410 1732 função para adicionar um elemento na pilha public void pushint x if isFull SystemoutprintlnPilha cheia Programa finalizado Systemexit1 SystemoutprintlnIncluindo x arrtopo x função para excluir um elemento do topo da pilha public int pop verificar se a pilha está vazia if isEmpty SystemoutprintlnVazia Programa finalizado Systemexit1 SystemoutprintlnExcluindo peek reduz o tamanho da pilha em 1 e opcionalmente retorna o elemento excluído return arrtopo função para retornar o elemento no topo da pilha public int peek if isEmpty return arrtopo else Systemexit1 return 1 função para retornar o tamanho da pilha 30052023 0004 Unidade 3 Estrutura de dados com orientação a objetos httpsambienteacademicocombrmodurlviewphpid784410 1832 public int size return topo 1 função para verificar se a pilha está vazia ou não public Boolean isEmpty return topo 1 ou retorna size 0 função para verificar se a pilha está cheia ou não public Boolean isFull return topo capacidade 1 ou retorna size capacidade implementação da pilha em Java após definição da classe Pilha suas operações e seus atributos específicos com um vetor ou seja de forma estática neste programa como a pilha é implementada com um vetor a classe Pilha foi definida com funções para incluir excluir verificar primeiro elemento da da frente verificar se a pilha está vazia verificar se a pilha está cheia esta estrutura representa a implementação FILO FirstIn LastOut public static void main String args Pilha pilha new Pilha3 definição da pilha com um array interno de 3 elementos e topo 1 pilhapush1 incluindo 1 na pilha pilhapush2 incluindo 2 na pilha pilhapop removendo o topo 2 pilhapop removendo o topo 1 pilhapush3 inserindo 3 na pilha SystemoutprintlnO elemento do topo é pilhapeek o elemento do topo é 3 SystemoutprintlnO tamanho da pilha é pilhasize o tamanho da pilha é 1 pilhapop removendo o topo 3 30052023 0004 Unidade 3 Estrutura de dados com orientação a objetos httpsambienteacademicocombrmodurlviewphpid784410 1932 verifica se a pilha está vazia if pilhaisEmpty SystemoutprintlnA pilha está vazia a pilha está vazia else SystemoutprintlnA pilha não está vazia Uma pilha pode também ser facilmente implementada por meio de uma lista encadeada Na implementação por lista encadeada a pilha se torna um ponteiro para o topo da lista em que as operações push e pop acontecem no início da lista com um contador para controlar o tamanho da lista VOCÊ QUER LER As pilhas são usadas como parte da solução de um relevante tópico em ciência da computação a análise de expressões matemáticas principalmente porque essa análise pode fazer parte de um compilador de linguagem aumentando ainda mais sua importância São utilizadas também nos sistemas operacionais das máquinas empilhando a chamada das funções Caso queira aprofundar o estudo das diversas formas de usar as pilhas para manipular expressões matemáticas leia o Capítulo 2 do livro Estrutura de dados usando C Tenenbaum 2004 A vantagem de usar lista encadeada em vez de vetores é que é possível implementar uma pilha que pode aumentar ou diminuir tanto quanto necessário O uso de array irá colocar uma restrição à capacidade máxima do array o que pode levar ao empilhamento A implementação com listas encadeadas permite que cada novo nó seja alocado dinamicamente portanto a sobrecarga não será possível a menos que a memória se esgote Acompanhe a implementação da pilha com uma lista encadeada import javautil declaração do nó de uma lista encadeada 30052023 0004 Unidade 3 Estrutura de dados com orientação a objetos httpsambienteacademicocombrmodurlviewphpid784410 2032 class No classe nó int dado dado inteiro No proximo ponteiro para o próximo nó class Pilha private No topo public Pilha thistopo null função para adicionar o elemento no topo da pilha public void pushint x inclui no inicio aloca um novo nó No no new No verifica se a pilha está cheia se inserir um elemento pode causar o estouro da pilha if no null Systemoutprint Pilha estourou return SystemoutprintlnIncluindo x insere o dado no nó previamente alocado nodado x define o próximo ponteiro do novo nó para apontar para o nó superior atual da lista noproximo topo atualiza o ponteiro do topo topo no função para verificar se a pilha está vazia ou não public boolean isEmpty 30052023 0004 Unidade 3 Estrutura de dados com orientação a objetos httpsambienteacademicocombrmodurlviewphpid784410 2132 return topo null função para retornar o elemento do topo da lista public int peek verifica se a pilha está vazia if isEmpty return topodado else SystemoutprintlnA pilha está vazia return 1 função para remover o elemento no topo da lista public void pop remove do início verifique se há estouro negativo da pilha if topo null Systemoutprint Estouro negativo return SystemoutprintlnExcluindo peek atualiza o ponteiro do topo para o ponteiro do próximo nó topo topoproximo implementação da pilha em Java após definição da classe nó para manutenção dos ponteiros para a implementação da lista encadeada ou seja de forma dinâmica a classe Pilha foi definida com funções para incluir excluir verificar primeiro elemento da frente verificar se a pilha está vazia 30052023 0004 Unidade 3 Estrutura de dados com orientação a objetos httpsambienteacademicocombrmodurlviewphpid784410 2232 esta estrutura representa a implementação FILO FirstIn LastOut class Main public static void mainString args Pilha pilha new Pilha definição da pilha sem tamanho definido e topo 1 pilhapush1 Incluindo 1 na pilha pilhapush2 Incluindo 2 na pilha pilhapush3 Incluindo 3 na pilha SystemoutprintlnO elemento do topo é pilhapeek apresenta o elemento 3 no topo da pilha e o elemento 1 como primeiro elemento da pilha pilhapop exclui o elemento do topo que é 3 pilhapop exclui o elemento do topo que é 2 pilhapop exclui o elemento do topo que é 1 if pilhaisEmpty verifica se a pilha está vazia SystemoutprintA pilha está vazia a pilha está vazia else SystemoutprintA pilha não está vazia Nos cards a seguir há um resumo dos conceitos técnicos sobre fila e suas informações assim como sobre pilhas e métodos Papo técnico Clique nas setas ou arraste para visualizar o conteúdo Existem vários recursos computacionais que são compartilhados como processador e sockets e os conceitos de fila são usados para controlar sua utilização Toda informação que chega à fila é adicionada no FIM toda informação a ser consumida pelo recurso é retirada do INÍCIO da 30052023 0004 Unidade 3 Estrutura de dados com orientação a objetos httpsambienteacademicocombrmodurlviewphpid784410 2332 Fonte BIANCHI FREITAS JUNIOR 2014 33 Recursividade Os programas que discutimos até aqui em geral são estruturados como métodos que chamam uns aos outros de uma maneira hierárquica Para alguns problemas é útil um método chamar a si próprio Algumas linguagens de programação permitem que um módulo ou função chame a si mesmo Essa técnica é conhecida como recursividade ou recursão Na recursão uma função α ou chama a si mesma diretamente ou chama uma função β que por sua vez chama a função original α A função α é chamada de função recursiva Assim um método que faz isso é conhecido como método recursivo que pode chamar a si próprio direta ou indiretamente por outro método DEITEL H M DEITEL P J 2017 Existem várias aplicações clássicas da recursividade na matemática como o cálculo de potências de números fatoriais na determinação do nésimo elemento da sequência de Fibonacci manipulação de árvores binárias entre outras aplicações toda informação a ser consumida pelo recurso é retirada do INÍCIO da fila Lembrese você SEMPRE entra no fim da fila INFORMAÇÕES NA FILA As filas são comumente chamadas de filas FIFO firstin firstout o primeiro a entrar é o primeiro a sair A informação colocada na fila pode ser qualquer tipo primitivo disponível ou abstrato criado no seu programa PILHAS E MÉTODOS Quando em um código de programa uma chamada de método operação é realizada o método chamado deve saber o que retornar para o elemento que o chamou de forma que o endereço de retorno seja inserido na pilha de execução do programa Se ocorrer uma série de chamadas de método os sucessivos valores de retorno são colocados na pilha na ordem último a entrarprimeiro a sair FILO 30052023 0004 Unidade 3 Estrutura de dados com orientação a objetos httpsambienteacademicocombrmodurlviewphpid784410 2432 A recursividade ou recursão é uma técnica de resolução de problemas que envolve dividir um problema em instâncias menores do mesmo problema também chamadas de subproblemas até que se obtenha um subproblema pequeno o suficiente e que tenha uma solução trivial Bianchi Freitas e Junior explicam o potencial da recursividade O grande potencial da recursão está na possibilidade de poder definir elementos com base em versões mais simples desses mesmos elementos Em termos computacionais tratase de dividir um problema maior em problemas menores em que a resolução é feita por uma mesma função ou método que é recorrentemente chamada Muitos autores chamam essa técnica computacional de dividir para conquistar parafraseando o grande imperador francês Napoleão Bonaparte BIANCHI FREITAS JUNIOR 2014 p 41 Podese dizer que a recursão é a definição de um problema em termos de si mesmo pois envolve uma função que se chama com um caso base para encerrar o loop infinito É um conceito de extrema importância na ciência da computação e uma ferramenta muito poderosa para escrever algoritmos permitindo escrever soluções muito elegantes para problemas que de outra forma poderiam ser muito difíceis de se implementar iterativamente 331 Implementação da recursividade Uma função recursiva pode ser infinita como um loop Para evitar a execução infinita dessa função recursiva existem duas propriedades que devem ser observadas segundo Bianchi et al 2014 Critérios de base deve haver pelo menos um critério ou condição de base de modo que quando essa condição for atendida a função pare de chamar a si mesma recursivamente Geralmente essa condição estabelece uma solução trivial ou um evento que encerra a autochamada consecutiva Abordagem progressiva as chamadas recursivas devem progredir de tal forma que cada vez que uma chamada recursiva seja feita ela se aproxime dos critérios 30052023 0004 Unidade 3 Estrutura de dados com orientação a objetos httpsambienteacademicocombrmodurlviewphpid784410 2532 básicos Muitas linguagens de programação implementam a recursividade por meio de pilhas Geralmente sempre que uma função chamador chama outra função receptor ou a si mesma como receptor a função do chamador transfere o controle de execução para o receptor Esse processo de transferência também pode envolver alguns dados a serem passados do chamador para o receptor Isso implica que a função do chamador deve suspender sua execução temporariamente e retomar mais tarde quando o controle de execução retornar da função do receptor Aqui a função do chamador precisa começar exatamente do ponto de execução onde ela se coloca em espera Ele também precisa dos mesmos valores de dados exatos nos quais estava trabalhando Para tanto é criado um registro de ativação para a função do chamador Observe um exemplo de recursividade Implementação simples de recursividade class Fatorial static int factorial int n if n 0 condição de término return n factorialn1 chamada recursiva else return 1 public static void mainString args int numero 4 resultado resultado factorialnumero Systemoutprintlnnumero fatorial resultado No exemplo acima temos um método denominado factorial O factorial é chamado a partir do método main com a variável numérica passada como argumento O método 30052023 0004 Unidade 3 Estrutura de dados com orientação a objetos httpsambienteacademicocombrmodurlviewphpid784410 2632 factorial está chamando a si mesmo Inicialmente o valor de n é 4 dentro do factorial Durante a próxima chamada recursiva 3 é passado para o método factorial Este processo continua até que n seja igual a 0 Quando n é igual a 0 a instrução if retorna falso portanto 1 é retornado Finalmente o resultado acumulado é passado para o método main Um mecanismo bastante conhecido para a implementação de uma função recursiva é a pilha de execução Neste tipo de implementação quando uma função é chamada no programa um espaço de memória é reservado pelo sistema operacional para variáveis e parâmetros desta função Assim a função em execução no momento da chamada encontrase no topo da pilha e quando finalizada é removida da pilha Esse comportamento se repete a cada nova chamada de função Para entender melhor observe o exemplo da Figura 3 para calcular o expoente de 4 PraCegoVer quatro ao cubo 3 30052023 0004 Unidade 3 Estrutura de dados com orientação a objetos httpsambienteacademicocombrmodurlviewphpid784410 2732 30052023 0004 Unidade 3 Estrutura de dados com orientação a objetos httpsambienteacademicocombrmodurlviewphpid784410 2832 Figura 3 Pilha de execução para recursividade Fonte Elaborado pela autora 2021 Percebese que à medida que esta sequência é demandada uma pilha com três elementos vai sendo preenchida de baixo para cima com os números É então iniciada a representação da função recursiva e assim que os valores são calculados os números desaparecem da pilha de cima para baixo representando a propriedade das pilhas FILO A última parte do esquema apresenta o cálculo final da exponenciação 64 e a pilha vazia Dicas de programação Clique nas setas ou arraste para visualizar o conteúdo de lógica conhecido como recursão infinita em que as chamadas recursivas são feitas continuamente até a memória esgotar ou o acúmulo de chamadas de métodos estourar Esse erro é análogo ao problema de um loop infinito em uma solução iterativa não recursiva ALOCAÇÃO DINÂMICA DE MEMÓRIA O limite para alocação dinâmica de memória pode ser tão grande quanto a memória física disponível no computador ou o espaço em disco disponível em um sistema de memória virtual Frequentemente os limites são bem menores porque a memória disponível do computador deve ser compartilhada entre muitos usuários DESEMPENHO Evite programas recursivos no estilo Fibonacci porque resultam em uma explosão exponencial de chamadas de método e também evite utilizar a recursão em situações que requerem alto desempenho Chamadas recursivas levam tempo e consomem memória adicional ITERATIVIDADE VERSUS RECURSIVIDADE Qualquer problema que possa ser resolvido recursivamente também pode ser resolvido iterativamente Uma abordagem recursiva em geral é f id b it ti d i i lh i 30052023 0004 Unidade 3 Estrutura de dados com orientação a objetos httpsambienteacademicocombrmodurlviewphpid784410 2932 Fonte DEITEL H M DEITEL P J 2017 Praticamente todas as funções recursivas podem ser convertidas para funções iterativas A condição de parada utilizada na versão recursiva pode ser aproveitada em uma estrutura de repetição na versão iterativa É interessante observar que a implementação iterativa tende a ser na prática mais rápida que implementação recursiva pois esta registra o estado atual do processamento para que ela possa continuar de onde parou após a conclusão de cada nova execução subordinada do procedimento recursivo o que consome tempo e memória É importante por fim entender que escolher um algoritmo iterativo ao invés de um algoritmo recursivo pode ser justificado pois o espaço disponível para o fluxo de controle é menor que o espaço disponível na pilha e algoritmos recursivos tendem a necessitar de mais espaço na pilha do que algoritmos iterativos Teste seus conhecimentos Atividade não pontuada é preferida sobre uma iterativa quando a primeira espelha mais naturalmente o problema e resulta em um programa mais fácil de entender e depurar Uma abordagem recursiva pode ser com frequência implementada com menos linhas de código Outra razão de escolher uma abordagem recursiva é que uma iterativa talvez não seja aparente 30052023 0004 Unidade 3 Estrutura de dados com orientação a objetos httpsambienteacademicocombrmodurlviewphpid784410 3032 Síntese Neste capítulo foram apresentados os principais conceitos relacionados às filas e pilhas em estruturas estáticas e estruturas dinâmicas de dados e também sobre recursividade ou recursão Foram discutidas suas diferenças e similaridades com outras estruturas de dados já estudadas assim como as possíveis operações para cada uma dessas estruturas aplicações reais e formas de implementação dos algoritmos em Java Na sequência o tema recursividade foi abordado enfatizando suas características aplicações reais e formas de implementação na linguagem Java Exemplos foram discutidos e foi apresentada sua importância para a área de ciências da computação Além disso pudemos recordar algumas estruturas já vistas anteriormente e aprender algumas dicas de programação em Java SAIBA MAIS Título Java como Programar Autores Paul Deitel e Harvey Deitel Ano 2017 Comentário Leia o capítulo 18 Recursão do livro pois ele complementa de forma didática o conteúdo disponibilizado no material de apoio Neste capítulo são apresentadas as diferenças entre recursão e iteração e quando usar cada uma delas Onde encontrar Biblioteca virtual da 30052023 0004 Unidade 3 Estrutura de dados com orientação a objetos httpsambienteacademicocombrmodurlviewphpid784410 3132 Título Recursividade em JAVA Autor Ricardo Alves Ano 2020 Comentário Leia este artigo pois ele complementa de forma didática o conteúdo disponibilizado no material de apoio Onde encontrar httpwwwlinhadecodigocombrartigo3316recursividadeemjavaaspx Referências bibliográficas 30052023 0004 Unidade 3 Estrutura de dados com orientação a objetos httpsambienteacademicocombrmodurlviewphpid784410 3232 BIANCHI F FREITAS R JUNIOR D Estrutura de dados e técnicas de programação São Paulo Elsevier Brasil 2014 DEITEL H M DEITEL P J Java como programar São Paulo Pearson 2017 FORBELLONE A L V EBERSPACHER H F Lógica de programação São Paulo Makron Books 2000 NEVES F Pilha estática uma estrutura leve para sistemas embarcados Embarcados s l 2016 Disponível em httpswwwembarcadoscombrpilhaestaticasistemas embarcados Acesso em 16 jan 2021 PUGA S RISSETTI G Lógica de Programação e Estrutura de Dados com aplicações em Java São Paulo Pearson 2004 TENENBAUM A M Estruturas de dados usando C São Paulo Makron Books 2004