Prolog/Recursão

Regras recursivas devem ser permitidas a fim de tornar a linguagem útil para muitas aplicações. Um predicado definido por uma regra recursiva deve necessariamente ter, no mínimo uma definição não recursiva. Se isto não acontecer, a definição é logicamente mal-formada e o programa ficaria em laço infinito.

Motivação

Considerando o seguinte programa:

 pai(david, john).
 pai(jim, david).
 pai(steve, jim).
 pai(nathan, steve).

 avo(A, B) :- pai(A, X), pai(X, B).

seria interessante poder definir ancestral(X, Y). Uma forma não-recursiva seria impraticável, pois seria necessário incluir todas as possíveis gerações:

 ancestor(A,B) :- pai(A, B).
 ancestor(A,B) :- pai(A, X), pai(X, B).
 ancestor(A,B) :- pai(A, X), pai(X, Y), pai(Y, B).
 ancestor(A,B) :- pai(A, X), pai(X, Y), pai(Y, Z), pai(Z,B).
% continue escrevendo - e ainda falta incluir as mães!

Claramente, este programa não é elegante.

Recursão - primeiro exemplo

A implementação da regra sobre ancestralidade usando recursão é muito mais simples e elegante:

 ancestral(X,Y) :- mae(X,Y).
 ancestral(X,Y) :- pai(X,Y).
 ancestral(X,Y) :- mae(X,Z), ancestral(Z,Y).
 ancestral(X,Y) :- pai(X,Z), ancestral(Z,Y).

Deve-se tomar cuidado com a ordem na qual unificações são procurados para objetivos. Se invertermos a ordem nas regras recursivas do predicado ancestral, isto é

 ancestral(X,Y) :- ancestral(Z,Y), mae(X,Z).
 ancestral(X,Y) :- ancestral(Z,Y), pai(X,Z).

a consulta resultará uma recursão infinita.

Recursão em cauda

Uma função $f$ pode ser definida por recursão em cauda da seguinte maneira:

f(x): se c(x) então g(x) senão f(h(x))

onde: - $c(x)$ é algum tipo de condição sobre o valor de $x$; - $g(x),h(x)$ são funções definidas com um argumento não definido na função $f$.

A mesma sentença pode ser escrita em Prolog desta forma:

 f(X, Z) :- c(X), g(X, Z).
 f(X, Z) :- h(X, Y), f(Y, Z).

Recursão em cauda é importante e preferível sobre recursão não cauda pois pode ser implementada como uma iteração que é computada usando uma pilha estática.

Recursão não em cauda

Recursão não em cauda pode ser definida pela sentença

f(x): se c(x) então g(x) senão k(x, f(h(x)))

Isto significa que o valor da chamada de recursão é modificado após sua computação. Em Prolog, esta função pode ser implementada assim:

 f(X, Y) :- c(X), g(X, Y).
 f(X, Y) :- h(X, X1), f(X1, Y1), k(X, Y1, Y).

Recursão em não cauda usa um espaço linear na pilha, conseqüentemente evitado caso não seja necessário. Em alguns casos é possível otimizar a implementação. Considere o esquema:

f(n): se n = 0 então a senão k(n, f(n - 1))

Isto pode ser escrito em Prolog usando recursão não em cauda:

 f(0, a).
 f(X, Y) :- X1 is X - 1, f(X1, Y1), k(X, Y1, Y).

(is/2 é a forma de fazer atribuições aritméticas: isto será visto no capítulo Prolog/Matemática). Este código requer espaço linear na pilha para guardar resultados temporários de chamadas recursivas. Usando um acumulador, o código abaixo pode ser escrito usando recursão em cauda:

 f(X, Y) :- f(X, 1, a, Y).
 f(X, M, ACC, ACC) :- M > N.
 f(X, M, ACC, Y) :- M <= N, k(M, ACC, ACC1), M1 is M + 1, f(N, M1, ACC1, Y).

(de novo, estamos usando conceitos matemáticos, no caso os predicados '>'/2 e '<='/2, que serão vistos no capítulo Prolog/Matemática).