Recursividad y Programación Lógica

Recursividad y Programación Lógica

Resumen—En este artículo se complementa con ejemplos la metodología expuesta por Raja Sooriamurthi [1] para la construcción y desarrollo de algoritmos recursivos. Estos ejemplos permiten apreciar la sencillez y belleza de esta metodología.

I. RECURSIVIDAD

En esta sección se va a demostrar que la recursividad puede ser tratada con mucha más facilidad si se piensa en que hace el algoritmo y no en como lo hace. Para lograr este objetivo se va a hacer uso de la modularidad.

A. Dividir y Conquistar

Un problema puede ser resuelto utilizando modularidad, la cual se consigue con la simple idea de dividir y conquistar.

La estrategia de dividir y conquistar establece:

1. Dividir un problema grande en piezas pequeñas

2. Resolver las piezas pequeñas

3. Combinar las soluciones

Por ejemplo, si consideramos el caso de comprar un auto, el problema puede dividirse en otros dos:

a. buscar el auto que uno quiere

b. conseguir financiamiento

En este caso se ha dividido un problema grande en dos subproblemas, cada uno posiblemente de diferentes tipos.

La recursión es un caso especial de dividir y conquistar donde los subproblemas individuales son del mismo tipo. De manera figurativa, para resolver un cuadrado no se debe dividir en un pequeño triángulo y un pequeño óvalo sino en pequeños cuadrados.

Los siguientes pasos son muy útiles al momento de diseñar un algoritmo recursivo.

B. Caso Base.- La más pequeña instancia del problema para la cual conocemos la respuesta sin mayor esfuerzo. Para ello se necesitan dos elementos

- Un test para reconocer el caso base

- Una respuesta para el caso base

C. Simplificación de la Rutina.- Algo que nos ayude a encoger el tamaño del problema hacia el caso base.

D. Recursión Natural.- Expresa una llamada recursiva de la función a la versión simplificada del problema

E. Completación.- Dada la solución es necesario preguntar que es lo que se necesita hacer con la respuesta de la llamada recursiva para formar la respuesta del problema original. Es necesario pensar en cual es la respuesta que da la llamada recursiva y evitar preguntar como funciona.

El siguiente ejemplo aclara el procedimiento descrito.

Ejemplo 5.- Sumar los dígitos de un número entero

Solución.- Para simplificar el análisis del problema es aconsejable utilizar un caso específico y no así el caso más general.

Para el ejemplo utilizamos el número 2368 = 2+3+6+8 = 20

a. Caso base.- La solución es trivial, para los enteros de un solo dígito.

- Test: n < 10

- Respuesta: n

b. Simplificación de la rutina.- Se necesita dividir el problema en subproblemas del mismo tipo, y existen varias maneras de hacer esto:

2 368 = 2 + (3+6+8)

23 68 = (2+3) + (6+8)

236 8 = (2+3+6) + 8

Cada una de las divisiones debería funcionar en teoría, es así que la atención debería centrarse en cual de ellas es más fácil de implementar en la práctica. En nuestro caso utilizaremos la tercera opción.

c. Recursión Natural.- Este es un paso mecánico que no requiere de mucha reflexión

sumarDigitos(236) = sumarDigitos(N/10)

donde ‘/ ‘denota la división entera.

d. Completación.- Asumiendo que conocemos la respuesta a la recursión natural, necesitamos saber qué más debe ser hecho para determinar la respuesta final.

En la recursión natural sumarDigitos(236) deberá dar 12 como respuesta. Dado este valor necesitamos adicionar el primer dígito (8) para obtener la respuesta final. La completación es:

sumarDigitos(N/10) + n%10

donde ‘%' es el operador módulo.

e. Solución Prolog.- Poniendo todo junto y utilizando Prolog como lenguaje de programación, obtenemos la siguiente solución:

sumarDigitos((N,N):- N < 10;

sumarDigitos(N,S):- N <= 10, N1 is N/10,

N2 is mod(N,10),

sumarDigitos(N1, X),

S is X + N2;

La primera línea devuelve el mismo número si este es menor a 10.

En la segunda línea N1 es igual a los dígitos de N excluyendo el primero, y N2 es igual al primer dígito. X es el resultado de aplicar la función a los dígitos de N1 y finalmente el resultado S es igual al obtenido en X más N2.

Aquí se puede ver como funciona el algoritmo, se supone que la función sumarDigitos devuelve la suma de los dígitos del número que es introducido, y como sabemos que esto funciona confiamos en que la función nos devolverá el resultado correcto cuando introducimos N1. Es decir que sabemos que es lo que hace la función pero ignoramos como lo hace.

II. PROBLEMAS RESUELTOS

A continuación se resuelven varios problemas utilizando el método descrito.

A. Calcular el factorial de un número natural N.

Solución.-

a. Caso base.- El caso base se da cuando N = 0. Para esta situación el factorial es 1.

- Test: N= 0

- Respuesta: 1

b. Simplificación de la rutina.- Supongamos que queremos encontrar el factorial de 6, para ello podemos dividir el problema en subproblemas del mismo tipo

6! = 1*2*3*4*5*6

Algunas posibles subdivisiones del problema son:

1 23456 = 1*(2*3*4*5*6)

12 3456 = (1*2*3)*(4*5*6)

123 456 = (1*2*3*4*5)*6

Si elegimos la tercera opción obtenemos 6! = 5!*6

//

c. Recursión Natural.-

factorial(5) = factorial(N-1)

d. Completación.- Conociendo la respuesta de la recursión natural el resultado debe multiplicarse por N. La completación es:

factorial(N-1)*N

e. Solución Prolog.-

factorial(0,1);

factorial(N,F):- factorial(N-1,R),

F is N*R;

B. Calcular el N-ésimo término de la serie de Fibonacci

Solución.-

a. Caso Base.- El fibonacci de 0 es 1, y el fibonacci

...