Recursividad

2. Recursividad.
3. Propiedades de las definiciones o algoritmos recursivos.
4. Cadenas recursivas.
5. Definición recursiva de expresiones algebraicas.
6. Programación Recursiva.
7. Asignación estática y dinámica de memoria.
8. Ejemplos.
9. Conclusión.
10. Bibliografía.

INTRODUCCIÓN

El área de la programación es muy amplia y con muchos detalles. Los programadores necesitan ser capaces de resolver todos los problemas que se les presente a través del computador aun cuando en el lenguaje que utilizan no haya una manera directa de resolver los problemas. En el lenguaje de programación C, así como en otros lenguajes de programación, se puede aplicar una técnica que se le dio el nombre de recursividad por su funcionalidad. Esta técnica es utilizada en la programación estructurada para resolver problemas que tengan que ver con el factorial de un número, o juegos de lógica. Las asignaciones de memoria pueden ser dinámicas o estáticas y hay diferencias entre estas dos y se pueden aplicar las dos en un programa cualquiera.

1.-Recursividad:

La recursividad es una técnica de programación importante. Se utiliza para realizar una llamada a una función desde la misma función. Como ejemplo útil se puede presentar el cálculo de números factoriales. Él factorial de 0 es, por definición, 1. Los factoriales de números mayores se calculan mediante la multiplicación de 1 * 2 * …, incrementando el número de 1 en 1 hasta llegar al número para el que se está calculando el factorial.

El siguiente párrafo muestra una función, expresada con palabras, que calcula un factorial.

"Si el número es menor que cero, se rechaza. Si no es un entero, se redondea al siguiente entero. Si el número es cero, su factorial es uno. Si el número es mayor que cero, se multiplica por él factorial del número menor inmediato."

Para calcular el factorial de cualquier número mayor que cero hay que calcular como mínimo el factorial de otro número. La función que se utiliza es la función en la que se encuentra en estos momentos, esta función debe llamarse a sí misma para el número menor inmediato, para poder ejecutarse en el número actual. Esto es un ejemplo de recursividad.

La recursividad y la iteración (ejecución en bucle) están muy relacionadas, cualquier acción que pueda realizarse con la recursividad puede realizarse con iteración y viceversa. Normalmente, un cálculo determinado se prestará a una técnica u otra, sólo necesita elegir el enfoque más natural o con el que se sienta más cómodo.

Claramente, esta técnica puede constituir un modo de meterse en problemas. Es fácil crear una función recursiva que no llegue a devolver nunca un resultado definitivo y no pueda llegar a un punto de finalización. Este tipo de recursividad hace que el sistema ejecute lo que se conoce como bucle "infinito".

Para entender mejor lo que en realidad es el concepto de recursión veamos un poco lo referente a la secuencia de Fibonacci.

Principalmente habría que aclarar que es un ejemplo menos familiar que el del factorial, que consiste en la secuencia de enteros.

0,1,1,2,3,5,8,13,21,34,…,

Cada elemento en esta secuencia es la suma de los precedentes (por ejemplo 0 + 1 = 0, 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, …) sean fib(0) = 0, fib (1) = 1 y así sucesivamente, entonces puede definirse la secuencia de Fibonacci mediante la definición recursiva (define un objeto en términos de un caso mas simple de si mismo):

fib (n) = n if n = = 0 or n = = 1

fib (n) = fib (n – 2) + fib (n – 1) if n >= 2

Por ejemplo, para calcular fib (6), puede aplicarse la definición de manera recursiva para obtener:

Fib (6) = fib (4) + fib (5) = fib (2) + fib (3) + fib (5) = fib (0) + fib (1) + fib (3) + fib (5) = 0 + 1 fib (3) + fib (5)

1. + fib (1) + fib (2) + fib(5) =

1. + 1 + fib(0) + fib (1) + fib (5) =
2. + 0 + 1 + fib(5) = 3 + fib (3) + fib (4) =

   3 + 1 + fib (0) + fib (1) + fib (4) =

3. + fib (1) + fib (2) + fib (4) =
4. + 0 + 1 + fib (2) + fib (3) = 5 + fib (0) + fib (1) + fib (3) =
5. + 0 + 1 + fib (1) + fib (2) = 6 + 1 + fib (0) + fib (1) =
6. + 0 + 1 = 8

Obsérvese que la definición recursiva de los números de Fibonacci difiere de las definiciones recursivas de la función factorial y de la multiplicación . La definición recursiva de fib se refiere dos veces a sí misma . Por ejemplo, fib (6) = fib (4) + fib (5), de tal manera que al calcular fib (6), fib tiene que aplicarse de manera recursiva dos veces. Sin embargo calcular fib (5) también implica calcular fib (4), así que al aplicar la definición hay mucha redundancia de cálculo. En ejemplo anterior, fib(3) se calcula tres veces por separado. Sería mucho mas eficiente "recordar" el valor de fib(3) la primera vez que se calcula y volver a usarlo cada vez que se necesite. Es mucho mas eficiente un método iterativo como el que sigue parar calcular fib (n).

If (n < = 1)

return (n);

lofib = 0 ;

hifib = 1 ;

for (i = 2; i < = n; i ++)

{

x = lofib ;

lofib = hifib ;

hifib = x + lofib ;

} /* fin del for*/

return (hifib) ;

Compárese el numero de adiciones (sin incluir los incrementos de la variable índice, i) que se ejecutan para calcular fib (6) mediante este algoritmo al usar la definición recursiva. En el caso de la función factorial, tienen que ejecutarse el mismo numero de multiplicaciones para calcular n! Mediante ambos métodos: recursivo e iterativo. Lo mismo ocurre con el numero de sumas en los dos métodos al calcular la multiplicación. Sin embargo, en el caso de los números de Fibonacci, el método recursivo es mucho mas costoso que el iterativo.

