A recursividade é um dos conceitos mais fundamentais e poderosos da programação — e em Prolog, ela é ainda mais natural, pois a linguagem foi projetada para suportar definições recursivas de forma elegante. O princípio é simples: resolver um problema usando uma instância menor (mais simples) dele mesmo. Para que isso funcione, precisamos de dois elementos essenciais: um caso base (que para a recursão) e um passo recursivo (que reduz o problema e chama a si mesmo).
Exemplo Matemático: Potência (Programa 4.1)
Vamos calcular potência: \( B^N \) (base elevada ao expoente). Sabemos que:
- Caso base: \( B^0 = 1 \) (qualquer número elevado a 0 é 1).
- Passo recursivo: \( B^N = B \times B^{N-1} \) (para N > 0).
% pot(Base, Expoente, Resultado)
% Caso base: qualquer base elevada a 0 é 1
pot(_, 0, 1).
% Passo recursivo: B^N = B * B^(N-1)
pot(B, N, P) :-
N > 0,
M is N - 1,
pot(B, M, R),
P is B * R.Estrutura de um Predicado Recursivo
Observe a estrutura:
- Caso base:
pot(_, 0, 1).— a condição mais simples, que não chama a si mesmo. - Passo recursivo:
pot(B, N, P) :- N > 0, M is N-1, pot(B, M, R), P is B * R.— reduz o problema (N diminui), chama recursivamente e depois combina o resultado.
A guarda N > 0 garante que a recursão não seja chamada com expoente negativo,
evitando loops infinitos.
Fluxo de Execução: pot(2, 3, P)
Veja como o Prolog processa a consulta passo a passo:
• O Prolog expande as chamadas recursivas até atingir o caso base.
• Depois, retorna os resultados de baixo para cima, combinando os valores.
• No final,
P é unificado com 8 (que é \(2^3\)).
Exemplo do Fatorial (Programa 4.2)
O fatorial é outro exemplo clássico:
% fat(N, F) → F = N!
% Caso base: 0! = 1
fat(0, 1).
% Passo recursivo: N! = N * (N-1)!
fat(N, F) :-
N > 0,
M is N - 1,
fat(M, R),
F is N * R.A estrutura é idêntica à da potência: um caso base (0! = 1) e um passo recursivo que reduz N até chegar a 0.
A Hipótese da Recursividade
Ao escrever um predicado recursivo, você faz uma suposição fundamental:
assumir que a chamada recursiva funciona corretamente para uma instância menor do problema.
Essa é a hipótese da recursividade. No caso da potência, assumimos que
pot(B, M, R) realmente calcula \( B^M \) corretamente, e então usamos esse resultado
para calcular \( B^N \). Essa confiança na chamada recursiva é o que torna a recursão poderosa
e elegante.
Exercícios Propostos
- Fibonacci: Implemente
fib(N, F)que calcula o N-ésimo termo da sequência de Fibonacci (F(0) = 0, F(1) = 1, F(N) = F(N-1) + F(N-2)). Use dois casos base. - Soma de lista: Implemente
soma_lista([], 0).esoma_lista([H|T], S) :- soma_lista(T, R), S is H + R. - Inverter lista: Crie
inverter([], []).einverter([H|T], Inv) :- inverter(T, R), append(R, [H], Inv). - Pertencimento: Implemente
membro(X, [X|_]).emembro(X, [_|T]) :- membro(X, T). - Desafio: Implemente
max_lista([X], X).emax_lista([H|T], M) :- max_lista(T, R), M is max(H, R).
Conclusão
A recursividade é o coração da programação lógica. Em Prolog, ela é expressa de forma natural através de regras que se referem a si mesmas, com um caso base que encerra a cadeia e um passo recursivo que reduz o problema. Esse padrão aparece em cálculos matemáticos (potência, fatorial), manipulação de listas, definição de estruturas de dados e muito mais. Dominar a recursividade é dominar o pensamento declarativo e estrutural que o Prolog exige. Pratique com os exercícios acima e explore a beleza da auto-referência lógica!