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
editarConsiderando 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
editarA 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
editarUma função 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: - é algum tipo de condição sobre o valor de ; - são funções definidas com um argumento não definido na função .
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
editarRecursã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).