Recursividade em Sistemas de Informação: Conceitos e Exemplos

Sistemas de Informação ESPM Laboratório de Programação Prof Dr Antonio Marcos SELMINI antonioselminiespmbr Recursividade Sistemas de Informação ESPM Recursão Sistemas de Informação ESPM Recursão Repetições podem ser obtidas escrevendose laços como laços for ou laços while Outra forma de se obter repetição é por meio da recursão que ocorre quando uma função método chama a si mesma A recursão oferece uma alternativa elegante e poderosa para executar tarefas repetitivas Recursão é um conceito que define um método que chama a si mesmo Quando isso ocorre denominase chamada recursiva Também se considera como recursivo um método M se ele chama outro método que chama M de volta Sistemas de Informação ESPM Recursão O maior benefício da abordagem recursiva no projeto de algoritmos é que nos permite tirar vantagem da estrutura repetitiva presente em muitos problemas Com a recursão podese evitar a análise de casos complexos e o uso de laços aninhados Essa abordagem pode levar a descrições de algoritmos mais legíveis e ainda manter a eficiência O uso da recursão é útil para definir objetos que tenham uma estrutura repetitiva similar como nos exemplos que seguem Sistemas de Informação ESPM Exemplos de recursão Exemplo 1 Sistemas operacionais modernos definem os diretórios do sistema de arquivos também conhecidos como pastas de uma forma recursiva Na verdade um sistema de arquivos consiste em um diretório de mais alto nível e o conteúdo deste diretório compreende arquivos e outros diretórios que podem por sua vez conter arquivos e diretórios e assim por diante Os diretórios base de um sistema de arquivos contêm apenas arquivos mas usando esta definição recursiva o sistema operacional permite que os diretórios sejam aninhados em qualquer profundidade enquanto houver espaço na memória Goodrich Michael T Tamassia Roberto Estruturas de Dados e Algoritmos em Java Página 145 Edição do Kindle Sistemas de Informação ESPM Exemplos de recursão Exemplo 2 Existem vários exemplos de recursão na arte e na natureza Um dos exemplos mais clássicos de recursão usado na arte são as bonecas russas Matryoshka Cada boneca é feita de madeira sólida ou oca contendo outra boneca Matryoshka dentro de si Goodrich Michael T Tamassia Roberto Estruturas de Dados e Algoritmos em Java Página 145 Edição do Kindle Sistemas de Informação ESPM Recursão Um exemplo típico de recursão é o cálculo do fatorial de um número Dado um número n inteiro e positivo o fatorial de n é dado por n 1 2 3 n1 n else f n n n f n 1 0 if 1 Sistemas de Informação ESPM Recursão public static int fatorialRecursivoint n método recursivo ifn 0 caso base return 1 else return n fatorialRecursivon1 caso recursivo public static int fatorialint n int fat 1 whilen 1 fat fat n n return fat versão não recursiva do cálculo do fatorial Sistemas de Informação ESPM Recursão fatorialRecursivo4 retorna 4 6 24 chamada fatorialRecursivo3 chamada retorna 3 2 6 fatorialRecursivo2 chamada retorna 2 1 2 fatorialRecursivo1 chamada retorna 1 1 1 fatorialRecursivo0 chamada retorna 1 Sistemas de Informação ESPM Recursão Soma dos elementos de um array de forma recursiva private static int somaVetorint v int n ifn 1 return v0 else return vn1somaVetorv n1 Sistemas de Informação ESPM Exercício 1 O que é retornado em cada uma das chamadas para os métodos abaixo public static int metodo1int x ifx 1 return x return 5 metodo1x 1 x a metodo11 b metodo13 public static int metodo2int n ifn 1 return 1 return n 1 metodo2n 1 a metodo22 b metodo23 c metodo20 Sistemas de Informação ESPM Exercício de programação 2 Escreva um método recursivo que calcule o valor de xn O valor de n deve ser maior ou igual a 0 3 Escreva um método recursivo que retorne a soma dos elementos de um array 4 Escreva um método recursivo que determine quantas vezes um dígito aparece em um número inteiro 5 Escreva um método recursivo que imprima no vídeo a correspondência em binário de um valor inteiro dado na base decimal 6 Escreva um método recursivo para calcular e retornar o nésimo termo da sequência de Fibonacci Sistemas de Informação ESPM Bibliografia CORNELL G HORSTMANN C A Y S Core Java Volume 1 Fundamentos 8ª ed Editora Pearson 2010 DEITEL H DEITEL P Java Como Programar 10ª ed Editora Pearson 2010 13 Sistemas de Informação ESPM Bibliografia COELHO A Java com orientação a objetos 1ª ed Editora LCM 2012 14