Aula_002

Prévia do material em texto

O conceito de recursividade
Algoritmo do fatorial recursivo
Problema da Torre de Hanói
Aula 2: Recursividade
2.1
Recursividade
2.2
Procedimentos ou funções recursivas correspondem
a aqueles que contêm chamadas a si mesmo.
Todo procedimento, recursivo ou não,
deve possuir pelo menos uma 
chamada não recursiva. 
Essas são denominadas chamadas externas.
Recursividade
2.3
Se ocorrer uma chamada recursiva:
o algoritmo é interrompido e reiniciado no 
princípio do procedimento recursivo;
após o término da computação do procedimento
correspondente à chamada recursiva, o algoritmo
é interrompido e reiniciado no ponto seguinte ao 
da ocorrência da chamada recursiva.
Recursão x Iteração
2.4
Vantagens da recursão
Recursão versus Iteração
Vantagens da iteração
De um modo geral, a cada processo recursivo 
corresponde um outro iterativo
algoritmos mais concisos;
Geralmente,
prova de correção mais simples.
Geralmente, mais eficiente.
Cálculo de Fatorial
2.5
n! = n.(n-1)...1
5! = 5 . 4 . 3 . 2 . 1 = 120
Convenção: 0! = 1
Escrever um algoritmo para calcular n!
Primeiro exemplo: cálculo de fatorial
Idéia: n! = n.(n-1)!
O algoritmo abaixo usa a função recursiva fat
Algoritmo: fatorial(recursivo)
chamada externa: fat(n)
função fat(i)
 se i ≤ 1 então 1 senão i.fat(i-1)
Recursividade Passo a Passo
2.6
Exemplo: fatorial recursivo, com n = 5
Como seguir os passos de um algoritmo recursivo?
 VoltarCalcular
Resposta: 120
fat( 5 )
Algoritmo 1.3: fatorial (iterativo)
Cálculo iterativo de fatorial
a variável fat representa um vetor, e não mais 
uma função
o elemento fat[i] contém o valor i!, 0 <= i <= n
fat[0]:=1
para j=1,..., n faça
 fat[j] := j . fat[j-1]
Cálculo Iterativo do Fatorial
2.7
Iteração Passo a Passo
2.8
Como seguir os passos de um algoritmo iterativo?
24 120
fat[1] fat[2] fat[3] fat[4] fat[5]fat[0]
1 1
 VoltarCalcular
Resposta: 1202 6
Calcular o valor n!, através de um algoritmo iterativo, 
de modo que prescinda do armazenamento de qualquer
vetor.
Tempo: 12 minutos.
Exercício
2.9
Exercício (solução)
2.10
Solução:
Ao final do algoritmo, a variável fat contém o valor 
de n!
algoritmo fatorial
ant := fat := 1
se n > 1 então
 para i = 2, ..., n faça
 fat := ant . i
 ant := fat
Problema da Torre de Hanói
2.11
O problema consiste de 3 pinos, A, B e C, denominados origem, destino e
trabalho, respectivamente. Além dos pinos, há n discos de diâmetros 
diferentes. Inicialmente, todos os discos se encontram empilhados no 
pino origem, em ordem crescente de tamanho, de cima para baixo.
O objetivo é empilhar todos os discos no pino destino, atendendo às 
seguintes restrições:
(i) apenas um disco pode ser movido de cada vez;
(ii) qualquer disco não pode jamais ser colocado sobre
outro de menor tamanho.
. . .
origem destino trabalho
 
1
n-1
n
situação inicial
. . .
origem destino trabalho
1
n-1
n
situação final
Torre de Hanói
2.12
Problema com n = 4 discos
origem destino trabalho
1
2
3
4
situação inicial
origem destino trabalho
4
2
3 1 possível situação 
intermediária
origem destino trabalho
4
3
2 1
situação proibida
Torre de Hanói
2.13
Problema com n = 2 discos
origem destino trabalho
1
2
situação inicial
origem destino trabalho
1
2
movimento 1
origem destino trabalho
1
2
movimento 2
origem destino trabalho
1
2
movimento 3
total: 3 movimentos
Torre de Hanói
2.14
Problema com n = 2 discos
 Voltar Mover
