Arquivo de Programação Lógica - Página 3 de 13

Algoritmos Recursivos em Listas (Merge Sort)

16/07/202615/07/2026 Por antonino

O Merge Sort é um algoritmo clássico de ordenação baseado no paradigma “dividir para conquistar”. Em Prolog, sua implementação é particularmente elegante devido à natureza recursiva das listas e ao poder da unificação. Vamos construir o algoritmo passo a passo.

1. O Paradigma “Dividir para Conquistar”

O Merge Sort segue três passos fundamentais:

Distribuir (Dividir): A lista original é dividida em duas sublistas aproximadamente iguais.
Ordenar recursivamente (Conquistar): Cada sublista é ordenada recursivamente usando o mesmo algoritmo.
Intercalar (Combinar): As duas sublistas ordenadas são mescladas em uma única lista ordenada.

2. Passo 1: Distribuir — `distribui/3` (Programa 5.4)

O predicado distribui/3 divide uma lista em duas, alternando os elementos entre elas.

% distribui(L, A, B) - A e B são as duas metades de L (alternadas)
% Caso base: lista vazia → duas listas vazias
distribui([], [], []).

% Caso base: lista com um elemento → A recebe o elemento, B fica vazio
distribui([X], [X], []).

% Passo recursivo: [X,Y|Z] → X vai para A, Y vai para B, continua com Z
distribui([X,Y|Z], [X|A], [Y|B]) :-
    distribui(Z, A, B).

% distribui(L, A, B) - A e B são as duas metades de L (alternadas)

% Caso base: lista vazia → duas listas vazias

distribui([], [], []).

% Caso base: lista com um elemento → A recebe o elemento, B fica vazio

distribui([X], [X], []).

% Passo recursivo: [X,Y|Z] → X vai para A, Y vai para B, continua com Z

distribui([X,Y|Z], [X|A], [Y|B]) :-

distribui(Z, A, B).

Explicação Passo-a-Passo

distribui([], [], []): Se a lista está vazia, ambas as sublistas estão vazias.
distribui([X], [X], []): Se a lista tem um elemento, ele vai para a primeira lista.
distribui([X,Y|Z], [X|A], [Y|B]): O primeiro elemento X vai para A, o segundo Y vai para B, e a recursão distribui o restante Z.

Exemplo de Distribuição

?- distribui([1,2,3,4,5,6], A, B).
A = [1,3,5],
B = [2,4,6].

?- distribui([a,b,c,d,e], A, B).
A = [a,c,e],
B = [b,d].

?- distribui([1,2,3,4,5,6], A, B).

A = [1,3,5],

B = [2,4,6].

?- distribui([a,b,c,d,e], A, B).

A = [a,c,e],

B = [b,d].

3. Passo 2: Intercalar — `intercala/3`

O predicado intercala/3 mescla duas listas ordenadas em uma única lista ordenada.

% intercala(A, B, C) - C é a fusão ordenada de A e B
% Caso base: A vazia → resultado é B
intercala([], B, B).

% Caso base: B vazia → resultado é A
intercala(A, [], A).

% Passo recursivo: compara as cabeças, coloca a menor primeiro
intercala([X|A], [Y|B], [X|C]) :-
    X =< Y,
    intercala(A, [Y|B], C).

intercala([X|A], [Y|B], [Y|C]) :-
    X > Y,
    intercala([X|A], B, C).

% intercala(A, B, C) - C é a fusão ordenada de A e B

% Caso base: A vazia → resultado é B

intercala([], B, B).

% Caso base: B vazia → resultado é A

intercala(A, [], A).

% Passo recursivo: compara as cabeças, coloca a menor primeiro

intercala([X|A], [Y|B], [X|C]) :-

X =< Y,

intercala(A, [Y|B], C).

intercala([X|A], [Y|B], [Y|C]) :-

X > Y,

intercala([X|A], B, C).

Explicação Passo-a-Passo

intercala([], B, B): Se A está vazia, o resultado é B.
intercala(A, [], A): Se B está vazia, o resultado é A.
intercala([X|A], [Y|B], [X|C]): Se X ≤ Y, X é colocado na frente e a intercalação continua com A e [Y|B].
intercala([X|A], [Y|B], [Y|C]): Se X > Y, Y é colocado na frente e a intercalação continua com [X|A] e B.

Exemplo de Intercalação

?- intercala([1,3,5], [2,4,6], C).
C = [1,2,3,4,5,6].

?- intercala([a,c,e], [b,d], C).
C = [a,b,c,d,e].

?- intercala([1,3,5], [2,4,6], C).