2.- Propiedades de las definiciones o algoritmos recursivos:

Un requisito importante para que sea correcto un algoritmo recursivo es que no genere una secuencia infinita de llamadas así mismo. Claro que cualquier algoritmo que genere tal secuencia no termina nunca. Una función recursiva f debe definirse en términos que no impliquen a f al menos en un argumento o grupo de argumentos. Debe existir una "salida" de la secuencia de llamadas recursivas.

Si en esta salida no puede calcularse ninguna función recursiva. Cualquier caso de definición recursiva o invocación de un algoritmo recursivo tiene que reducirse a la larga a alguna manipulación de uno o casos mas simples no recursivos.

3.- Cadenas recursivas:

Una función recursiva no necesita llamarse a sí misma de manera directa. En su lugar, puede hacerlo de manera indirecta como en el siguiente ejemplo:

a (formal parameters) b (formal parameters)

{ {

. .

b (arguments); a (arguments);

. .

} /*fin de a*/ } /*fin de b*/

En este ejemplo la función a llama a b, la cual puede a su vez llamar a a, que puede llamar de nuevo a b. Así, ambas funciones a y b, son recursivas, dado que se llamas a sí mismo de manera indirecta. Sin embargo, el que lo sean no es obvio a partir del examen del cuerpo de una de las rutinas en forma individual. La rutina a, parece llamar a otra rutina b y es imposible determinar que se puede llamar así misma de manera indirecta al examinar sólo a a.

Pueden incluirse mas de dos rutinas en una cadena recursiva. Así, una rutina a puede llamar a b, que llama a c, …, que llama a z, que llama a a. Cada rutina de la cadena puede potencialmente llamarse a sí misma y, por lo tanto es recursiva. Por supuesto, el programador debe asegurarse de que un programa de este tipo no genere una secuencia infinita de llamadas recursivas.

4.- Definición recursiva de expresiones algebraicas:

Como ejemplo de cadena recursiva consideremos el siguiente grupo de definiciones:

1. una expresión es un término seguido por un signo mas seguido por un término, o un término solo
2. un término es un factor seguido por un asterisco seguido por un factor, o un factor solo.
3. Un factor es una letra o una expresión encerrada entre paréntesis.

Antes de ver algunos ejemplos, obsérvese que ninguno de los tres elementos anteriores está definido en forma directa en sus propios términos. Sin embargo, cada uno de ellos se define de manera indirecta. Una expresión se define por medio de un término, un término por medio de un factor y un factor por medio de una expresión. De manera similar, se define un factor por medio de una expresión, que se define por medio de un término que a su vez se define por medio de un factor. Así, el conjunto completo de definiciones forma una cadena recursiva.

La forma mas simple de un factor es una letra. Así A, B, C, Q, Z y M son factores. También son términos, dado que un término puede ser un factor solo. También son expresiones dado que una expresión puede ser un término solo. Como A es una expresión, (A) es un factor y, por lo tanto, un término y una expresión. A + B es un ejemplo de una expresión que no es ni un término ni un factor, sin embargo (A + B) es las tres cosas. A * B es un término y, en consecuencia, una expresión, pero no es un factor. A * B + C es una expresión, pero no es un factor.

Cada uno de los ejemplos anteriores es una expresión valida. Esto puede mostrarse al aplicar la definición de una expresión de cada uno. Considérese, sin embargo la cadena A + * B. No es ni una expresión, ni un término, ni un factor. Sería instructivo para el lector intentar aplicar la definición de expresión, término y factor para ver que ninguna de ellas describe a la cadena A + * B. De manera similar, (A + B*) C y A + B + C son expresiones nulas de acuerdo con las definiciones precedentes.

A continuación se codificará un programa que lea e imprima una cadena de caracteres y luego imprima "valida" si la expresión lo es y "no valida" de no serlo. Se usan tres funciones para reconocer expresiones, términos y factores, respectivamente. Primero, sin embrago se presenta una función auxiliar getsymb que opera con tres parámetros: str, length y ppos. Str contiene la entrada de la cadena de cadena de caracteres; length representa el número de caracteres en str. Ppos apunta a un puntero pos cuyo valor es la posición str de la que obtuvimos un carácter la ultima vez. Si pos < length, getsymb regresa el carácter cadena str [pos] e incrementa pos en 1. Si pos > = length, getsymb regresa un espacio en blanco.

getsymb (str, length, ppos)

char str[];

int length, *ppos;

{

char C;

if (*ppos < length)

c = str [*ppos];

else

c = ‘ ‘ ;

(*ppos) ++;

return ( c );

} /* fin de getsymb*/

La función que reconoce una expresión se llama expr. Regresa TRUE (o1) (VERDADERO) si una expresión valida comienza en la posición pos de str y FALSE (o0) FALSO en caso contrario. También vuelve a colocar pos en la posición que sigue en la expresión de mayor longitud que puede encontrar. Suponemos también una función readstr que lee una cadena de caracteres, poniendo la cadena en str y su largo en length.

Una vez descritas las funciones expr y readst, puede escribirse la rutina principal como sigue. La biblioteca estándar ctype.h incluye una función isalpha que es llamada por una de las funciones siguientes.

# include <stdio.h>

# include <ctype.h>

# define TRUE 1

# define FALSE =

# define MAXSTRINGSIZE 100

main ()