Exercício: resolver o problema da Torre de Hanói
 
 com n = 3 discos
Tempo: 12 minutos
Total: 3 movimentos
origem destino trabalho
Solução do problema da Torre de Hanói: 3 discos, 7 movimentos
origem destino trabalho
1
2
3
Torre de Hanói
2.15
origem destino trabalho
1
23
origem destino trabalho
2
3 1
origem destino trabalho
1 3 2
origem destino trabalho
1
2
3
origem destino trabalho
3 1 2
origem destino trabalho
3
1
2
origem destino trabalho
1
2
3
Torre de Hanói
2.15
Solução do problema da Torre de Hanói: 3 discos
origem destino trabalho
 Voltar Mover
Total: 7 movimentos
Suponha que se saiba como resolver o problema até
n-1 discos, n > 1, de forma recursiva.
Solução geral do problema da Torre de Hanói
A extensão para n discos pode ser obtida pela 
realização dos seguintes passos:
Resolver o problema da Torre de Hanói com os n-1
discos do topo do pino A, usando A como origem, 
B como trabalho e C como destino;
Mover o n-ésimo pino (maior de todos) de A para B;
Resolver o problema da Torre de Hanói com os n-1
discos do topo do pino C, usando A como trabalho, 
B como destino e C como origem.
Torre de Hanói
2.17
Torre de Hanói
2.18
Esquema da solução do problema da Torre de Hanói
. . .
origem destino trabalho
 
1
n-1
n
(a) situação inicial
origem destino trabalho
 
n
 (b)
. . .
1
n-1
origem destino trabalho
 
 (c)
. . .
1
n-1n
origem destino trabalho
 
 (d)
. . .
1
n-1
n
A Bc
Reiniciar
Animar
n = 1; origem: A; destino: B; trabalho: C
sub-objetivo: mover 1 peça de A para B
Caso simples:
mover 1 peça de ORIGEM para DESTINO
n = 1; origem: B; destino: C; trabalho: A
sub-objetivo: mover 1 peça de B para C
Caso simples:
mover 1 peça de ORIGEM para DESTINO
n = 2; origem: A; destino: C; trabalho: B
sub-objetivo: mover 2 peças de A para C
mover n-1 peças de ORIGEM para TRABALHO
mover 1 peça de ORIGEM para DESTINO
mover n-1 peças de TRABALHO para DESTINO
n = 1; origem: C; destino: A; trabalho: B
sub-objetivo: mover 1 peça de C para A
Caso simples:
mover 1 peça de ORIGEM para DESTINO
n = 1; origem: A; destino: B; trabalho: C
sub-objetivo: mover 1 peça de A para B
Caso simples:
mover 1 peça de ORIGEM para DESTINO
n = 2; origem: C; destino: B; trabalho: A
sub-objetivo: mover 2 peças de C para B
mover n-1 peças de ORIGEM para TRABALHO
mover 1 peça de ORIGEM para DESTINO
mover n-1 peças de TRABALHO para DESTINO
n = 3; origem: A; destino: B; trabalho: C
Objetivo: mover 3 peças de A para B
mover n-1 peças de ORIGEM para TRABALHO
mover 1 peça de ORIGEM para DESTINO
mover n-1 peças de TRABALHO para DESTINO
2.19
Algoritmo: Torre de Hanói
Parâmetros: 1°) número de discos
 2°) pino de origem
 3°) pino de destino
 4°) pino de trabalho
proc hanoi( n, A, B, C )
 se n > 0 então
 hanoi( n-1, A, C, B )
 mover o disco do topo de A para B
 hanoi( n-1, C, B, A )
Torre de Hanói
2.20
Torre de Hanói
2.21
Exercícios finais:
Mostrar que o algoritmo apresentado para o
Problema da Torre de Hanói requer, exatamente,
2 
n
 - 1 movimentos de disco.
Reescrever o algoritmo do Problema da Torre de
Hanói de forma que a recursividade pare no nível
correspondente a n = 1, e não n = 0. Há alguma
vantagem em realizar esta modificação? Qual?