C = [1,2,3,4,5,6].

?- intercala([a,c,e], [b,d], C).

C = [a,b,c,d,e].

4. Passo 3: Ordenar — `ordena/2`

O predicado ordena/2 combina distribuição, ordenação recursiva e intercalação.

% ordena(L, S) - S é a lista L ordenada
% Caso base: lista vazia
ordena([], []).

% Caso base: lista com um elemento
ordena([X], [X]).

% Passo recursivo: divide, ordena cada parte, intercala
ordena([X,Y|Z], S) :-
    distribui([X,Y|Z], A, B),   % Divide a lista
    ordena(A, As),              % Ordena a primeira metade
    ordena(B, Bs),              % Ordena a segunda metade
    intercala(As, Bs, S).       % Intercala as duas metades ordenadas

% ordena(L, S) - S é a lista L ordenada

% Caso base: lista vazia

ordena([], []).

% Caso base: lista com um elemento

ordena([X], [X]).

% Passo recursivo: divide, ordena cada parte, intercala

ordena([X,Y|Z], S) :-

distribui([X,Y|Z], A, B), % Divide a lista

ordena(A, As), % Ordena a primeira metade

ordena(B, Bs), % Ordena a segunda metade

intercala(As, Bs, S). % Intercala as duas metades ordenadas

5. Fluxo de Execução: ordena([3,5,0,4,1,2], S)

Vamos acompanhar a execução passo a passo:

1. distribui([3,5,0,4,1,2], A, B)
   A = [3,0,1], B = [5,4,2]

2. ordena([3,0,1], As)
   a. distribui([3,0,1], A1, B1) → A1 = [3,1], B1 = [0]
   b. ordena([3,1], As1)
      - distribui([3,1], A2, B2) → A2 = [3], B2 = [1]
      - ordena([3], [3])
      - ordena([1], [1])
      - intercala([3], [1], S1) → S1 = [1,3]
   c. ordena([0], [0])
   d. intercala([1,3], [0], As) → As = [0,1,3]

3. ordena([5,4,2], Bs)
   a. distribui([5,4,2], A3, B3) → A3 = [5,2], B3 = [4]
   b. ordena([5,2], Bs1)
      - distribui([5,2], A4, B4) → A4 = [5], B4 = [2]
      - ordena([5], [5])
      - ordena([2], [2])
      - intercala([5], [2], S2) → S2 = [2,5]
   c. ordena([4], [4])
   d. intercala([2,5], [4], Bs) → Bs = [2,4,5]

4. intercala([0,1,3], [2,4,5], S)
   S = [0,1,2,3,4,5]

1. distribui([3,5,0,4,1,2], A, B)

A = [3,0,1], B = [5,4,2]

2. ordena([3,0,1], As)

a. distribui([3,0,1], A1, B1) → A1 = [3,1], B1 = [0]

b. ordena([3,1], As1)

- distribui([3,1], A2, B2) → A2 = [3], B2 = [1]

- ordena([3], [3])

- ordena([1], [1])

- intercala([3], [1], S1) → S1 = [1,3]

c. ordena([0], [0])

d. intercala([1,3], [0], As) → As = [0,1,3]

3. ordena([5,4,2], Bs)

a. distribui([5,4,2], A3, B3) → A3 = [5,2], B3 = [4]

b. ordena([5,2], Bs1)

- distribui([5,2], A4, B4) → A4 = [5], B4 = [2]

- ordena([5], [5])

- ordena([2], [2])

- intercala([5], [2], S2) → S2 = [2,5]

c. ordena([4], [4])

d. intercala([2,5], [4], Bs) → Bs = [2,4,5]

4. intercala([0,1,3], [2,4,5], S)

S = [0,1,2,3,4,5]

Consulta Completa

?- ordena([3,5,0,4,1,2], S).
S = [0,1,2,3,4,5].

?- ordena([5,2,8,1,9,3], S).
S = [1,2,3,5,8,9].

?- ordena([], S).
S = [].

?- ordena([7], S).
S = [7].

?- ordena([3,5,0,4,1,2], S).

S = [0,1,2,3,4,5].

?- ordena([5,2,8,1,9,3], S).

S = [1,2,3,5,8,9].

?- ordena([], S).

S = [].

?- ordena([7], S).

S = [7].

6. Árvore de Recursão do Merge Sort