{

char str [MAXSTRINGSIZE];

int length, pos;

readstr (str, &length);

pos = 0;

if (expr (str, length, &pos) = = TRUE && por >= length)

printf ("%s", "valida");

else

printf ("%s", "no valida");

/* la condición puede fallar por una de dos razones (o ambas). Si expr(str, length, &pos) = = FALSE entonces no hay una expresión valida al inicio de pos. Si pos < length puede que se encuentre una expresión valida, comenzando en pos, pero no ocupa la cadena completa */

} /*fin del main*/

Las funciones factor y term se parecen mucho a expr excepto en que son responsables del reconocimiento de factores y término, respectivamente. También reinicializan pos en la posición que sigue al factor o término de mayor longitud que se encuentra en la cadena str.

Los códigos para estas rutinas se apegan bastantes a las definiciones dadas antes. Cada una intenta satisfacer uno de los criterios para la entidad que se reconoce. Si se satisface uno de esos criterios el resultado es TRUE (VERDADERO). Si no satisface ninguno, el resultado es FALSE (FALSO).

expr (str. length, ppos)

char str [];

int length, *ppos;

{

/* buscando un término */

if (term( str, length, ppos) = = FLASE)

return (FLASE);

/* se ha encontrado un término; revisar el siguiente símbolo */

if (getsymb(str, length, ppos) ! = ‘+’) {

/* se encontró la mayor expresión (un solo término). Reposicionar pos para que señale la última posición de la expresión */

(*ppos) – – ;

return (TRUE);

} /* fin del if */

/* en este punto, se a encontrado un termino y su signo mas. Se deberá buscar otro termino */

return (term(str, length, ppos));

} /*fin de expr */

La rutina term que reconoce términos, es muy similar y será presentada sin comentarios.

term (str, length, ppos)

char str[];

int length, *ppos;

{

if (factor(str, length, ppos) = = FALSE)

return (FALSE);

if (getsymb (str, length, ppos) ! = ‘+’) {

(*ppos) — ;

return (TRUE) ;

} /* fin del if */

return (factor(str, length, ppos));

} /* fin de term */

La función factor reconoce factores y debería ser ahora bastante sencilla. Usa el programa común de biblioteca isalpha (esta función se encuentra en la biblioteca ctype.h), que regresa al destino de cero si su carácter de parámetro es una letra y cero (o FALSO) en caso contrario.

factor (str, length, ppos)

char str[];

int length, *ppos;

{

int c;

if ((c = getsymb (str, length, ppos)) ! = ‘)’ )

return (isalpha(c));

return (expr(str, length, ppos) && getsymb (str, length, ppos) == ‘)’ );

} /* fin de factor */

Las tres rutinas son recursivas, dado que cada una puede llamar a sí misma da manera indirecta. Pos ejemplo, si se sigue la acción del programa para la cadena de entrada " (a * b + c * d) + (e * (f) + g) " se encontrará que cada una de las tres rutinas expr, term y factor se llama a sí misma.

5.- Programación Recursiva:

Es mucho mas difícil desarrollar una solución recursiva en C para resolver un problema especifico cuando no se tiene un algoritmo. No es solo el programa sino las definiciones originales y los algoritmos los que deben desarrollarse. En general, cuando encaramos la tarea de escribir un programa para resolver un problema no hay razón para buscar una solución recursiva. La mayoría de los problemas pueden resolverse de una manera directa usando métodos no recursivos. Sin embargo, otros pueden resolverse de una manera mas lógica y elegante mediante la recursión.

Volviendo a examinar la función factorial. El factor es, probablemente, un ejemplo fundamental de un problema que no debe resolverse de manera recursiva, dado que su solución iterativa es directa y simple. Sin embargo, examinaremos los elementos que permiten dar una solución recursiva. Antes que nada, puede reconocerse un gran número de casos distintos que se deben resolver. Es decir, quiere escribirse un programa para calcular 0!, 1!, 2! Y así sucesivamente. Puede identificarse un caso "trivial" para el cual la solución no recursiva pueda obtenerse en forma directa. Es el caso de 0!, que se define como 1. El siguiente paso es encontrar un método para resolver un caso "complejo" en términos de uno mas "simple", lo cual permite la reducción de un problema complejo a uno mas simple. La transformación del caso complejo al simple resultaría al final en el caso trivial. Esto significaría que el caso complejo se define, en lo fundamental, en términos del mas simple.

Examinaremos que significa lo anterior cuando se aplica la función factorial. 4! Es un caso mas complejo que 3!. La transformación que se aplica al numero a para obtener 3 es sencillamente restar 1. Si restamos 1 de 4 de manera sucesiva llegamos a 0, que es el caso trivial. Así, si se puede definir 4! en términos de 3! y, en general, n! en términos de (n – 1)!, se podrá calcular 4! mediante la definición de n! en términos de (n – 1)! al trabajar, primero hasta llegar a 0! y luego al regresar a 4!. En el caso de la función factorial se tiene una definición de ese tipo, dado que:

n! = n * (n – 1)!

Asi, 4! = 4 * 3! = 4 * 3 * 2! = 4 * 3 * 2 * 1! = 4 * 3 * 2 * 1 * 0! = 4 * 3 * 2] * ] = 24

Estos son los ingredientes esenciales de una rutina recursiva: poder definir un caso "complejo" en términos de uno más "simple" y tener un caso "trivial" (no recursivo) que pueda resolverse de manera directa. Al hacerlo, puede desarrollarse una solución si se supone que se ha resuelto el caso más simple. La versión C de la función factorial supone que esta definido (n –1)! y usa esa cantidad al calcular n!.

