Recursividad en prolog

Hoy les comparto un mini tutorial acerca de recursividad en prolog.

¿Qué es la recursividad?

Es la técnica utilizada en la programación que consiste en un bloque de instrucciones se llame a si mismo para resolver una parte mas pequeña del problema inicial.

Sabiendo lo anterior, comencemos. Les explicare la recursividad en prolog con un ejemplo muy conocido en la recursividad, como lo es obtener el factorial de un número.

factorial(0,1).
factorial(N,F) :-
N>0,
N1 is N-1,
factorial(N1,F1),
F is N * F1.

La recursividad se compone de dos elemento:

  • Caso base: La solución para un caso particular, en el ejemplo anterior el caso base es: factorial(0,1). Donde cada que se reciba un 0, nos retornara como resultado un 1, esto es un valor que ya se encuentra establecido.
  • Caso recursivo: Consiste en utilizar la misma operación, pero tratando de llegar al caso base, que es donde se detendrá la recursividad, en este ejemplo el caso recursivo es el resto.

Y ahora, como funciona la funciona recursiva del factorial:

Ejemplo:

Si se recibe: factorial(5,X).

X sera el valor que retornara nuestra función.

5>0, por lo tanto a la variable “N1” se le asigna el valor 4 o “N-1”. Posteriormente se vuelve a llamar a la función pero se le manda la variable “N1” como parámetro y se recibirá el valor en la variable “F1”. Y por ultimo se asigna a la variable F=5*F1, donde F1, es el valor que nos retornara la recursividad.

La nueva función recibe el valor 4, 4>0, por lo tanto a la variable “N1” se le asigna el valor 3 o “N-1”. Posteriormente se vuelve a llamar a la función pero se le manda la variable “N1” como parámetro y se recibirá el valor en la variable “F1”. Y por ultimo se asigna a la variable F=4*F1, donde F1, es el valor que nos retornara la recursividad.

La nueva función recibe el valor 3, 3>0 por lo tanto a la variable “N1” se le asigna el valor 2 o “N-1”. Posteriormente se vuelve a llamar a la función pero se le manda la variable “N1” como parámetro y se recibirá el valor en la variable “F1”. Y por ultimo se asigna a la variable F=3*F1, donde F1, es el valor que nos retornara la recursividad.

La nueva función recibe el valor 2, 2>0 por lo tanto a la variable “N1” se le asigna el valor 1 o “N-1”. Posteriormente se vuelve a llamar a la función pero se le manda la variable “N1” como parámetro y se recibirá el valor en la variable “F1”. Y por ultimo se asigna a la variable F=2*F1, donde F1, es el valor que nos retornara la recursividad.

La nueva función recibe el valor 1, 1>0 por lo tanto a la variable “N1” se le asigna el valor 0 o “N-1”. Posteriormente se vuelve a llamar a la función pero se le manda la variable “N1” como parámetro y se recibirá el valor en la variable “F1”. Y por ultimo se asigna a la variable F=1*F1, donde F1, es el valor que nos retornara la recursividad.

Y por ultimo se recibe el valor “0” que es nuestro caso base, por lo tanto de manera automática se retorna el valor 1 como resultado, dentro de la variable “F1”, se recibe en la función anterior y F=1*1, y se manda como resultado a la función anterior en la variable “F1”, se recibe en la función anterior y F=2*1, y se manda como resultado a la función anterior en la variable “F1”, se recibe en la función anterior y F=3*2, y se manda como resultado a la función anterior en la variable “F1”, se recibe en la función anterior y F=4*6, y se manda como resultado a la función anterior (la función inicial) en la variable “F1”, se recibe en la función inicial y F=5*24, por lo tanto F=120. Y este es el valor que se retorna como resultado al usuario en la variable F, que el usuario recibirá dentro de la variable X. como se muestra en el caso siguiente.

Consulta con el valor 5.
Consulta con el valor 5.

Y con esto concluiría nuestro mini tutorial acerca de recursividad en prolog. Espero y les sirva y sea de su agrado. Cualquier cosa no duden en comentarla y de antemano muchas gracias.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s