Programação Lógica

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

Solução em Prolog

Consultas de Teste

Desafios Adicionais

1. Modifique o predicado para funcionar com números negativos.
2. Implemente potencia(Base, Expoente, Resultado) usando o mesmo padrão recursivo.
3. 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.

Solução em Prolog

Consultas de Teste

Desafios Adicionais

1. Implemente binario_str(N, S) que retorna uma string binária em vez de lista.
2. Implemente decimal(B, N) que converte uma lista de bits de volta para decimal.
3. 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

Solução em Prolog

Problema: Loops Infinitos!

O predicado acima pode entrar em loops infinitos devido a ciclos no grafo. Para resolver isso, mantemos uma lista de visitados:

Consultas de Teste

Desafios Adicionais

1. Caminho mais curto: Implemente menor_dist(A, B, D) que encontra a menor distância entre A e B (use findall/3 e min_list/2).
2. Lista de cidades: Modifique o predicado para retornar a lista de cidades no caminho, além da distância.
3. Grafo com pesos negativos: Como você lidaria com estradas de “mão única” ou pesos negativos?
4. 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!

Uma relação transitiva é aquela em que, se r(x,y) e r(y,z) são verdadeiras, então r(x,z) também é verdadeira. Em Prolog, podemos modelar relações transitivas de forma elegante usando recursão, permitindo navegar por cadeias de relacionamentos como ancestralidade, hierarquias e conexões em grafos.

O que é uma Relação Transitiva?

Formalmente, uma relação R é transitiva se:

Por exemplo, se “x é pai de y” e “y é pai de z”, então “x é avô de z”. A relação “ancestral” é o fecho transitivo da relação “pai”.

Programa 4.3: Ancestral

Vamos construir uma base de fatos sobre relações familiares e definir a regra ancestral/2:

Estrutura da Regra Ancestral

A regra ancestral/2 tem dois componentes:

1. Caso base: ancestral(X, Y) :- pai(X, Y). — X é ancestral direto de Y (pai).
2. Passo recursivo: ancestral(X, Y) :- pai(X, Z), ancestral(Z, Y). — X é ancestral de Y se existe um intermediário Z, onde X é pai de Z e Z é ancestral de Y.

Diagrama da Árvore Genealógica

Visualize a estrutura familiar:

Fluxo de Execução: ancestral(X, enos)

Quando consultamos ?- ancestral(X, enos)., o Prolog busca todos os ancestrais de Enos:

Resultado: X = seth ; X = adao ; false.

Navegando pela Árvore

O Prolog navega pela árvore genealógica da seguinte forma:

Programa 4.4: Acima (Relação Espacial)

Agora, um exemplo diferente: objetos empilhados uns sobre os outros.

Diagrama da Relação “Acima”

Visualize a pilha de objetos:

Consultas com Acima

1. Quem está acima de a?

2. Quem está abaixo de d?

Recursão “Para Frente” e “Para Trás”

Observe a diferença na direção da recursão:

• Ancestral (para cima): ancestral(X, Y) :- pai(X, Z), ancestral(Z, Y).
  Percorre a árvore para cima (dos mais novos para os mais velhos).
• Descendente (para baixo): Se quiséssemos encontrar descendentes, faríamos:
  descendente(X, Y) :- pai(Y, X). (base)
  descendente(X, Y) :- pai(Y, Z), descendente(X, Z). (passo)
  Percorre a árvore para baixo (dos mais velhos para os mais novos).

A direção da recursão é determinada por onde colocamos a variável fixa na chamada recursiva.

Exercícios Propostos

1. Descendente: Implemente descendente(X, Y) que é verdadeiro se X é descendente de Y (filho, neto, bisneto, etc.). Use a base de fatos pai/2.
2. Irmãos: Implemente irmao(X, Y) que é verdadeiro se X e Y têm o mesmo pai.
3. Primos: Implemente primo(X, Y) que é verdadeiro se X e Y são primos (têm um ancestral em comum, mas não são irmãos).
4. Caminho em grafo: Dada uma base de fatos aresta(X, Y), implemente caminho(X, Y) que é verdadeiro se existe um caminho de X até Y.
5. Desafio: Implemente parente(X, Y) que é verdadeiro se X é parente de Y (ancestral ou descendente). Dica: use a união de duas regras.

Conclusão

As relações transitivas são um dos usos mais poderosos da recursão em Prolog. Com apenas algumas linhas de código, podemos modelar:

• Árvores genealógicas (ancestralidade, descendência)
• Hierarquias espaciais (acima, abaixo, dentro)
• Grafos (caminhos, conexões)
• Redes de dependência (pré-requisitos, requisitos)

A elegância da solução está na simplicidade da definição: uma regra base e uma regra recursiva que “anda” pela relação. O Prolog cuida do resto — navegando pela árvore, encontrando todos os caminhos e retornando as soluções uma a uma.

A chave para dominar relações transitivas é entender a direção da recursão: a posição da variável fixa determina se você está subindo ou descendo na hierarquia. Pratique com os exercícios e explore as infinitas possibilidades que essa técnica oferece!