Otra forma de aplicar estas ideas a otros ejemplos antes explicados. En la definición de a * b, es trivial el caso de b = 1, pues a * b es igual a a. En general, a + b puede definirse en términos de a * (b – 1) mediante la definición a * b = a * (b – 1) + a. De nuevo, el caso complejo se transforma en un caso mas simple al restar 1, lo que lleva, al final, al caso trivial de b = 1. Aquí la recursión se basa únicamente en el segundo parámetro, b.

Con respecto al ejemplo de la función de Fibonacci, se definieron dos casos triviales: fib(0) = 0 y fib(1) = 1. Un caso complejo fib(n) se reduce entonces a dos más simples: fib(n –1) y fib(n –2). Esto se debe a la definición de fib(n) como fib(n –1) + fib(n – 2), donde se requiere de dos casos triviales definidos de manera directa. Fib(1) no puede definirse como fib(0) + fib(-1) porque la función de Fibonacci no está definida para números negativos.

6.- Asignación estática y dinámica de memoria:

Hasta este momento solamente hemos realizado asignaciones estáticas del programa, y más concretamente estas asignaciones estáticas no eran otras que las declaraciones de variables en nuestro programa. Cuando declaramos una variable se reserva la memoria suficiente para contener la información que debe almacenar. Esta memoria permanece asignada a la variable hasta que termine la ejecución del programa (función main). Realmente las variables locales de las funciones se crean cuando éstas son llamadas pero nosotros no tenemos control sobre esa memoria, el compilador genera el código para esta operación automáticamente.

En este sentido las variables locales están asociadas a asignaciones de memoria dinámicas, puesto que se crean y destruyen durante la ejecución del programa.

Así entendemos por asignaciones de memoria dinámica, aquellas que son creadas por nuestro programa mientras se están ejecutando y que por tanto, cuya gestión debe ser realizada por el programador.

El lenguaje C dispone, como ya indicamos con anterioridad, de una serie de librerías de funciones estándar. El fichero de cabeceras stdlib.h contiene las declaraciones de dos funciones que nos permiten reservar memoria, así como otra función que nos permite liberarla.

Las dos funciones que nos permiten reservar memoria son:

• malloc (cantidad_de_memoria);
• calloc (número_de_elementos, tamaño_de_cada_elemento);

Estas dos funciones reservan la memoria especificada y nos devuelven un puntero a la zona en cuestión. Si no se ha podido reservar el tamaño de la memoria especificado devuelve un puntero con el valor 0 o NULL. El tipo del puntero es, en principio void, es decir, un puntero a cualquier cosa. Por tanto, a la hora de ejecutar estás funciones es aconsejable realizar una operación cast (de conversión de tipo) de cara a la utilización de la aritmética de punteros a la que aludíamos anteriormente. Los compiladores modernos suelen realizar esta conversión automáticamente.

Antes de indicar como deben utilizarse las susodichas funciones tenemos que comentar el operador sizeof. Este operadores imprescindible a la hora de realizar programas portables, es decir, programas que puedan ejecutarse en cualquier máquina que disponga de un compilador de C.

El operador sizeof (tipo_de_dato), nos devuelve el tamaño que ocupa en memoria un cierto tipo de dato, de esta manera, podemos escribir programas independientes del tamaño de los datos y de la longitud de palabra de la máquina. En resumen si no utilizamos este operador en conjunción con las conversiones de tipo cast probablemente nuestro programa sólo funciones en el ordenador sobre el que lo hemos programado.

Por ejemplo, el los sistemas PC, la memoria está orientada a bytes y un entero ocupa 2 posiciones de memoria, sin embargo puede que en otro sistema la máquina esté orientada a palabras (conjuntos de 2 bytes, aunque en general una máquina orientada a palabras también puede acceder a bytes) y por tanto el tamaño de un entero sería de 1 posición de memoria, suponiendo que ambas máquinas definan la misma precisión para este tipo.

Con todo lo mencionado anteriormente veamos un ejemplo de un programa que reserva dinámicamente memoria para algún dato.

#include <stdlib.h

#include <stdio.h>

main()

{

int *p_int;

float *mat;

p_int = (int *) malloc(sizeof(int));

mat = (float *)calloc(20,sizeof(float));

if ((p_int==NULL)||(mat==NULL))

{

printf ("nNo hay memoria");

exit(1);

}

/* Aquí irían las operaciones sobre los datos */

/* Aquí iría el código que libera la memoria */

}

Este programa declara dos variables que son punteros a un entero y a un float. A estos punteros se le asigna una zona de memoria, para el primero se reserva memoria para almacenar una variable entera y en el segundo se crea una matriz de veinte elementos cada uno de ellos un float. Obsérvese el uso de los operadores cast para modificar el tipo del puntero devuelto por malloc y calloc, así como la utilización del operador sizeof.

Como se puede observar no resulta rentable la declaración de una variable simple (un entero, por ejemplo, como en el programa anterior) dinámicamente, en primer lugar por que aunque la variable sólo se utilice en una pequeña parte del programa, compensa tener menos memoria (2 bytes para un entero) que incluir todo el código de llamada a malloc y comprobación de que la asignación fue correcta (esto seguro que ocupa más de dos bytes).

En segundo lugar tenemos que trabajar con un puntero con lo cual el programa ya aparece un poco más engorroso puesto que para las lecturas y asignaciones de las variables tenemos que utilizar el operador *.

Para termina un breve comentario sobre las funciones anteriormente descritas. Básicamente da lo mismo utilizar malloc y calloc para reservar memoria es equivalente:

mat = (float *)calloc (20,sizeof(float));

mat = (float *)malloc (20*sizeof(float));

