RECURSIVIDAD

La recursividad es un mecanismo que da bastante potencia a cualquier lenguaje de programación. Veamos un ejemplo de programación recursiva que nos permitirá determinar si un tomo es miembro de una lista dada:

(1) miembro(X,[X|_]).

(2) miembro(X,[_|Y]) :- miembro(X,Y).

La regla (1) es el caso base de la recursión. Se evaluar como cierta siempre que coincida la variable X con la cabeza de la lista que se pasa como argumento. En la regla (2) est la definición recursiva. X es miembro de una lista si lo es de la cola de esa lista (la cabeza se comprueba en la regla (1)).

La regla (1) es una simplificación de la regla:

miembro(X,[Y|_]) :- X = Y.

La traza para el caso de 'miembro(b,[a,b,c]).' es la siguiente:

(1) miembro(b,[a,b,c]) :- b = a. ---> no.

(2) miembro(b,[a,b,c]) :- miembro(b,[b,c]).

(1) miembro(b,[b,c]) :- b = b. ---> yes.

Si necesitamos conocer la longitud de una lista, emplearemos una función recursiva como la siguiente:

longitud([],0).

longitud([_|Y],L1) :- longitud(Y,L2), L1 is L2 + 1.