Buscar

608674_AED (3) - Recursividade

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#

Outros materiais

Materiais relacionados

Perguntas relacionadas

Materiais recentes

Perguntas Recentes