La diferencia fundamental es que, a la hora de definir matrices dinámicas calloc es mucho más claro y además inicializa todos los elementos de la matriz a cero. Nótese también que puesto que las matrices se referencian como un puntero la asignación dinámica de una matriz nos permite acceder a sus elementos con instrucciones de la forma:

NOTA: En realidad existen algunas diferencias al trabajar sobre máquinas con alineamiento de palabras.

mat[0] = 5;

mat[2] = mat[1]*mat[6]/67;

Con lo cual el comentario sobre lo engorroso que resultaba trabajar con un puntero a una variable simple, en el caso de las matrices dinámicas no existe diferencia alguna con una declaración normal de matrices.

La función que nos permite liberar la memoria asignada con malloc y calloc es free(puntero), donde puntero es el puntero devuelto por malloc o calloc.

En nuestro ejemplo anterior, podemos ahora escribir el código etiquetado como: /* Ahora iría el código que libera la memoria */

free (p_int);

free(mat);

Hay que tener cuidado a la hora de liberar la memoria. Tenemos que liberar todos los bloque que hemos asignado, con lo cual siempre debemos tener almacenados los punteros al principio de la zona que reservamos. Si mientras actuamos sobre los datos modificamos el valor del puntero al inicio de la zona reservada, la función free probablemente no podrá liberar el bloque de memoria.

7.- Ejemplos:

7.1.- Las Torres de Hanoi:

A continuación se verá cómo pueden usarse técnicas recursivas para lograr una solución lógica y elegante de un problema que no se especifica en términos recursivos. EL problema es el de "las torres de Hanoi", cuyo planteamiento inicial se muestra en la figura a continuación…

 Hay tres postes: A, B y C. En el poste A se ponen cinco discos de diámetro diferente de tal manera que un disco de diámetro mayor siempre queda debajo de uno de diámetro menor. El objetivo es mover los discos al poste C usando B como auxiliar. Sólo puede moverse el disco superior de cualquier poste a otro poste, y un disco mayor jamás puede quedar sobre uno menor. Considérese la posibilidad de encontrar una solución. En efecto, ni siquiera es claro que exista una.

Ahora se verá si se puede desarrollar una solución. En lugar de concentrar la atención en una solución para cinco discos, considérese el caso general de n discos. Supóngase que se tiene una solución para n – 1 discos y que en términos de ésta, se pueda plantear la solución para n – 1 discos. El problema se resolvería entonces. Esto sucede porque en el caso trivial de un disco (al restar 1 de n de manera sucesiva se producirá, al final, 1) la solución es simple: sólo hay que el único disco del poste A a C. Así se habrá desarrollado una solución recursiva si se plantea una solución para n discos en términos de n – 1. Considérese la posibilidad de encontrar tal relación. Para el caso de cinco discos en particular, supóngase que se conoce la forma de mover cuatro de ellos del poste A al otro, de acuerdo con las reglas. ¿Cómo puede completarse entonces el trabajo de mover el quinto disco? Cabe recordar que hay 3 postes disponibles.

Supóngase que se supo cómo mover cuatro discos del poste A al C. Entonces, se pondrá mover éstos exactamente igual hacia B usando el C como auxiliar. Esto da como resultado la situación los cuatro primeros discos en el poste B, el mayor en A y en C ninguno. Entonces podrá moverse el disco mayor de A a C y por último aplicarse de nuevo la solución recursiva para cuatro discos para moverlo de B a C, usando el poste A como auxilia. Por lo tanto, se puede establecer una solución recursiva de las torres de Hanoi como sigue:

Para mover n discos de A a C usando B como auxiliar:

1. Si n = = 1, mover el disco único de A a C y parar.
2. Mover el disco superior de A a B n – 1 veces, usando C como auxiliar.
3. Mover el disco restante de A a C.
4. Mover los disco n – 1 de B a C usando A como auxiliar

Con toda seguridad este algoritmo producirá una solución completa por cualquier valor de n. Si n = = , el paso 1 será la solución correcta. Si n = = 2, se sabe entonces que hay una solución para n – 1 = = 1, de manera tal que los pasos 2 y 4 se ejecutaran en forma correcta. De manera análoga, cuando n = = 3 ya se habrá producido una solución para n – 1 = = 2, por lo que los pasos 2 y 4 pueden ser ejecutados. De esta forma se puede mostrar que la solución funciona para n = = 1, 2, 3, 4, 5,… hasta el valor para el que se desee encontrar una solución. Adviértase que la solución se desarrollo mediante la identificación de un caso trivial (n = = 1) y una solución para el caso general y complejo (n) en términos de un caso mas simple (n – 1).

Ya se demostró que las transformaciones sucesivas de una simulación no recursivas de una rutina recursiva pueden conducir a un programa mas simple para resolver un problema. Ahora se simulara la recursión del problema y se intentara simplificar la simulación no recursiva.

towers (n, frompeg, topeg, auxpeg)

int n;

char auxpeg, frompeg, topeg;

{

/* si es solo un disco, mover y regresar */

if (n = = 1) {

printf (" /n%s%c%s%c%", "mover disco 1 del poste",frompeg, "al poste", topeg);

return; } /* fin del if*/

/* mover los n – 1 discos de arriba de A a B, usando como auxiliar */

towers (n – 1, frompeg, auxpeg, tpoeg);

/* move remaining disk from A to C */

printf ("/n%s%d%s%c%s%c%", "mover disco", n, "del poste" frompeg, "al poste", topeg);

/* mover n – 1 discos de B hacia C empleando a A como auxiliar */

towers (n – 1, auxpeg, topeg, frompeg);} /* fin de towers */

