Pratica10-Recursividade

Prévia do material em texto

Algoritmos e Técnicas de 
Programação
Prática – Recursividade
Recursividade - Introdução
� Um algoritmo “A” é denominado recursivo quando 
chama (invoca) a si mesmo de forma:
� direta: “A” chama “A” dentro dele mesmo, de forma visível 
ou explícita.
� indireta: “A” invoca outro(s) algoritmo(s) que, em algum 
momento, chama(m) “A”.
� Um algoritmo recursivo tem duas partes essenciais:
� uma ou mais chamadas a si mesmo, direta(s) ou 
indireta(s), sem a(s) qual(ais) não seria recursivo;
� uma ou mais condições de parada, para garantir que a 
computação seja finita!
Problema 1
� Implementar dentro de um programa em C uma 
função recursiva para calcular o Máximo Divisor 
Comum (MDC) entre dois inteiros positivos, a partir 
da definição recursiva do algoritmo de Euclides:
se 0
MDC( , ) MDC( , mod ) se
MDC( , mod ) se
a b
a b b a b a b
a b a b a
=

= >
 >
Solução 1a – Pseudocódigo
função MDC(a, b : inteiro) : inteiro
início
se b = 0 então
retorne a
senão
se a > b então
retorne MDC(b, a mod b)
senão
retorne MDC(a, b mod a)
fimse
fimse
fim
Solução 1b (Iterativa)-Pseudocódigo
funcao MDC_NR(a, b: inteiro): inteiro
declare
r: inteiro
inicio
r ← a mod b
enquanto r > 0 faça
a ← b
b ← r
r ← a mod b
fimenquanto
retorne b
fim
Comentários sobre as soluções 1a e 1b
� Observe que, dada a definição recursiva, a 
implementação recursiva (1a) é imediata, ou 
seja, quase uma transcrição. Além disso, o 
código é compacto e claro.
� Chegar à conclusão de que a solução “1b”
faz o mesmo que “1a” não é tão imediato, 
requer uma análise mais minuciosa.
Problema 2 – Torre de Hanoi
� O problema da torre de Hanoi consiste em mover 
N discos (torre) de um pino A para um pino C, 
usando um pino B como auxiliar e duas regras:
� somente um disco pode ser movido de cada vez;
� um disco maior não pode ficar sobre outro menor.
� Uma elegante solução recursiva consiste em:
� Mover a torre com N-1 discos de A para B;
� Mover o disco de A para C;
� Mover a torre com N-1 discos de B para C.
Problema 2 - Visualização do Problema e 
sua Solução
Torre original em A 1) Torre com N-1 discos de A para B
2) Disco de A para C 3) Torre com N-1 discos de B para C
Solução 2 – Pseudocódigo
procedimento MoveTorre(N : inteiro; 
Orig, Dest, Aux : caractere) 
início
se N = 1 então
Escreva(“Movimento:”, Orig, “ -> ”, Dest) 
senão
MoveTorre(N - 1, Orig, Aux, Dest) 
Escreva(“Movimento:”, Orig, “ -> ”, Dest) 
MoveTorre(N - 1, Aux, Dest, Orig) 
fimse
fim