A melhor forma de aprender recursividade em Prolog é praticando! Neste artigo, vamos resolver três exercícios clássicos que cobrem diferentes aspectos da recursão: operações aritméticas, conversão de bases e caminhamento em grafos. Cada exercício inclui dicas, solução completa, testes e desafios extras.
Exercício 4.1: Produto de Números Naturais
Problema: Defina um predicado recursivo prod(X, Y, P) que calcule o produto
de dois números naturais X e Y usando apenas soma e subtração.
Raciocínio
Sabemos que X * Y = X + X + X + … (Y vezes). Usando recursão:
- Caso base: X * 0 = 0
- Passo recursivo: X * Y = X + X * (Y-1)
Diagrama do Processo
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
prod(3, 4, P) │ ├─ Y = 4 > 0, Y1 = 3 │ chama prod(3, 3, P1) │ │ │ ├─ Y = 3 > 0, Y1 = 2 │ │ chama prod(3, 2, P2) │ │ │ │ │ ├─ Y = 2 > 0, Y1 = 1 │ │ │ chama prod(3, 1, P3) │ │ │ │ │ │ │ ├─ Y = 1 > 0, Y1 = 0 │ │ │ │ chama prod(3, 0, P4) │ │ │ │ │ │ │ │ │ ├─ [BASE] prod(3, 0, 0) ✅ │ │ │ │ │ │ │ │ │ └─ P4 = 0 │ │ │ │ │ │ │ └─ P3 = 3 + 0 = 3 │ │ │ │ │ └─ P2 = 3 + 3 = 6 │ │ │ └─ P1 = 3 + 6 = 9 │ └─ P = 3 + 9 = 12 ✅ |
Solução em Prolog
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
% prod(X, Y, P) - P é o produto de X e Y % Caso base: qualquer número multiplicado por 0 é 0 prod(_, 0, 0). % Passo recursivo: X * Y = X + X * (Y-1) prod(X, Y, P) :- Y > 0, % Garante que Y é positivo Y1 is Y - 1, % Decrementa Y prod(X, Y1, P1), % Chama recursivamente com Y-1 P is P1 + X. % Soma X ao resultado parcial |
Consultas de Teste
|
1 2 3 4 5 6 7 8 9 10 11 |
?- prod(3, 4, P). P = 12. ?- prod(5, 0, P). P = 0. ?- prod(7, 3, P). P = 21. ?- prod(0, 5, P). P = 0. |
Desafios Adicionais
- Modifique o predicado para funcionar com números negativos.
- Implemente
potencia(Base, Expoente, Resultado)usando o mesmo padrão recursivo. - Implemente
divisao(Dividendo, Divisor, Quociente, Resto)usando apenas subtração.
Exercício 4.2: Número Natural em Binário
Problema: Defina um predicado recursivo binario(N, B) que converta um número
natural N para sua representação binária B (como lista de bits).
Raciocínio
Para converter um número para binário:
- Caso base: N = 0 → [0]; N = 1 → [1]
- Passo recursivo: O bit menos significativo é N mod 2; o resto é a representação binária de N // 2.
Exemplo: 13 em binário é 1101.
|
1 2 3 4 5 6 |
13 / 2 = 6, resto 1 → bit menos significativo = 1 6 / 2 = 3, resto 0 → próximo bit = 0 3 / 2 = 1, resto 1 → próximo bit = 1 1 / 2 = 0, resto 1 → próximo bit = 1 Resultado: [1, 1, 0, 1] (lido de cima para baixo) |
Solução em Prolog
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
% binario(N, B) - B é a lista de bits da representação binária de N % Caso base: números 0 e 1 binario(0, [0]). binario(1, [1]). % Passo recursivo: divide N por 2, converte o quociente e adiciona o resto binario(N, B) :- N > 1, % Apenas para números maiores que 1 Q is N // 2, % Quociente da divisão por 2 R is N mod 2, % Resto (bit menos significativo) binario(Q, B1), % Converte o quociente recursivamente append(B1, [R], B). % Adiciona o bit ao final da lista |
Consultas de Teste
|
1 2 3 4 5 6 7 8 9 10 11 |
?- binario(13, B). B = [1, 1, 0, 1]. ?- binario(0, B). B = [0]. ?- binario(5, B). B = [1, 0, 1]. ?- binario(255, B). B = [1, 1, 1, 1, 1, 1, 1, 1]. |
Desafios Adicionais
- Implemente
binario_str(N, S)que retorna uma string binária em vez de lista. - Implemente
decimal(B, N)que converte uma lista de bits de volta para decimal. - Implemente
binario_completo(N, Bits, Tamanho)que retorna a representação com um número fixo de bits (ex: 8 bits).
Exercício 4.3: Mapa de Estradas
Problema: Dado um mapa de estradas com distâncias, defina um predicado dist(A, B, D)
que calcule a distância total entre duas cidades A e B, considerando caminhos diretos e indiretos.
Raciocínio
Temos fatos estrada(Origem, Destino, Km). Queremos encontrar a distância total entre duas cidades:
- Caso base: Existe uma estrada direta entre A e B.
- Passo recursivo: Existe uma estrada de A para C, e um caminho de C para B.
Diagrama do Mapa
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
10 A -------- B | | | 15 | 20 | | C -------- D 25 Estradas: - estrada(a, b, 10) - estrada(a, c, 15) - estrada(b, d, 20) - estrada(c, d, 25) Rotas possíveis: - a → b → d = 10 + 20 = 30 - a → c → d = 15 + 25 = 40 - a → b → d → c → a = 10 + 20 + 25 + 15 = 70 (ciclo) |
Solução em Prolog
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
% Fatos: estrada(Origem, Destino, Km) estrada(a, b, 10). estrada(a, c, 15). estrada(b, d, 20). estrada(c, d, 25). % Para rotas bidirecionais (opcional) estrada(X, Y, D) :- estrada(Y, X, D). % dist(A, B, D) - D é a distância total entre A e B % Caso base: estrada direta dist(A, B, D) :- estrada(A, B, D). % Passo recursivo: A → C → B dist(A, B, D) :- estrada(A, C, D1), % Vai de A para C dist(C, B, D2), % Caminho de C para B D is D1 + D2. % Soma as distâncias |
Problema: Loops Infinitos!
O predicado acima pode entrar em loops infinitos devido a ciclos no grafo. Para resolver isso, mantemos uma lista de visitados:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
% dist_seguro(A, B, D) - com prevenção de loops dist_seguro(A, B, D) :- dist_seguro(A, B, [A], D). % Caso base: estrada direta dist_seguro(A, B, _, D) :- estrada(A, B, D). % Passo recursivo com lista de visitados dist_seguro(A, B, Visitados, D) :- estrada(A, C, D1), \+ member(C, Visitados), % C não foi visitado ainda dist_seguro(C, B, [C|Visitados], D2), D is D1 + D2. |
Consultas de Teste
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
?- dist(a, d, D). D = 30 ; % Via b D = 40 ; % Via c false. ?- dist_seguro(a, d, D). D = 30 ; % Via b D = 40 ; % Via c false. ?- dist(a, a, D). D = 0 ; % (se houver estrada direta de a para a) ... loop infinito (com dist) ... false (com dist_seguro, após explorar ciclos) ?- dist_seguro(a, b, D). D = 10 ; % Direto D = 40 ; % Via c → d → b (15 + 25 + 20) D = 70 ; % Via c → d → b → a → ... (ciclo) - com dist_seguro, evita |
Desafios Adicionais
-
Caminho mais curto: Implemente
menor_dist(A, B, D)que encontra a menor distância entre A e B (usefindall/3emin_list/2). - Lista de cidades: Modifique o predicado para retornar a lista de cidades no caminho, além da distância.
- Grafo com pesos negativos: Como você lidaria com estradas de “mão única” ou pesos negativos?
-
Todas as rotas: Implemente
todas_rotas(A, B, R)que retorna todas as rotas possíveis entre A e B (sem loops).
Conclusão: A Importância da Recursão em Prolog
Os exercícios acima demonstram três áreas onde a recursão em Prolog é essencial:
- Operações aritméticas: A recursão permite definir operações matemáticas a partir de conceitos mais simples, como soma e subtração.
- Conversão e processamento de dados: A recursão é natural para processar estruturas hierárquicas, como a representação binária de números.
- Exploração de grafos: A recursão é a ferramenta ideal para navegar em estruturas interconectadas, encontrando caminhos e calculando distâncias.
A beleza da recursão em Prolog está na sua simplicidade declarativa: você descreve o caso base e a regra de redução, e o Prolog cuida da execução, backtracking e busca de soluções. Isso permite que problemas complexos sejam expressos em poucas linhas de código.
Para dominar a recursão em Prolog, pratique com diferentes tipos de problemas:
- Estruturas de lista: soma, inversão, busca, ordenação
- Árvores: percurso, altura, busca
- Grafos: caminhos, ciclos, conectividade
- Matemática: sequências, séries, relações
Lembre-se sempre: todo predicado recursivo precisa de um caso base e de uma garantia de progresso (a chamada recursiva deve operar sobre uma instância menor do problema). Com isso, você estará pronto para explorar todo o poder da programação lógica!