En esta función, hay cuatro parámetros, cada uno de los cuales esta sujeto a cambios en cada llamada recursiva. En consecuencia, el área de datos debe contener elementos que representen a los cuatro. No hay variables locales. Hay un solo valor temporal que se necesita para guardar el valor de n – 1, pero esta se puede representar por un valor temporal similar en el programa de simulación y no tiene que estar apilada. Hay tres puntos posibles a los que regresa la función en varias llamadas: el programa de llamada y los dos puntos que siguen a las llamadas recursivas. Por lo tanto, se necesitan cuatro etiquetas.

start:

Label1:

Label2:

Label3:

La dirección de regreso se codifica como un entero (1, 2 o 3) dentro de cada área de datos.

Considérese la siguiente simulación no recursiva de towers:

struct dataarea {

int nparam;

char fromparam;

char toparam;

char auxparam;

short int retaddr;

};

struct stack {

int top struct dataarea item [MAXSTACK]; };

simtowers (m, frompeg, topeg, auxpeg)

int n;

char auspeg, frompeg, topeg; {

struct stack s;

struct dataarea currarea;

char temp;

short int i;

s.top = -1;

currarea.nparam = 0;

currarea.fromparam = ‘ ‘ ;

currarea.toparam = ‘ ‘ ;

currarea. auxparam = ‘ ‘ ;

currarea.retaddr = 0;

/* colocar en la pila un área de datos simulados */

push (&s, &currarea);

/* asignar parámetros y direcciones de regreso del área de datos actual a sus valores apropiados */

currarea.nparam = n;

currarea,fromparam = frompeg;

currarea,toparam = topeg;

currarea.auxparam = auxpeg;

currarea.retaddr = 1;

start: /* Este es el inicio de la rutina simulada */

if (currarea.nparam = = 1) {

printf (" /n%s%c%s%c", "mover disco 1 del poste", currarea.fromparam, "al poste", currarea.toparam) ;

i = currarea.retaddr;

pop (&s, &currarea);

switch (i) {

case 1: goto label1;

case 2: goto label2;

case 3: goto label3; } /* fin del switch */

} /* fin del if */

/* Esta es la primera llamada recursiva */

push (&s, &currarea);

— currarea.nparam;

temp = currarea.auxparam;

currarea.auxparam = currarea.toparam;

currarea.toparam = temp;

currarea.retaddr = 2;

got start;

label2: /* se regresa a este punto desde la primera llamada recursiva */

printf ("/n%s%d%s%c%s%c", "mover disco", currarea.nparam, "del poste", currarea.fromparam, "al poste", currarea.toparam);

/* Esta es la segunda llamada recursiva */

push (&s, &currarea);

–currarea.nparam;

temp = currarea.fromparam;

currarea.fromparam = currarea.auxparam;

currarea.auxparam = temp;

currarea.rtaddr = 3;

got start;

label3: /* se regresa a este punto desde la segunda llamada recursiva */

i = currarea.retaddr;

pop (&s, &currarea);

swicth (i) {

case 1: goto label1;

case 2: goto label2;

case 3: goto label3; } /* fin del switch */

label1: return;

} /* fin de simtowers */

Ahora se simplificará el programa. En primer lugar, debe observarse que se usan tres etiquetas para indicar direcciones de regreso; una para cada una de las dos llamadas recursivas y otra para el regreso al programa principal. Sin embargo, el regreso al programa principal puede señalarse por un subdesborde en la pila, de la misma for que en la segunda versión simfact. Esto deja dos etiquetas de regreso. Si pudiera eliminarse otra mas, sería innecesario guardar en la pila la dirección de regreso, ya que solo restaría un punto al que se podría transferir el control si se eliminan los elementos de la pila con éxito. Ahora dirijamos nuestra atención a la segunda llamada recursiva y a la instrucción:

towers (n – 1, auxpeg, topeg, frompeg);

Las acciones que ocurren en la simulación de esta llamada son las siguientes:

1. Se coloca el área de datos vigente a 1 dentro de la pila.
2. En la nueva área de datos vigente a 2, se asignan los valores respectivos n – 1, auxpeg, topeg, y frompeg a los parámetros.
3. En el área de datos vigente a 2, se fija la etiqueta de retorno a la dirección de la instrucción que sigue de inmediato a la llamada.
4. Se salta hacia el principio de la rutina simulada.
5. Después de completar la rutina simulada, ésta queda lista parar regresar. Las siguientes acciones se llevan a efecto:
6. Se salva la etiqueta de regreso, /, de área de datos vigentes a 2.
7. Se eliminan de la pila y se fija el área de datos vigente como el área de datos eliminada de la pila, a 1.
8. Se transfiere el control a /.

Sin embrago, / es la etiqueta del final del bloque del programa ya que la segunda llamada a towers aparece en la última instrucción de la función. Por lo tanto, el siguiente paso es volver a eliminar elementos de la pila y regresar. No se volverá a hacer uso de la información del área de datos vigente a 1, ya que ésta es destruida en la eliminación de los elementos en la pila tan pronto como se vuelve a almacenar. Puesto que no hay razón para volver a usar esta área de datos, tampoco hay razón para salvarla en la pila durante la simulación de la llamada. Los datos se deben salvar en la pila sólo si se van a usar otra vez. En consecuencia, la seguida llamada a towers puede simularse en forma simple mediante:

1. El cambio de los parámetros en el área de datos vigente a sus valores respectivos.
2. El "salto" al principio de la rutina simulada.

