Inteligencia Artificial: Prolog
Recursión
Christopher Expósito-Izquierdo1 ,
Belén Melián-Batista2
{cexposit1 , mbmelian2 }@[Link]
Universidad de La Laguna (España)
Contenidos
Concepto de Recursión
Recursión en Prolog
Ejemplo de Recursión
El predicado fibonacci
El predicado maximum
2 of 17
Concepto de Recursión
La recursión es la manera en la que la especificación de un determinado
proceso del mundo real se basa en sı́ misma
Muchos problemas tienen definiciones intrı́nsecamente recursivas.
Algunos ejemplos son los siguientes:
Torres de Hanoi
Secuencia de Fibonacci
Máximo común divisor
Número factorial
...
3 of 17
Recursión en Prolog
La recursión es una herramienta de suma importancia en Prolog para
la definición de predicados. En Prolog podemos encontrar, en general,
dos tipos de recursión:
Recursión directa. Un cierto predicado pred está definido en base
a sı́ mismo
Recursión indirecta. Un determinado predicado pred1 está definido
en base al predicado pred2, el cual a su vez está definido en base
al predicado pred3,... el cual está definido en base al predicado
pred1
4 of 17
Ejemplo de Recursión
A continuación veamos cómo definir relaciones de parentesco entre
personas de una forma recursiva. Comenzamos definiendo un
conjunto de hechos simples:
padre(marcos, antonio).
padre(antonio, sandra).
padre(luis, marcos).
padre(luis, andrea).
padre(luis, nuria).
Ahora podemos definir las siguientes reglas:
ascendiente(X, Y) :- padre(X, Y).
ascendiente(X, Y) :- padre(X, Z), ascendiente(Z, Y).
5 of 17
Ejemplo de Recursión
La base de conocimiento la guardamos en un fichero de texto
denominado [Link]. Este fichero debe ser cargado
en el intérprete antes de poder emplear sus predicados. A
continuación podemos ver ejemplos del uso:
6 of 17
El predicado fibonacci
Objetivo: calcular la sucesión de Fibonacci. Esta sucesión viene definida
por la siguiente expresión matemática:
0 if n = 0
fib(n) = 1 if n = 1
fib(n − 2) + fib(n − 1) if n > 1
El predicado propuesto debe tener dos argumentos:
1. El número n
2. El resultado de la sucesión para el número n establecido como
primer argumento
7 of 17
El predicado fibonacci
El elemento de la sucesión de Fibonacci cuando n = 0 es 0.
Se puede expresar en Prolog con el siguiente hecho:
fib(0, 0).
8 of 17
El predicado fibonacci
Al igual que en el caso anterior, el elemento de la sucesión de
Fibonacci cuando n = 1 es 1.
Se puede expresar en Prolog con el siguiente hecho:
fib(1, 1).
9 of 17
El predicado fibonacci
El elemento de la sucesión de Fibonacci cuando n > 1 se calcula
como la suma de los elementos de la sucesión de Fibonacci para n − 2
y n − 1. Por tanto, en primer lugar hay que comprobar que n toma un
valor mayor que 1, calcular los elementos de la sucesión de Fibonacci
para n − 2 y n − 1 y finalmente sumarlos.
Se puede expresar en Prolog con la siguiente regla:
fib(X, Y) :- X > 1, X1 is X - 1, X2 is X - 2, fib(X1,
Y1), fib(X2, Y2), Y is Y1 + Y2.
10 of 17
El predicado fibonacci
La definición del predicado fibonacci la guardamos en un fichero de
texto denominado [Link]. Este fichero debe ser
cargado en el intérprete antes de poder emplear el predicado. A
continuación podemos ver ejemplos del uso:
11 of 17
El predicado maximum
Objetivo: calcular el máximo común divisor de dos números. El máximo
común divisor de dos números x e y viene definido por la siguiente
expresión matemática:
x if y = 0
mcd(x, y ) =
mcd(y , mod(x, y )) if y > 0 ∧ x ≥ y
El predicado propuesto debe tener tres argumentos:
1. El primero de los números cuyo máximo común divisor se desea
calcular
2. El segundo de los números cuyo máximo común divisor se desea
calcular
3. El máximo común divisor de los números anteriormente definidos
12 of 17
El predicado maximum
El máximo común divisor de dos números iguales es ese mismo
número.
Se puede expresar en Prolog con el siguiente hecho:
maximum(X, X, X).
13 of 17
El predicado maximum
Si el número x es menor que y se calcula el máximo común divisor de
x y la resta y − x.
Se puede expresar en Prolog con la siguiente regla:
maximum(X, Y, Z) :- X < Y, Y1 is Y - X, maximum(X, Y1,
Z).
14 of 17
El predicado maximum
Finalmente, si el número x es mayor que y se calcula el máximo
común divisor de y y x.
Se puede expresar en Prolog con la siguiente regla:
maximum(X, Y, Z) :- X > Y, maximum(Y, X, Z).
15 of 17
El predicado maximum
La definición del predicado maximum la guardamos en un fichero de
texto denominado [Link]. Este fichero debe ser
cargado en el intérprete antes de poder emplear el predicado. A
continuación podemos ver ejemplos del uso:
16 of 17
Inteligencia Artificial: Prolog
Recursión
Christopher Expósito-Izquierdo1 ,
Belén Melián-Batista2
{cexposit1 , mbmelian2 }@[Link]
Universidad de La Laguna (España)
17 of 17