Visualize a árvore de recursão para ordena([3,5,0,4,1,2], S):

                    [3,5,0,4,1,2]
                    /           \
              [3,0,1]           [5,4,2]
              /     \           /     \
           [3,1]   [0]       [5,2]   [4]
           /   \             /   \
        [3]   [1]         [5]   [2]
         |     |           |     |
        [3]   [1]         [5]   [2]
           \   /             \   /
          [1,3]             [2,5]
              \             /
            [0,1,3]     [2,4,5]
                 \     /
              [0,1,2,3,4,5]

[3,5,0,4,1,2]

/ \

[3,0,1] [5,4,2]

/ \ / \

[3,1] [0] [5,2] [4]

/ \ / \

[3] [1] [5] [2]

| | | |

[3] [1] [5] [2]

\ / \ /

[1,3] [2,5]

\ /

[0,1,3] [2,4,5]

\ /

[0,1,2,3,4,5]

7. Análise de Complexidade

O Merge Sort tem complexidade:

Tempo: O(n log n) no pior caso, médio e melhor caso.
Espaço: O(n) para armazenar as sublistas durante a intercalação.

Em Prolog, a implementação é particularmente elegante porque:

A recursão natural do Prolog se alinha perfeitamente com a estrutura do algoritmo.
A unificação simplifica a distribuição e intercalação.
O código é declarativo e fácil de ler.

8. Exercícios Propostos

Insertion Sort: Implemente o algoritmo Insertion Sort em Prolog.
Dica: Use insere/3 para inserir um elemento em uma lista ordenada.
Quick Sort: Implemente o Quick Sort em Prolog.
Dica: Use um pivô (ex: o primeiro elemento) e divida a lista em menores e maiores.
Bubble Sort: Implemente o Bubble Sort em Prolog.
Dica: Use troca_uma_vez/2 e repita até a lista ficar ordenada.
Selection Sort: Implemente o Selection Sort.
Dica: Encontre o menor elemento, remova-o e ordene o resto.
Comparação: Teste os diferentes algoritmos com listas de diferentes tamanhos e compare a eficiência em termos de tempo (use time/1).

9. Conclusão

O Merge Sort é um exemplo perfeito de como o Prolog pode expressar algoritmos complexos de forma elegante e declarativa. Com poucas linhas de código, implementamos um algoritmo eficiente de ordenação que é:

Correto: A recursão garante que todas as partes sejam ordenadas.
Eficiente: O(log n) para divisão e O(n) para intercalação.
Legível: Cada passo do algoritmo é claramente expresso em Prolog.

Dominar o Merge Sort em Prolog é um excelente exercício para entender como a recursão, a unificação e a divisão de listas se combinam para criar soluções poderosas.

Predicados Clássicos para Listas

16/07/202615/07/2026 Por antonino

As listas são a estrutura de dados mais importante em Prolog. Para manipulá-las, utilizamos predicados recursivos que exploram a natureza recursiva das listas. Neste artigo, vamos estudar os predicados mais fundamentais: membro/2, anexa/3, e alguns outros como ultimo/2, tam/2 e soma/2.

1. O Predicado membro/2 (Programa 5.2)

O predicado membro/2 verifica se um elemento pertence a uma lista. Ele tem duas cláusulas:

% membro(X, L) - X é elemento da lista L
% Caso base: X é a cabeça da lista
membro(X, [X|_]).

% Passo recursivo: X está na cauda da lista
membro(X, [_|Y]) :-
    membro(X, Y).

% membro(X, L) - X é elemento da lista L

% Caso base: X é a cabeça da lista

membro(X, [X|_]).

% Passo recursivo: X está na cauda da lista

membro(X, [_|Y]) :-

membro(X, Y).

Explicação Passo-a-Passo

Primeira cláusula: membro(X, [X|_]). — X é membro se ele é a cabeça da lista. A variável anônima _ ignora a cauda.
Segunda cláusula: membro(X, [_|Y]) :- membro(X, Y). — X é membro se ele está na cauda. Ignoramos a cabeça com _ e chamamos membro recursivamente na cauda Y.

A recursão percorre a lista elemento por elemento até encontrar X ou chegar ao fim da lista.

Usos de membro/2

1. Testar pertinência:

?- membro(3, [1, 2, 3, 4]).
true.

?- membro(5, [1, 2, 3, 4]).
false.

?- membro(3, [1, 2, 3, 4]).

true.

?- membro(5, [1, 2, 3, 4]).

false.

2. Gerar elementos da lista:

?- membro(X, [a, b, c]).
X = a ;
X = b ;
X = c ;
false.

?- membro(X, [a, b, c]).

X = a ;

X = b ;

X = c ;

false.

3. Verificar se uma lista contém todos os elementos de outra:

