Recursividade em Codigos de Alta Performance - Guia e Exemplos

1 Recursividade Códigos de Alta Performance PROFa PATRÍCIA MAGNA profpatriciamagnafiapcombr 2 Recursividade Recursividade é um termo usado de maneira mais geral para descrever o processo de repetição de um objeto de um jeito similar ao que já fora mostrado Um bom exemplo disso são as imagens repetidas que aparecem quando dois espelhos são apontados um para o outro httpsptwikipediaorgwikiRecursividade Recursividade 4 Aplicação de Recursividade em Programação Alguns problemas têm como propriedade de ter sua solução facilitada a cada instância menor do mesmo problema Dizse que esses problemas possuem uma estrutura recursiva A resolução desse tipo de problema baseiase na aplicação do seguinte método 1 se a instância em questão for pequena resolvaa diretamente 2 Senão reduzaa a uma instância menor do mesmo problema aplique o método à instância menor volte à instância original A aplicação desse método produz um algoritmo recursivo 5 Aplicação de Recursividade em Programação Algoritmo recursivos são normalmente implementados usando funções recursivas ou métodos recursivos Uma função é dita recursiva quando ela chama a ela mesma para resolver um determinado problema Passando para a função chamada uma instância menor do problema Um exemplo de uso de recursividade é o percurso de todos os nós de uma árvore veremos daqui a pouco Definição Matemática da Função Fatorial n n n1 se n 0 1 caso contrário Aplicação da Função Fatorial n4 4 4 3 3 3 2 2 2 1 1 1 0 0 1 n n n1 se n 0 1 caso contrário Implementação Recursiva da Função Fatorial public static void mainString args int fat fat fatorial 4 SystemoutprintlnFatorial fat public static int fatorial int n if n 0 return n fatorial n1 else return 1 Ativação 1 n 4 return 4 fatorial 3 Ativação 1 n 4 4 fatorial 3 Ativação 2 n 3 return 3 fatorial 2 Ativação 1 n 4 4 fatorial 3 Ativação 2 n 3 3 fatorial 2 Ativação 3 n 2 return 2 fatorial 1 Ativação 1 n 4 4 fatorial 3 Ativação 2 n 3 3 fatorial 2 Ativação 3 n 2 2 fatorial 1 Ativação 4 n 1 return 1 fatorial 0 Ativação 1 n 4 4 fatorial 3 Ativação 2 n 3 3 fatorial 2 Ativação 3 n 2 2 fatorial 1 Ativação 4 n 1 return 1 fatorial 0 Ativação 5 n 0 return 1 Ativação 1 n 4 4 fatorial 3 Ativação 2 n 3 3 fatorial 2 Ativação 3 n 2 2 fatorial 1 Ativação 4 1 n 1 return 1 fatorial 0 Ativação 1 n 4 4 fatorial 3 Ativação 2 n 3 3 fatorial 2 Ativação 3 1 n 2 return 2 fatorial 1 Ativação 1 n 4 4 fatorial 3 Ativação 2 2 n 3 return 3 fatorial 2 Ativação 1 6 n 4 return 4 fatorial 3 public static void mainString args int fat fat fatorial 4 SystemoutprintlnFatorial fat public static int fatorial int n if n 0 return n fatorial n1 else return 1 Implementação Recursiva da Função Fatorial 24 Outra Forma de Representar as ativações de função recursiva Função Recursiva Máximo Divisor Comum public static int mdcint n int m if n m returnmdcmn else if n 0 returnm else returnmdcn mn Chamada da Função MDC public static int mdcint n int m if n m returnmdcmn else if n 0 returnm else returnmdcnmn public static void mainString args int x mdc 84 Systemoutprintln MDC entre 8 e 4 x Ativação 1 n 8 m4 nm returnmdc48 Ativação 1 n 4 4 fatorial 3 Ativação 2 n4 e m8 nm e n20 returnmdc 4 84 Ativação 1 n 4 4 fatorial 3 Ativação 2 n4 e m8 nm e n20 returnmdc 40 Ativação 1 n 4 4 fatorial 3 Ativação 2 n 3 3 fatorial 2 Ativação 3 n 4 e m0 nm returnmdc 04 Ativação 1 n 4 4 fatorial 3 Ativação 2 n 3 3 fatorial 2 Ativação 3 n 2 2 fatorial 1 Ativação 4 n0 e m4 nm e n0 return 4 Ativação 1 n 4 4 fatorial 3 Ativação 2 n 3 3 fatorial 2 Ativação 3 4 n 4 e m0 nm returnmdc04 Ativação 1 n 4 4 fatorial 3 Ativação 2 4 n4 e m8 nm e n20 returnmdc4 0 Ativação 1 4 n8 e m4 nm returnmdc48 Chamada da Função MDC public static int mdcint n int m if n m returnmdcmn else if n 0 returnm else returnmdcnmn public static void mainString args int x mdc 84 Systemoutprintln MDC entre 8 e 4 x 4 Exercício 1 Ideia para Resolução de Exercício Exercício 2 public static void mainString args int x 25 Int y 2 apresentax y public static void apresentaint x int y if x0 apresentaxy y Systemoutprintxy Faça o teste de mesa da execução do programa a seguir Perguntas 1 Faça o teste de mesa alterando y para 8 2 Qual o objetivo do programa REFERÊNCIAS TENENBAUM AM E outros Estruturas de Dados usando C Makron Books do Brasil Editora Ltda SP PEREIRA S L Estrutura de Dados Fundamentais São Paulo Érica FORBELLONE ALV EBERSPÄCHER HF Lógica de Programação A Construção de Algoritmos e Estruturas de Dados Makron Books São Paulo SP ASCENCIOAFG e ARAÚJO GS Estruturas de Dados Algoritmos Análise da Complexidade e Implementação em JAVA e CC 34 Copyright 2024 Profa Patrícia Magna Todos direitos reservados Reprodução ou divulgação total ou parcial deste documento é expressamente proibido sem o consentimento formal por escrito dos professores