O Princípio da Recursividade

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 * B^(N-1) (para N > 0).

Estrutura de um Predicado Recursivo

Observe a estrutura:

1. Caso base: pot(_, 0, 1). — a condição mais simples, que não chama a si mesmo.
2. 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:

Interpretação:

• 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:

A estrutura é idêntica à da potência: um caso base (0! = 1) e um passo recursivo que reduz N até chegar a 0.

Fluxo para fat(3, F):

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.

Importante: A condição de parada (caso base) é obrigatória para evitar recursão infinita. Sem ela, o Prolog entraria em um loop até estourar a pilha de chamadas. A guarda N > 0 no passo recursivo garante que nunca chamaremos pot com um expoente negativo.

Exercícios Propostos

1. 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.
2. Soma de lista: Implemente soma_lista([], 0). e soma_lista([H|T], S) :- soma_lista(T, R), S is H + R.
3. Inverter lista: Crie inverter([], []). e inverter([H|T], Inv) :- inverter(T, R), append(R, [H], Inv).
4. Pertencimento: Implemente membro(X, [X|_]). e membro(X, [_|T]) :- membro(X, T).
5. Desafio: Implemente max_lista([X], X). e max_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!

---