Computação Básica - Recursividade

Prévia do material em texto

Departamento de Ciência da ComputaçãoDepartamento de Ciência da Computação
Universidade Universidade de de BrasíliaBrasília
Computação BásicaComputação Básica
COMPUTAÇÃO BÁSICA
Recursividade
Prof. Bruno Macchiavello (bruno@cic.unb.br)
Universidade de Brasília – UnB 
Instituto de Ciências Exatas – IE 
Departamento de Ciência da Computação – CIC 
Prof. Bruno Macchiavello 1
Departamento de Ciência da ComputaçãoDepartamento de Ciência da Computação
Universidade Universidade de de BrasíliaBrasília
Computação BásicaComputação Básica
Introdução
• Após termos trabalhado com funções vocês já 
devem ter se perguntado: 
Posso chamar uma função 
• Este técnica se chama RECURSIVIDADE, e
muitas vezes ela facilita a interpretação de 
certos problemas.
Prof. Bruno Macchiavello 2
Posso chamar uma função 
dentro dela mesma? SIM
Departamento de Ciência da ComputaçãoDepartamento de Ciência da Computação
Universidade Universidade de de BrasíliaBrasília
Computação BásicaComputação Básica
Conceito de Recursividade
• Um programa recursivo é um programa que chama
a si mesmo.
• Vantagens
� Redução do tamanho do código fonte
� Permite descrever algoritmos de forma mais clara e� 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
Prof. Bruno Macchiavello 3
Departamento de Ciência da ComputaçãoDepartamento de Ciência da Computação
Universidade Universidade de de BrasíliaBrasília
Computação BásicaComputação Básica
Conceito de Recursividade
• Em geral, uma rotina recursiva R pode ser
expressa como uma composição formada por
um conjunto de comandos C (que não contem
chamadas a R) e uma chamada (recursiva) à R.
Prof. Bruno Macchiavello 4
R ≡ [C, R]
Departamento de Ciência da ComputaçãoDepartamento de Ciência da Computação
Universidade Universidade de de BrasíliaBrasília
Computação BásicaComputação Básica
Condição de Parada
• 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.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
Prof. Bruno Macchiavello 5
Departamento de Ciência da ComputaçãoDepartamento de Ciência da Computação
Universidade Universidade de de BrasíliaBrasília
Computação BásicaComputação Básica
Algoritmo Recursivo sem condição de 
Parada
Exemplo de um algoritmo com uma função RECURSIVA QUE ENTRA EM
LOOP INFINITO.
Algoritmo LoopInfinito
Função inteiro loop (inteiro x) 
Início
Se (x<10) 
Prof. Bruno Macchiavello 6
Se (x<10) 
Retorne loop(x) 
Fim
Variáveis
i : inteiro
Início
i ← 1
loop(i)
retorna 0
Fim
Esta função ficará num
loop infinito (chamando
a si mesmo), pois não há 
uma condição de parada.
Departamento de Ciência da ComputaçãoDepartamento de Ciência da Computação
Universidade Universidade de de BrasíliaBrasília
Computação BásicaComputação Básica
Exemplo Algoritmo Recursivo
• Por exemplo, vamos analizar o problema do 
fatorial.
�De maneira ITERATIVA temos:
fat (n) = 1 * 2 * 3 .... n
�De maneira RECURSIVA temos:
Prof. Bruno Macchiavello 7
fat (n) = 1 * 2 * 3 .... n
fat (n) = n * fat (n – 1), 
sendo fat (0) = 1
Departamento de Ciência da ComputaçãoDepartamento de Ciência da Computação
Universidade Universidade de de BrasíliaBrasília
Computação BásicaComputação Básica
Exemplo Algoritmo Recursivo
FATORIAL ITERATIVO (não recursivo)
Algoritmo FatorialIterativo
fat (n) = 1 * 2 * 3 .... n
Prof. Bruno Macchiavello 8
Algoritmo FatorialIterativo
Variáveis
n, i, fat : inteiro
Início
fat ← 1
Leia (n)
Para i= 1 até n faça
fat ← fat * i
Escreva (“Fatorial de n = “,fat)
Fim
Algoritmos iterativos solucionam
um problema através de 
execução repetida utilizando 
construções como Para e, 
Enquanto.
Departamento de Ciência da ComputaçãoDepartamento de Ciência da Computação
Universidade Universidade de de BrasíliaBrasília
Computação BásicaComputação Básica
Exemplo Algoritmo Recursivo
• FATORIAL RECURSIVO:
fat(5) = 5*fat (5-1); equação 1
fat(4) = 4*fat(4-1); equação 2
fat(3) = 3*fat(3-1); equação 3
fat(2) = 2*fat(2-1); equação 4
fat(1) = 1*fat(1-1); equação 5
fat (n) = n * fat (n – 1), 
sendo fat (0) = 1
fat(1) = 1*fat(1-1); equação 5
fat(0) = 1; equação 6
Substituindo a equação 6 na equação 5 temos: fat(1) = 1*1
Substituindo a equação 5 na equação 4 temos: fat(2) = 2*1
Substituindo a equação 4 na equação 3 temos: fat(3) = 3*2
Substituindo a equação 3 na equação 2 temos: fat(4) = 4*6
Substituindo a equação 2 na equação 1 temos: fat(5) = 5*24
E assim fat(5) = 120
Prof. Bruno Macchiavello 9
Departamento de Ciência da ComputaçãoDepartamento de Ciência da Computação
Universidade Universidade de de BrasíliaBrasília
Computação BásicaComputação Básica
Exemplo Algoritmo Recursivo
• Visualmente podemos analisar o fatorial de 3, fat(3), 
da seguinte forma:
• Para cada nova chamada na função, mais memória 
é utilizada para guardar as informações (variáveis) 
daquela chamada.
Prof. Bruno Macchiavello 10
Departamento de Ciência da ComputaçãoDepartamento de Ciência da Computação
Universidade Universidade de de BrasíliaBrasília
Computação BásicaComputação Básica
Exemplo Algoritmo Recursivo
• Chamamos esse conjunto de chamadas da mesma
função RECURSIVIDADE. É facil ver como o algoritmo
do fatorial é fortemente recursivo, pois é muito simples
analisar como a função pode se auto chamar.
• Entretanto, temos que tomar alguns CUIDADOS com a• Entretanto, temos que tomar alguns CUIDADOS com a
recursividade:
1. Temos sempre que ter um ponto de parada, para não
entramos em um loop infinito, por exemplo no fatorial, fat(0) = 1.
2. Analisar se a função realizará um número muito grande de
chamadas a ela mesma, pois a recursividade gasta um tempo
significativo para empilhar (guardar na memória) esses valores
e depois os desempilhar (recuperar e liberar memória).
Prof. Bruno Macchiavello 11
Departamento de Ciência da ComputaçãoDepartamento de Ciência da Computação
Universidade Universidade de de BrasíliaBrasília
Computação BásicaComputação Básica
Exemplo Algoritmo Recursivo
FATORIAL RECURSIVO
Algoritmo FatorialRecursivo
Função inteiro Fatorial (inteiro a)
Início
Se (a==0)
retorne 1
Prof. Bruno Macchiavello 12
retorne 1
senão
retorne (a*Fatorial(a-1))
Fim
Variáveis
n : inteiro
Início
Leia(n)
Escreva(Fatorial(n))
Fim
Departamento de Ciência da ComputaçãoDepartamento de Ciência da Computação
Universidade Universidade de de BrasíliaBrasília
Computação BásicaComputação Básica
Em Ansi C
FATORIAL RECURSIVO em C
#include <stdio.h>
int fat(int n)
{
if (n==0)
return 1;
else 
Prof. Bruno Macchiavello 13
else 
return n*fat(n-1);
}
int main()
{
int n;
printf("\n\nDigite um valor para n: ");
scanf("%d", &n);
printf("\nO fatorial de %d e' %d", n, fat(n));
getchar();
getchar();
return 0;
}
Departamento de Ciência da ComputaçãoDepartamento de Ciência da Computação
Universidade Universidade de de BrasíliaBrasília
Computação BásicaComputação Básica
Recursão Indireta
• Pode-se ter também uma forma indireta de recursão,
nas quais as rotinas são conectadas atravésde uma
cadeia de chamadas que acaba retornando a primeira
que foi chamada.
R1 ≡ [C1, R2]R1 ≡ [C1, R2]
R2 ≡ [C2, R3]
R3 ≡ [C3, R4]
R4 ≡ [C4, R5]
.
.
.
Rn ≡ [Cn, R1]
Prof. Bruno Macchiavello 14
Departamento de Ciência da ComputaçãoDepartamento de Ciência da Computação
Universidade Universidade de de BrasíliaBrasília
Computação BásicaComputação Básica
Torre de Hanoi
• O problema ou quebra-cabeça conhecido como torre de
Hanói foi publicado em 1883 pelo matemático francês
Edouard Lucas, também conhecido por seus estudos com a
série Fibonacci.
• Conta a lenda que no templo de Benares repousa uma placa
de latão onde estão pressas três agulhas de diamante. Numade latão onde estão pressas três agulhas de diamante. Numa
destas agulhas Deus colocou 64 discos, com o maior disco
na base e diminuindo cada vez de tamanho. Dia e noite sem
parar os sacerdotes transferem os discos de uma agulha para
a outra segundo as seguintes leis: um sacerdote não pode
mover mais de um disco por vez e deve colocar os discos na
nova agulha de modo que não haja nenhum disco menor
embaixo dele. Quando os 64 discos tiverem sido transferidos
o mundo desaparecerá.
Prof. Bruno Macchiavello 15
Departamento de Ciência da ComputaçãoDepartamento de Ciência da Computação
Universidade Universidade de de BrasíliaBrasília
Computação BásicaComputação Básica
Torres de Hanoi
• Algoritmo para mover N discos de A para C, usando B 
como auxiliar
1. Se N=1, mova o único disco de A para C e pare.
2. De N>1:
2.1 Mova os N-1 discos superiores de A prar B, usando C como 2.1 Mova os N-1 discos superiores de A prar B, usando C como 
auxiliar
2.2 Mova o disco restante de A para C
2.3 Mova os N-1 discos de B para C, usando A como auxiliar
Prof. Bruno Macchiavello 16
A B C
Departamento de Ciência da ComputaçãoDepartamento de Ciência da Computação
Universidade Universidade de de BrasíliaBrasília
Computação BásicaComputação Básica
Torres de Hanoi
Prof. Bruno Macchiavello 17
Departamento de Ciência da ComputaçãoDepartamento de Ciência da Computação
Universidade Universidade de de BrasíliaBrasília
Computação BásicaComputação Básica
Torres de Hanoi
• O número mínimo de “movimentos” para 
conseguir todos os discos é 2n-1.
• Logo:• Logo:
�Para 3 discos, são necessários 7 movimentos
�Para 15 discos, são necessários 32767 movimentos
�Para 64 discos, são necessários 
18446744073551615 movimentos
Prof. Bruno Macchiavello 18
Departamento de Ciência da ComputaçãoDepartamento de Ciência da Computação
Universidade Universidade de de BrasíliaBrasília
Computação BásicaComputação Básica
Torre de Hanoi – solução recursiva
Algoritmo Hanoi
Função MoveDisco(leteral Orig, Dest)
início
Escreva(“Movimento: ”, Orig, “ -> ”, Dest)
retorne()
Fim
Função MoveTorre(inteiro N; literal Orig, Dest, Aux)
Início
Prof. Bruno Macchiavello 19
Início
se N = 1 então
MoveDisco(Orig, Dest) 
senão
MoveTorre(N - 1, Orig, Aux, Dest)
MoveDisco(Orig, Dest)
MoveTorre(N - 1, Aux, Dest, Orig)
fim-se
retorne()
Fim
Variaveis
num_discos: inteiro
INICIO
Escreva(“Digite o numero de discos: “)
leia(num_discos)
movetorre(num_discos, “A”, “C”, “B”)
FIM
Departamento de Ciência da ComputaçãoDepartamento de Ciência da Computação
Universidade Universidade de de BrasíliaBrasília
Computação BásicaComputação Básica
Recusividade
• FUNÇÃO RECURSIVA:
� Uma solução recursiva ocupa mais memória e é mais lenta que a solução 
iterativa para um mesmo problema.
� Em cada instância, todos os parâmetros e variáveis locais são criados 
novamente, independentemente dos que já existiam antes.
� A cada nova chamada, o sistema deve guardar a posição de memória de � A cada nova chamada, o sistema deve guardar a posição de memória de 
onde a chamada foi feita, para que posteriormente possa voltar ao lugar 
certo.
� 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. 
� É fácil criar funções que chamem a elas mesmas.
� É difícil reconhecer situações apropriadas para a utilização de 
recursividade.
� Há certos problemas cuja natureza permite uma solução recursiva bem 
mais simples e intuitiva do que a solução iterativa. 
Prof. Bruno Macchiavello 20
Departamento de Ciência da ComputaçãoDepartamento de Ciência da Computação
Universidade Universidade de de BrasíliaBrasília
Computação BásicaComputação Básica
Exercícios
Realizar o algoritmo de busca binária de forma recursiva.
Prof. Bruno Macchiavello 21