Cuando la rutina simulada regresa puede hacerlo en forma directa a la rutina que llamó a la versión vigente. No hay razón para ejecutar un regreso a la versión vigente, sólo para regresar de inmediato a la versión previa. Por lo tanto, se elimina la necesidad de guardar en la pila la dirección de regreso al simular la llamada externa (ya que se puede señalar mediante subdesborde y simular la segunda llamada recursiva, ya que no hay necesidad de salvar y volver a almacenar al área de datos de la rutina que llamada en este momento). La única dirección de regreso que resta es la que sigue a la primera llamada recursiva.

Ya que sólo queda una dirección de regreso posible, no tiene caso guardarla en la pila para que se vuelva a insertar y eliminar con el resto de los datos. Siempre se eliminan elementos de la pila con éxito, hay una solo dirección hacia la que se puede ejecutar un "salto" (la instrucción que sigue a la primera llamada). Como los nuevos valores de las variables del área de datos vigente se obtendrán a partir de los datos antiguos de área de datos vigente, es necesario declarar una variable adicional, temp, de manera que los valores sean intercambiables.

7.2.- El Problema de las Ocho Reinas:

El problema de las ocho reinas y en general de las N reinas, se basa en colocar 8 reinas en un tablero de 8´ 8 (o N en un tablero de NxN, si el problema se generaliza), de forma que en no puede haber dos piezas en la misma línea horizontal, vertical o diagonal, ver Figura 1.

 Para ver el gráfico seleccione la opción "Descargar" del menú superior

Figura 1

Posible solución para el problema de las ocho reinas

Este programa has sido muy estudiado por los matemáticos. Se trata de un problema NP-Completo que no tiene solución para N=2 y N=3. Para N=4 tiene una única solución. Para N=8 hay más de 80 soluciones dependiendo de las restricciones que se impongan.

Una forma de abordar el problema se lleva a cabo mediante la construcción de un predicado en Prolog del tipo siguiente: reinas (N, Solución), donde N representa las dimensiones del tablero y el número de reinas y Solución es una lista que contiene la permutación de la lista de números que resuelven el problema. Los índices de dicha lista representan la columna en la que se encuentra una reina y el número que almacena la posición o índice representa la fila donde la reina está colocada. Así, para el ejemplo mostrado en la Figura 1, tenemos que R=[2,4,1,3].

Este problema es resuelto, de modo clásico, por el método de prueba y error, luego se adapta perfectamente a un algoritmo de backtracking. Básicamente, el problema se reduce a colocar una reina, e intentar repetir el proceso teniendo en cuenta la reina colocada. Si logramos poner todas las reinas el problema se ha resuelto, en caso contrario, deshacemos lo que llevamos hasta ahora y probamos con otra combinación. Por tanto, hemos de generar un conjunto de permutaciones y seleccionar aquella que cumpla los requisitos impuestos por el juego.

Veamos el código que resuelve el problema:

rango(N, N, [N]).

rango(N, M, [N|Cola]):-N<M, Aux is N+1, rango(Aux, M, Cola). 

dame(X,[X|Xs],Xs).

dame(X,[Y|Ys],[Y|Zs]):-dame(X,Ys,Zs). 

permuta([],[]).

permuta(L,[Z|Zs]):-dame(Z,L,Ys), permuta(Ys,Zs). 

atacada(X,Y):-atacada(X,1,Y).

atacada(X,N,[Y|Ys]):-X is Y+N; X is Y-N.

atacada(X,N,[Y|Ys]):-N1 is N+1, atacada(X,N1,Ys). 

correcta([]).

correcta([X|Y]):-correcta(Y), not atacada(X,Y). 

reina(N, Solucion):-rango(1,N,L1), permuta(L1,Solucion), correcta(Solucion).

Es muy importante comprender como funciona cada uno de los predicados para entender el funcionamiento del algoritmo general.

Prolog permite implementar los programas casi directamente a partir de las especificaciones realizadas a partir de un análisis y diseño de la solución desde un alto nivel de abstracción. Además el procedimiento de backtracking está implícito en el propio motor de inferencia, luego este paradigma se adapta perfectamente a nuestro problema.

Si analizamos y diseñamos nuestro problema tenemos que la forma de resolverlo se resume en los pasos siguientes:

Para N, obtenemos una lista de números comprendidos entre 1 y N: [1,2,3,4,…,N].

Obtenemos una permutación del conjunto de números de la lista.

Comprobamos que la permutación es correcta.

Si la permutación no es correcta, lo que debemos hacer es volver al paso 2 para generar una permutación nueva.

Comencemos a analizar la solución implementada. El problema se resuelve con el predicado reina(N, Solución): rango(1,N,L1), permuta(L1,Solucion), correcta Solución).Como vemos es, sencillamente, una copia de las especificaciones realizadas más arriba. Se genera el rango entre 1 y N, se obtiene una permutación y se comprueba si la permutación es, o no, correcta. En el caso de que cualquier predicado del consecuente falle, la propia máquina Prolog se encarga de realizar el proceso de backtracking. Con lo cual ya tenemos cubiertos los cuatro pasos fundamentales del algoritmo. Para tener más claras las ideas, observemos el árbol de ejecución general del objetivo reina(4,Solucion) en la Figura 2.

Figura 2

Árbol de ejecución para el objetivo reina(4,Solucion)

He aquí otro ejemplo sobre el problema de las ocho reinas. Primero se mostrara un pseudocodigo sobre el mismo y luego su respectiva codificación en el lenguaje C.

<PRINCIPIO ensayar> (i: entero)

inicializar el conjunto de posiciones de la reina i-ésima

+-REPETIR hacer la selección siguiente

| +-SI segura ENTONCES

