Baixe o app para aproveitar ainda mais
Prévia do material em texto
1 Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Recursividade Recursividade • Introdução – Conceitos Básicos • A Função Recursiva e o “Critério de Saída” • Exemplos Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Recursividade Bibliografia • MANZANO, José Augusto N. G.; OLIVEIRA, Jayr F. – Algoritmos: Lógica para Desenvolvimento de Programação • CORMEN, Thomas H. et al. – Algoritmos: Teoria e Prática • DEITEL & DEITEL – C# - Como Programar – 2003 • PREISS, Bruno – Estruturas de dados e algoritmos. Rio de Janeiro: Campus, 2001. 584p. • SZWARCFITER, Jayme Luiz; MARKENZON, Lilian – Estruturas de dados e seus Algoritmos • VILLAS, Marcos Vianna; VILLASBOAS, Luiz Felipe P. – Programação – Conceitos, Técnicas e Linguagens. Rio de Janeiro: Campus, 1988. 196p. • MCDONALD, Matthew – Begining ASP.NET 4 in C# 2010 – Apress – 2010 • MCMILLAN, Michael – Data Structures and Algorithms Using C# – Cambridge University Press – 2007 • Stellman & Greene – C# - Use a Cabeça – 2ª Edição – 2011 • Material de Aula – Algoritmos e Técnicas de Programação – Aluísio Eustáquio da Silva – 2012 2 Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Recursividade Recursividade Introdução – Conceitos Básicos Recursividade é um termo usado para descrever uma função (ou rotina, ou método) que pode chamar a si mesma. É um recurso computacional bastante sofisticado que pode simplificar muito um problema computacional. A Função Recursiva chama a si mesma, geralmente utilizando parâmetros similares. Cada chamada implica em uma nova instância da função e de todas as variáveis utilizadas. static int Fatorial(int x) { ... Fat = x * Fatorial(x - 1); ... return (Fat); } Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Recursividade Recursividade Introdução – Conceitos Básicos Uma chamada recursiva pode ser direta, a mais comum, ou indireta, quando uma função A chama outra função B e esta chama novamente a função A. O controle sobre esse tipo de chamada deve ser rigoroso para se evitarem erros, que são difíceis de serem identificados. Internamente, quando uma chamada recursiva é feita, é criado um Registro de Ativação na Pilha de Execução do Programa. Esse Registro de Ativação armazena os parâmetros e variáveis locais da função, assim como o “ponto de retorno” no programa que chamou a função. Ao final da execução da função o registro é desempilhado e a execução volta ao programa que inicialmente chamou a função. 3 Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Recursividade Recursividade Chamadas e Retornos Exemplo: Fatorial (4) x = 4 Fat = 4 * Fatorial (3) x = 3 Fat = 3 * Fatorial (2) x = 2 Fat = 2 * Fatorial (1) x = 1 Fat = 1 * Fatorial (0) x = 0 Fat = 1 static int Fatorial(int x) { int Fat; if (x == 0) Fat = 1; else Fat = x * Fatorial(x - 1); return (Fat); } 1 1 2 6 24 Fatorial (4) = 24 Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Recursividade Recursividade Critérios de Saída – Condição de Parada Toda Função Recursiva precisa possuir um Critério de Saída ou Condição de Parada, uma forma de terminar a execução da função. Se isso não existir as chamadas ocorrerão de forma indefinida. Um Critério de Saída normalmente é chamado de Caso Base, uma condição em que o problema pode ser facilmente resolvido. static int Fatorial(int x) { int Fat; if (x == 0) Fat = 1; else Fat = x * Fatorial(x - 1); return (Fat); } 4 Pontifícia Universidade Católica de Minas Gerais Curso de Sistemas de Informação Algoritmos e Estruturas de Dados Recursividade Exercícios em C#
Compartilhar