- Recursividad.
- Propiedades de las definiciones
o algoritmos recursivos. - Cadenas
recursivas. - Definición recursiva de
expresiones algebraicas. - Programación
Recursiva. - Asignación estática
y dinámica de memoria. - Ejemplos.
- Conclusión.
- Bibliografía.
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.
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)
- + fib (1) + fib (2) + fib(5) =
- + 1 + fib(0) + fib (1) + fib (5) =
- + 0 + 1 + fib(5) = 3 + fib (3) + fib (4) =
3 + 1 + fib (0) + fib (1) + fib (4) =
- + fib (1) + fib (2) + fib (4) =
- + 0 + 1 + fib (2) + fib (3) = 5 + fib (0) + fib (1) +
fib (3) = - + 0 + 1 + fib (1) + fib (2) = 6 + 1 + fib (0) + fib
(1) = - + 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.
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:
- una expresión es un término
seguido por un signo mas seguido por un término, o un
término solo - un término es un factor seguido por un
asterisco seguido por un factor, o un factor solo. - 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.
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:
- Si n = = 1, mover el disco único de A a
C y parar. - Mover el disco superior de A a B n – 1
veces, usando C como auxiliar. - Mover el disco restante de A a C.
- 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:
- Se coloca el área de datos vigente a 1
dentro de la pila. - En la nueva área de datos vigente a 2, se
asignan los valores
respectivos n – 1, auxpeg, topeg, y frompeg a los
parámetros. - 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. - Se salta hacia el principio de la rutina
simulada. - Después de completar la rutina simulada,
ésta queda lista parar regresar. Las siguientes acciones se
llevan a efecto: - Se salva la etiqueta de regreso, /, de área de
datos vigentes a 2. - Se eliminan de la pila y se fija el área de
datos vigente como el área de datos eliminada de la
pila, a 1. - 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:
- El cambio de
los parámetros en el área de datos vigente a sus
valores
respectivos. - 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);
}
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.
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