| | poner reina

| | +-SI i < 8 ENTONCES

| | | LLAMAR ensayar (i + 1)

| | | +-SI no acertado ENTONCES

| | | | quitar reina

| | | +-FINSI

| | +-FINSI

| +-FINSI

+-HASTA acertada O no hay más posiciones

<FIN>

Observaciones sobre el código:

1) Estudiar la función ensayar() a partir de este pseudocódigo.

2) Vectores utilizados:

int posiciones_en_columna[8]; RANGO: 1..8

BOOLEAN reina_en_fila[8]; RANGO: 1..8

BOOLEAN reina_en_diagonal_normal[15]; RANGO: -7..7

BOOLEAN reina_en_diagonal_inversa[15]; RANGO: 2..16

En C, el primer elemento de cada vector tiene índice 0, esto

es fácil solucionarlo con las siguientes macros:

#define c(i) posiciones_en_columna[(i)-1]

#define f(i) reina_en_fila[(i)-1]

#define dn(i) reina_en_diagonal_normal[(i)+7]

#define di(i) reina_en_diagonal_inversa[(i)-2]

Significado de los vectores:

c(i) : la posición de la reina en la columna i

f(j) : indicativo de que no hay reina en la fila j-ésima

dn(k): indicativo de que no hay reina en la diagonal normal

() k-ésima

di(k): indicativo de que no hay reina en la diagonal

invertida (/) k-ésima

Dado que se sabe, por las reglas del ajedrez, que una reina actúa sobre todas las piezas situadas en la misma columna, fila o diagonal del tablero se deduce que cada columna puede contener una y sólo una reina, y que la elección de la situación de la reina i-ésima puede restringirse a los cuadros de la columna i. Por tanto, el parámetro i se convierte en el índice de columna, y por ello el proceso de selección de posiciones queda limitado a los ocho

posibles valores del índice de fila j.

A partir de estos datos, la línea poner reina del pseudocódigo es:

c (i) = j; f (j) = di (i + j) = dn (i – j) = FALSE;

y la línea quitar reina del pseudocódigo:

f (j) = di (i + j) = dn (i – j) = TRUE;

y la condición segura del pseudocódigo:

f (i) && di (i + j) && dn (i – j)

/* Ficheros a incluir: */

#include <stdio.h> /* printf () */

#include <conio.h> /* getch () */

/* Macros: */

#define BOOLEAN int

#define TRUE 1

#define FALSE 0

/* Variables globales: */

BOOLEAN acertado;

int posiciones_en_columna[8];

BOOLEAN reina_en_fila[8];

BOOLEAN reina_en_diagonal_normal[15];

BOOLEAN reina_en_diagonal_inversa[15];

#define c(i) posiciones_en_columna[(i)-1]

/* rango de índice: 1..8 */

#define f(i) reina_en_fila[(i)-1]

/* rango de índice: 1..8 */

#define dn(i) reina_en_diagonal_normal[(i)+7]

/* rango de índice: -7..7 */

#define di(i) reina_en_diagonal_inversa[(i)-2]

/* rango de índice: 2..16 */

/* Prototipos de las funciones: */

void proceso (void);

void ensayar (int i);

/* Definiciones de las funciones: */

void main (void)

{

printf ("nnPROBLEMA DE LAS OCHO REINAS:n ");

proceso ();

printf ("nnPulsa cualquier tecla para finalizar. ");

getch ();

}

void proceso (void)

{

register int i,j;

for (i = 1; i <= 8; i++)

f (i) = TRUE;

for (i = 2; i <= 16; i++)

di (i) = TRUE;

for (i = -7; i <= 7; i++)

dn (i) = TRUE;

ensayar (1);

if (acertado)

for (printf ("nnLA SOLUCION ES:nn"), i = 1; i <= 8; i++)

{

for (j = 1; j <= 8; j++)

printf ("%2d", c (j) == i ? 1 : 0);

printf ("n");

}

else

printf ("nnNO HAY SOLUCION.n");

}

void ensayar (int i)

{

int j = 0;

do

{

j++;

acertado = FALSE;

if (f (j) && di (i + j) && dn (i – j))

{

c (i) = j;

f (j) = di (i + j) = dn (i – j) = FALSE;

if (i < 8)

{

ensayar (i + 1);

if (! acertado)

f (j) = di (i + j) = dn (i – j) = TRUE;

}

else

acertado = TRUE;

}

} while (! acertado && j != 8);

}

CONCLUSIÓN

Se puede decir que la recursividad es una técnica de programación bastante útil y muy interesante de estudiar. A través de los ejemplos que el individuo pueda revisar, aprenderá con más rapidez y sencillez lo que es programar recursivamente e incluir esta técnica cuando se le presente un problema como los que fueron mencionados anteriormente. La asignación de memoria, sea estática o dinámica, en realidad se tendrá que aplicar en cualquier programa al momento de su codificación; tomando en cuenta que cada programador tiene su estilo de programar. El ejemplo de las torres de Hanoi tanto como el ejemplo de las ocho reinas son problemas claves que tienen que ver directamente con lo que es la recursividad.

BIBLIOGRAFIA

1.- Tenenbaum, Aaron. Estructura de Datos en C. México 1995.

2.- Páginas Web Visitadas: http://www.ulpgc.es/otros/tutoriales/mtutor/ej-d.html

http://www.uhu.es/nieves.pavon/p2/tema5/5punto11.html

http://193.145.132.15/otros/tutoriales/mtutor/mt2f.html

http://microsoft.com/spain/scripting/jscript/doc/recurse.htm

Autor:

Eloy Pascal

Juan Navas