Programando en Prolog: Recursividad

La recursividad en Prolog es una técnica donde un predicado se define a sí mismo para resolver un problema complejo dividiéndolo en casos más pequeños.

Se llama recursividad por que se llama sí mismo para repetir una tarea o recorrer estructuras de datos, ya que el lenguaje no cuenta con bucles tradicionales como for o while.

Recursividad en Prolog

Un predicado recursivo es aquel que en alguna de sus cláusulas se invoca a sí mismo. Los predicados recursivos para poder funcionar correctamente necesitan contar con algún caso base que corte la recursividad.

Estructura recursiva en Prolog

Toda estructura recursiva en Prolog consta de dos partes esenciales:

1. El caso base: Un hecho o regla simple que se cumple de inmediato y detiene la recursión. 
2. El caso recursivo: Una regla que realiza una operación y se llama a sí misma con un problema más pequeño.

Factorial en Prolog

El clásico ejemplo para entender la recursividad es el programa para obtener el factorial de un número.

factorial.pl

factorial(0,1).
factorial(N,F):- 
  Anterior is N-1,
  factorial(Anterior,F2),
  F is F2*N.

Este programa cumple con la estructura recursiva al contar con un caso base y la regla que realiza la operación y se llama a así misma.

Entramos al REPL:

$ swipl

Cargamos el programa:

1 ?- [factorial].                                                                  true.  

Hacemos una consulta:

2 ?- factorial(5,X).
X = 120 .

La entrada fue 5 y el resultado de la consulta fue 120, lo cual es una respuesta correcta.

Podríamos extender el tema al uso de listas y otras estructuras pero por el momento es todo.

Continuaremos con este tema en próximas entregas.

Enlaces:

https://swish.swi-prolog.org/p/ExpoPrologLP.swinb
https://wiki.uqbar.org/wiki/articles/recursividad-en-logico.html
Recursividad en Prolog (Youtube)