?- membro(X, [1, 2, 3]), membro(X, [2, 3, 4]).
X = 2 ;
X = 3 ;
false.

?- membro(X, [1, 2, 3]), membro(X, [2, 3, 4]).

X = 2 ;

X = 3 ;

false.

2. O Predicado anexa/3 (Programa 5.3)

O predicado anexa/3 (também conhecido como append/3) concatena duas listas. Ele tem dois casos:

% anexa(A, B, C) - C é a concatenação de A e B
% Caso base: concatenar a lista vazia com B resulta em B
anexa([], B, B).

% Passo recursivo: [X|A] concatenado com B é [X|C], onde C é A concatenado com B
anexa([X|A], B, [X|C]) :-
    anexa(A, B, C).

% anexa(A, B, C) - C é a concatenação de A e B

% Caso base: concatenar a lista vazia com B resulta em B

anexa([], B, B).

% Passo recursivo: [X|A] concatenado com B é [X|C], onde C é A concatenado com B

anexa([X|A], B, [X|C]) :-

anexa(A, B, C).

Explicação Passo-a-Passo

Caso base: anexa([], B, B). — Se a primeira lista é vazia, o resultado é a segunda lista.
Passo recursivo: anexa([X|A], B, [X|C]) :- anexa(A, B, C). — Remove a cabeça X da primeira lista, concatena A com B recursivamente (resultando em C), e depois coloca X de volta na frente.

Usos de anexa/3

1. Concatenar duas listas:

?- anexa([1, 2], [3, 4], R).
R = [1, 2, 3, 4].

1 2	?- anexa([1, 2], [3, 4], R). R = [1, 2, 3, 4].

2. Dividir uma lista (encontrar prefixos):

?- anexa(A, B, [a, b, c]).
A = [], B = [a, b, c] ;
A = [a], B = [b, c] ;
A = [a, b], B = [c] ;
A = [a, b, c], B = [] ;
false.

?- anexa(A, B, [a, b, c]).

A = [], B = [a, b, c] ;

A = [a], B = [b, c] ;

A = [a, b], B = [c] ;

A = [a, b, c], B = [] ;

false.

3. Encontrar o último elemento (via divisão):

?- anexa(_, [X], [a, b, c, d]).
X = d.

1 2	?- anexa(_, [X], [a, b, c, d]). X = d.

4. Remover um elemento (encontrando o que está antes e depois):

?- anexa(A, [b|B], [a, b, c]).
A = [a], B = [c].

1 2	?- anexa(A, [b\|B], [a, b, c]). A = [a], B = [c].

3. Exercícios do PDF (5.1, 5.2, 5.3)

Exercício 5.1: último/2

Problema: Encontrar o último elemento de uma lista.

% ultimo(L, X) - X é o último elemento da lista L
% Caso base: lista com um único elemento
ultimo([X], X).

% Passo recursivo: ignorar a cabeça e continuar na cauda
ultimo([_|T], X) :-
    ultimo(T, X).

% ultimo(L, X) - X é o último elemento da lista L

% Caso base: lista com um único elemento

ultimo([X], X).

% Passo recursivo: ignorar a cabeça e continuar na cauda

ultimo([_|T], X) :-

ultimo(T, X).

Como funciona: A recursão percorre a lista até chegar ao último elemento, que é retornado.

?- ultimo([1, 2, 3, 4], X).
X = 4.

?- ultimo([a, b, c], X).
X = c.

?- ultimo([], X).
false.

?- ultimo([1, 2, 3, 4], X).

X = 4.

?- ultimo([a, b, c], X).

X = c.

?- ultimo([], X).

false.

Exercício 5.2: tam/2

Problema: Calcular o tamanho (comprimento) de uma lista.

% tam(L, N) - N é o número de elementos da lista L
% Caso base: lista vazia tem tamanho 0
tam([], 0).

% Passo recursivo: tamanho = 1 + tamanho da cauda
tam([_|T], N) :-
    tam(T, N1),
    N is N1 + 1.

% tam(L, N) - N é o número de elementos da lista L

% Caso base: lista vazia tem tamanho 0

tam([], 0).

% Passo recursivo: tamanho = 1 + tamanho da cauda

tam([_|T], N) :-

tam(T, N1),

N is N1 + 1.

Como funciona: A cada chamada recursiva, removemos a cabeça da lista (ignorando-a com _) e adicionamos 1 ao resultado da chamada recursiva.

?- tam([1, 2, 3, 4], N).
N = 4.

?- tam([a, b, c, d, e], N).
N = 5.

?- tam([], N).
N = 0.

