Recursão em Javascript: Fatorial, Fibonacci, Torres de Hanói e Labirinto

Prévia do material em texto

ESTRUTURA DE DADOS
PROF. MSC. ALLAN KÁSSIO BECKMAN SOARES DA CRUZ
RECURSIVIDADE
CONCEITOS DE RECURSÃO
 Quando um método recursivo é chamado para resolver um problema, 
na verdade, ele é capaz de atuar somente no(s) caso(s) mais 
simples(s), ou caso(s) básico(s). 
 Se o método é requisitado para um caso básico, ele retorna um 
resultado. 
 Se é para um problema mais complexo, ele o divide em duas partes 
conceituais. 
 Para tornar a recursão realizável, a última parte deve assemelhar-se ao 
problema original, mas ser uma versão ligeiramente mais simples ou 
menor dele. 
 Como esse novo problema é parecido com o original, o método 
destina uma cópia nova dele próprio para trabalhar no problema 
menor
FATORIAIS
 Vamos escrever um programa recursivo para efetuar um 
cálculo matemático popular. Considere o fatorial de um 
inteiro positivo, n, escrito como n! (pronuncia-se “n fatorial”), 
que é o produto 
 n · (n – 1) · (n – 2) · … · 1 
 com 1! igual a 1 e 0! definido como 1. 
 Por exemplo, 5! é o produto 5 · 4 · 3 · 2 · 1, que é igual a 120.
FATORIAL
FATORIAL
FATORIAL
PARE E PENSE!
O QUE ACONTECE COM 
ENTRADAS MAIORES OU 
IGUAIS A 22!
FATORIAL
SÉRIE DE FIBONACCI
 Inicia com 0 e 1 e tem a propriedade de que cada número de 
Fibonacci subsequente é a soma dos dois anteriores.
 0, 1, 1, 2, 3, 5, 8, 13, 21, … 
 Definição recursiva:
 fibonacci(0) = 0 
 fibonacci(1) = 1 
 fibonacci(n) = fibonacci(n – 1) + fibonacci(n – 2)
SÉRIE DE FIBONACCI
SÉRIE DE FIBONACCI
RECURSÃO E A PILHA DE CHAMADAS DE 
MÉTODO
TORRES DE HANÓI
 As Torres de Hanói são um dos problemas clássicos da 
computação. 
 Diz a lenda que, em um templo no Extremo Oriente, os sacerdotes 
tentam mover uma pilha de discos dourados de um pino de 
diamante para outro. 
 A pilha inicial tem 64 discos sobrepostos em um pino e organizados 
de baixo para cima por tamanho decrescente. 
TORRES DE HANÓI
 Os sacerdotes tentam mover a pilha de um pino para outro sob as 
restrições de que exatamente um disco seja movido por vez e de 
que, em nenhuma circunstância, um disco maior pode ser 
colocado em cima de um menor. 
 Três pinos são fornecidos, e um deles é utilizado para armazenar 
discos temporariamente. 
 Ao que parece, o mundo acabará quando os sacerdotes 
completarem sua tarefa, portanto, há pouco incentivo para 
facilitarmos esses esforços.
TORRES DE HANÓI
 Vamos assumir que os sacerdotes estão tentando mover os discos 
do pino 1 para o pino 3. Desejamos desenvolver um algoritmo que 
represente a sequência precisa de transferências de discos de um 
pino para outro.
TORRES DE HANÓI
 Se procurarmos uma solução iterativa, provavelmente nos 
encontraremos sem esperança “enroscados” no gerenciamento dos 
discos. 
 Em vez disso, abordar esse problema de maneira recursiva produz logo 
uma solução. Mover n discos pode ser visualizado em termos de mover 
somente n – 1 discos (daí a recursão), como a seguir: 
 1. Mova n – 1 discos do pino 1 para o pino 2, utilizando o pino 3 como área 
de armazenamento temporário. 
 2. Mova o último disco (o maior) do pino 1 para o pino 3. 
 3. Mova n – 1 discos do pino 2 para o pino 3, utilizando o pino 1 como área 
de armazenamento temporário. 
 O processo termina quando a última tarefa envolve mover n = 1 disco (isto é, 
o caso básico). Essa tarefa é cumprida movendo o disco sem usar uma área 
de armazenamento temporário.
TORRES DE HANÓI
1 --> 3 
1 --> 2 
3 --> 2 
1 --> 3 
2 --> 1 
2 --> 3
1 --> 3
DESAFIO: LABIRINTO MAZE RUNNER
 A grade de #s e pontos (.) é uma representação bidimensional do array de um 
labirinto. 
 Os #s representam as paredes do labirinto, e os pontos, as localizações nos possíveis 
caminhos por ele. Um movimento só é permitido nas posições do array que 
contiverem um ponto.
# # # # # # # # # # # #
# . . . # . . . . . . #
. . # . # . # # # # . #
# # # . # . . . . # . #
# . . . . # # # . # . .
# # # # . # . # . # . #
# . . # . # . # . # . #
# # . # . # . # . # . #
# . . . . . . . . # . #
# # # # # # . # # # . #
# . . . . . . # . . . #
# # # # # # # # # # # #
DESAFIO: LABIRINTO MAZE RUNNER
 Escreva um método recursivo (mazeRunner) para percorrer labirintos como 
o do slide anterior. 
 O método deve receber como argumentos o array de caracteres de 12 
por 12 representando o labirinto e a localização atual nele (na primeira vez 
que esse método é chamado, a localização atual deve ser o ponto de 
entrada no labirinto). 
 À medida que mazeRunner tenta localizar a saída, ele deve colocar o 
caractere x em cada quadrado no caminho. Há um algoritmo simples para 
percorrer um labirinto que garante a localização da saída (assumindo que 
existe uma saída). 
 Se não houver nenhuma saída, você chegará à localização inicial 
novamente. O algoritmo é como segue: a partir da localização atual no 
labirinto, tente mover-se um espaço em qualquer uma das possíveis 
direções (para baixo, para a direita, para cima ou para a esquerda). 
DESAFIO: LABIRINTO MAZE RUNNER
 Se for possível ir pelo menos para uma direção, chame mazeRunner 
recursivamente, passando o novo local no labirinto como o atual. 
 Caso não consiga caminhar em nenhuma direção, “volte” a um local 
anterior no labirinto e tente um novo sentido a partir desse local (esse é um 
exemplo do retorno recursivo). 
 Programe o método para exibir o labirinto depois de cada movimento a 
fim de que o usuário possa observar enquanto uma solução para ele é 
procurada. 
 A saída final do labirinto deve exibir somente o caminho necessário para 
resolvê-lo — na hipótese de que seguir por uma direção resulte em um 
caminho sem saída, o x para marcar esses passos não deve ser exposto. 
 [Dica: para mostrar apenas o caminho final, pode ser útil marcar os locais 
que resultam em um caminho sem saída com outro caractere (como ‘0’).]