Prolog/Recursão

Origem: Wikilivros, livros abertos por um mundo aberto.

[editar] 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.

Um exemplo de regra recursiva seria a definição de uma base de dados sobre relações familiares que responda questões sobre ancestralidade. Isto pode ser definido da seguinte forma:

ancestral(X,Y) :- mãe(X,Y).
ancestral(X,Y) :- pai(X,Y).
ancestral(X,Y) :- mãe(X,Z),ancestral(Z,Y).
ancestral(X,Y) :- pai(X,Z),ancestral(Z,Y).

Além disso, é necessário tomar cuidado com a ordem na qual unificações(ver Unificação em Prolog) são procurados para objetivos. Se invertermos a ordem nas regras recursivas do predicado ancestral, isto é

ancestral(X,Y) :- ancestral(Z,Y),mãe(X,Z).
ancestral(X,Y) :- ancestral(Z,Y),pai(X,Z).

a consulta resultará uma recursão infinita.

Outro exemplo mais concreto seria:

nascido(curitiba, joão). nascido(paris, jean). cidade(curitiba, paraná). cidade(paris, frança). naturalidade(X,Y):- nascido(K,Y), cidade(K,X).

universo(venus, perto_n_possui_cauda). universo(cometa, perto_possui_cauda). astros(venus, venus). astros(cometa, cometa).

espaco(X,Y):- universo(K,Y), astros(K,X).

[editar] 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.

[editar] 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).

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)