?- tam([1, 2, 3, 4], N).

N = 4.

?- tam([a, b, c, d, e], N).

N = 5.

?- tam([], N).

N = 0.

Exercício 5.3: soma/2

Problema: Calcular a soma dos elementos de uma lista de números.

% soma(L, S) - S é a soma dos elementos da lista L
% Caso base: soma da lista vazia é 0
soma([], 0).

% Passo recursivo: soma = cabeça + soma da cauda
soma([H|T], S) :-
    soma(T, S1),
    S is H + S1.

% soma(L, S) - S é a soma dos elementos da lista L

% Caso base: soma da lista vazia é 0

soma([], 0).

% Passo recursivo: soma = cabeça + soma da cauda

soma([H|T], S) :-

soma(T, S1),

S is H + S1.

Como funciona: Percorre a lista recursivamente, somando a cabeça ao resultado da cauda.

?- soma([1, 2, 3, 4], S).
S = 10.

?- soma([5, 10, 15], S).
S = 30.

?- soma([], S).
S = 0.

?- soma([1, 2, 3, 4], S).

S = 10.

?- soma([5, 10, 15], S).

S = 30.

?- soma([], S).

S = 0.

4. Recursão e Listas: O Padrão Fundamental

Todos os predicados que vimos seguem o mesmo padrão:

% Padrão geral para predicados de listas
pred([], ...).          % Caso base: lista vazia
pred([H|T], ...) :-    % Passo recursivo: processa a cabeça H e chama pred na cauda T
    pred(T, ...).       % A cauda T é uma lista menor

% Padrão geral para predicados de listas

pred([], ...). % Caso base: lista vazia

pred([H|T], ...) :- % Passo recursivo: processa a cabeça H e chama pred na cauda T

pred(T, ...). % A cauda T é uma lista menor

Esse padrão é universal em Prolog para manipulação de listas. A recursão percorre a lista até o fim, processando cada elemento (ou acumulando resultados) e depois retorna o resultado combinado.

5. Exercícios Adicionais

Pratique com estes desafios:

maximo/2: Encontre o maior elemento de uma lista de números.
Dica: Caso base: lista com um elemento. Passo: compare a cabeça com o máximo da cauda.
minimo/2: Encontre o menor elemento de uma lista de números.
remover/3: remover(X, L, R) — R é a lista L sem a primeira ocorrência de X.
Dica: Use anexa/3 para encontrar X e construir o resultado.
remover_todos/3: Remova todas as ocorrências de X da lista L.
inverter/2: inverter(L, R) — R é a lista L invertida.
Dica: Use anexa/3 para construir a lista invertida.
pertence_todos/2: pertence_todos(Xs, Ys) — todos os elementos de Xs estão em Ys.

6. Conclusão

As listas são a estrutura de dados fundamental em Prolog. Através da notação cabeça-cauda [X|Y] e da recursão, podemos implementar uma vasta gama de operações:

Busca: membro/2
Combinação: anexa/3
Medidas: tam/2, soma/2, ultimo/2
Transformações: inverter/2, remover/3

Dominar esses predicados fundamentais é o primeiro passo para se tornar um programador Prolog proficiente. Pratique com os exercícios e explore como a recursão pode ser aplicada a problemas cada vez mais complexos.

1. O Paradigma “Dividir para Conquistar”

2. Passo 1: Distribuir — distribui/3 (Programa 5.4)

Explicação Passo-a-Passo

Exemplo de Distribuição

3. Passo 2: Intercalar — intercala/3

Explicação Passo-a-Passo

Exemplo de Intercalação

4. Passo 3: Ordenar — ordena/2

5. Fluxo de Execução: ordena([3,5,0,4,1,2], S)

Consulta Completa

6. Árvore de Recursão do Merge Sort

7. Análise de Complexidade

8. Exercícios Propostos

9. Conclusão

1. O Predicado membro/2 (Programa 5.2)

Explicação Passo-a-Passo

Usos de membro/2

2. O Predicado anexa/3 (Programa 5.3)

Explicação Passo-a-Passo

Usos de anexa/3

3. Exercícios do PDF (5.1, 5.2, 5.3)

Exercício 5.1: último/2

Exercício 5.2: tam/2

Exercício 5.3: soma/2

4. Recursão e Listas: O Padrão Fundamental

5. Exercícios Adicionais

6. Conclusão

2. Passo 1: Distribuir — `distribui/3` (Programa 5.4)

3. Passo 2: Intercalar — `intercala/3`

4. Passo 3: Ordenar — `ordena/2`