Recursividade em Programação

Prévia do material em texto

Estrutura de dadosEstrutura de dados
Recursividade Recursividade 
20132013
Prof Melo
Apresentação
• Técnico em Desenvolvimento de Sistemas - Ibratec, Recife-PE
• Bacharel em Sistemas de Informação – FIR, Recife-PE
• Especialista em Docência no Ensino Superior – Faculdade 
Maurício de Nassau, Recife-PE
• Mestre em Ciência da Computação – UFPE/CIN, Recife-PE
• Currículo Lattes http://lattes.cnpq.br/0759508594425296)
• Homepage https://sites.google.com/site/hildebertomelo/
Disciplinas Lecionadas
• Desenvolvimento de Aplicações Desktop
• Programação Orientada a Objetos
• Estrutura de Dados
• Tecnologia da Informação & Sociedade
• Sistemas Operacionais
• Sistemas Distribuídos
• Introdução a Informática
• Lógica de Programação
• Informática Aplicada a Saúde
• Banco de Dados
• Projeto de Banco de Dados
• Análise de Projetos Orientado a Objetos
• Programação Cliente Servidor
• Linguagens de Programação: C, C#, Pascal, PHP, ASP, Delphi, Java, JavaScript
• Programação WEB
Recursividade
• Na linguagem C, assim como em muitas outras 
linguagens de programação, uma função pode 
chamar a si própria. Uma função assim é
chamada função recursiva. Todo cuidado é pouco 
ao se fazer funções recursivas. A primeira coisa a 
se providenciar é um critério de parada. Este vai 
determinar quando a função deverá parar de 
chamar a si mesma. Isto impede que a função se 
chame infinitas vezes. 
Recursividade
• O processo recursivo é baseado na recorrência válida 
para essa sequência: todo termo é igaul à soma dos 
dois termos anteriores. É importante que um 
programa recursivo deve ter obrigatoriamente uma 
condição que controla sua execução ou término, sob 
pena de produzir uma computação interminável. No 
exemplo, o término da execução da função ocorre 
quando o parâmetro t é menor ou igual a 2, como 
cada chamada de Fi diminui o valor de t, o término 
está garantido.
Recursividade
• Um programa recursivo é mais elegante e 
menor que a sua versão iterativa, além de 
exibir com maior clareza o processo utilizado, 
desde que o problema ou dados sejam 
naturalmente definidos através da 
recorrência. Por outro lado, um programa 
recursivo exige mais espaço de memória e é
mais lento do que a versão iterativa.
Recursividade
• Vantagens
– Redução do tamanho do código fonte
– Permite descrever algoritmos de forma mais clara e 
concisa
• Desvantagens
– Redução do desempenho de execução devido ao tempo 
para gerenciamento de chamadas
– Dificuldades na depuração de programas recursivos, 
especialmente se a recursão for muito profunda
Recursividade
• Usa-se uma pilha para armazenar os dados 
usados em cada chamada de um 
procedimento / função que não terminou
• Todos os dados não globais são armazenados 
na pilha, informando o resultado corrente
• Quando uma ativação anterior prossegue, os 
dados da pilha são recuperados
• Uma função que calcule o fatorial de um número inteiro n é um bom 
exemplo de uma função recursiva: 
• #include <stdio.h> 
• int fat(int n) { 
– if (n > 1)
• return n*fat(n-1) 
– else 
• return 1; 
• } 
• int main() { 
– int n; 
– printf("\n\nDigite um valor para n: "); 
– scanf("%d", &n); //vamos supor que a entrada foi 4
– printf("\nO fatorial de %d e' %d", n, fat(n)); 
– return 0; 
• }
Resultado da Implementação
Fatorial := 3 * (Fatorial(2))
Fatorial := 4 * (Fatorial(3)) 
Fatorial := 2 * (Fatorial(1))
Fatorial := 1 * (Fatorial(0))
Fatorial := 1
1 Fatorial = 1
1 Fatorial = 2
2 Fatorial = 6
6 Fatorial = 24
Problema com terminação de 
Procedimentos Recursivos
• Procedimentos recursivos introduzem a possibilidade de 
iterações que podem não terminar: existe a necessidade de 
considerar o problema de terminação.
• É fundamental que a chamada recursiva a um procedimento 
P esteja sujeita a uma condição A, a qual se torna satisfeita 
em algum momento da computação.
– Ex.: Se não existisse a condição n=0, quando o procedimento 
terminaria?
• Condição de terminação
– Permite que o procedimento deixe de ser executado
– O procedimento deve ter pelo menos um caso básico para cada caso 
recursivo, o que significa a finalização do procedimento
Recursividade
• Um algoritmo recursivo tem que ter obrigatoriamente a condição 
de quebra da recursividade, senão o algoritmo vai entrar em loop
infinito.
• Ex:
– //errado
– void fatorial(int n){
• Return n * fatorial(n-1);
– }
– //certo
– void fatorial(int n){
• If(n <= 1)
• return 1
• Else
• Return n * fatorial(n-1);
– }
Dicas
• Não se aprende recursividade sem praticar
• Para montar um algoritmo recursivo
– Defina pelo menos um caso básico (condição de 
terminação);
– Quebre o problema em problemas menores, definindo 
o(s) caso(s) com recursão(ões)
– Fazer o teste de finitude, isto é, certificar-se de que as 
sucessivas chamadas recursivas levam obrigatoriamente, 
e numa quantidade finita de vezes, ao(s) caso(s) básico(s)
Finalizando
• Recursividade é um tópico fundamental
• Algoritmos recursivos aparecem bastante na prática
• Dividir e conquistar é uma técnica naturalmente 
recursiva para solução de problemas
• Mais recursividade no nosso futuro, principalmente 
na implementação de árvores...
Perguntas...
Bibliografia
• Livro(s) Texto(s):
• PREISS, Bruno R. Estrutura de Dados e 
Algoritmos. Rio de Janeiro: Campus, 2001.
• PEREIRA, Silvio L. Estruturas de dados 
fundamentais. São Paulo: Érica, 2000.
• AZEREDO, Paulo A. Métodos de Classificação 
de Dados e Análise de suas Complexidades. 
Rio de Janeiro: Campus, 1995.
• http://www.nuperc.unifacs.br/
Bibliografia
• Livros de referencia:
• WEISS, M. A. Data structures and algorithm analysis in 
C++. California: Benjamin/Cummings, 1999.
• SEDGEWICK, R. Algorithms in C++: Fundamentals, data 
structures, sorting, searching. New York: Addison-
Wesley, 2001.
• TANENBAUM, Aaron; LANGSAM, Y. & AUGENSTEIN, M. 
Estruturas de Dados usando C. São Paulo: Makron 
Books, 1995.
• LAFORE, R. Aprenda em 24 horas estrutura de dados e 
algoritmo. Rio de Janeiro: Campus, 1999.
• MORAES, Celso R. Estruturas de Dados e Algoritmos. 
São Paulo: Berkeley Brasil, 2001.