Algoritmos2_Aula8-Recursividade3

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

RECURSIVIDADE - parte 3
Algoritmos II
Prof. Thiago Meirelles Ventura
UFMT – IC – 2012/2
Máximo Divisor Comum (MDC)
Exemplos:
mdc (12,20) = 4
mdc (20,24) = 4
mdc (12,15) = 3
Máximo Divisor Comum (MDC)
Função mdc1 (x, y: inteiro): inteiro 
Início
 Se (x = y)
 retorne x;
 Fimse
 Se (x > y)
 retorne mdc1 (x - y, y);
 Senão
 retorne mdc1 (x, y - x); 
 Fimse
Fim
Máximo Divisor Comum (MDC)
Função mdc2 (x, y: inteiro): inteiro 
Início
 Se (y = 0) então
 retorne x;
 Fimse
 retorne mdc2 (y, x resto y);
 
Fim
Recursão indireta
Uma função é dita recursiva quando ela chama a si mesma.
Mas uma função pode chamar uma outra função, que por sua vez chama a primeira função.
Isso é uma recursão indireta
Função A -> Função B -> ... -> Função A
Recursão indireta
Verificar se um número é par ou ímpar
Função par (n: inteiro): lógico 
Início
 Se (n = 0) então
 retorne VERDADEIRO;
 Senão 
 retorne impar (n-1);
 Fimse
Fim
Função impar (n: inteiro): lógico 
Início
 Se (n = 0) então
 retorne FALSO;
 Senão 
 retorne par (n-1);
 Fimse
Fim
Iteração vs Recursão
Implemente uma função NÃO-recursiva que resolva o sistema de equações abaixo:
Depois, resolva o mesmo problema, só que de forma recursiva.
Torre de Hanoi
Objetivo: 
Transportar os discos de um bastão para outro
Regras:
Só pode movimentar um disco por vez
Um disco maior não pode ficar por cima de um disco menor
Não pode mover um disco que está em baixo de outro
Jogo online
Torre de Hanoi
Algoritmo Hanoi
Início
 transfere (7, “a”, “b”, “c”);
Fim
Procedimento moveTorre (n: inteiro, orig, dest, aux: String)
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);
 Fimse
Fim
Curvas de Hilbert