Fecha y hora actual: Domingo 25 Ago 2019 05:32
Índice del Foro

Foros de programación informática, diseño gráfico y Web

En esta comunidad intentaremos dar soporte de programación a todos los niveles, desde principiantes a profesionales de la informática, desarrollo de programas, programación web y mucho más.

Programando desde 0: 36- Aplicando Recursividad - Ejemplo 1

Responder al Tema

Índice del Foro > Programación en general > Programando desde 0: 36- Aplicando Recursividad - Ejemplo 1

Autor Mensaje
Kyshuo Ayame
Moderador Global


Registrado: 07 Ene 2011
Mensajes: 1043

Mensaje Publicado: Viernes 11 Nov 2011 15:57

Título del mensaje: Programando desde 0: 36- Aplicando Recursividad - Ejemplo 1

Responder citando

Lección 36 - Aplicando recursividad

Todo muy lindo, muy hermoso... eso del stack y los registros, el caso base, hay una ida y una vuelta, bla bla bla... ¿Y? ¿Cómo aplico todo esto? ¿Qué uso le puedo dar?

Seguramente ustedes tengan muchas preguntas más incluyendo el para qué sirve esto. Sin embargo, como bien dije, trabajaremos con recursividad a lo largo del curso y pues es allí que encontrarán casos donde utilizar iteración sería inhumano ya que ustedes mismos tendrían que programarse un Stack para recordar qué es lo que les queda por hacer y pues, si el lenguaje nos provee de uno automático, mejor aprovecharlo.

Realmente para trabajar con recursividad se debe enseñar un poco acerca de tipos inductivos, aplicando lo que se conoce como inducción matemática. Sin embargo eso haría que el alcance de este manual escapara solo a aquellas personas que se llevan bien con las matemáticas y han estudiado bastante con ellas. De este modo conocerían lo que es la inducción completa y resultaría para mí muy sencillo explicar los conceptos en que se aplica la recursividad, ya que esta nació justamente del principio de inducción matemática.

Dado que yo quiero que cualquier persona pueda seguir este manual, intentaré enseñarles el concepto de inducción sin utilizar matemáticas, sino más bien intuición.

Entonces, diremos informalmente que un tipo inductivo es aquel que tiene una cantidad variable de elementos, y que si cierta condición se cumple para un elemento, entonces es posible demostrar que se cumple para todos los demás. Imaginen una fila muy larga de personas en la que cada persona, cada vez que alguien le dice algo, automáticamente se lo dice a la persona que está en frente a ella. Imaginen entonces que alguien va y le dice un secreto a la primera persona de la fila ¿Se enterarán entonces todas las personas de la fila del secreto contado?
Y pues sí, ya que la primera persona se lo dirá a la segunda. En ese momento la segunda, al recibir un mensaje, automáticamente se lo dirá a la tercera, que automáticamente se lo dirá a la cuarta, y así sucesivamente hasta llegar al final de la fila.

Podríamos asumir que la fila de personas es eventualmente infinita, o sea, tiene un principio pero no un final, y pues, esta propiedad se cumpliría igualmente para todos los que estén en ella. Normalmente los tipos inductivos, dada una propiedad, requieren que esta sea demostrada matemáticamente mediante inducción completa, o sea, si la propiedad se cumple para un elemento hay que demostrar fehacientemente que se cumple para todos los demás. Como los tipos inductivos en general representan estructuras que pueden ser infinitas, esta demostración muchas veces no es sencilla.

Ustedes conocen ya a las listas encadenadas simples, las cuales representan a un tipo inductivo. Si una propiedad se cumple para uno de sus elementos entonces se cumple para todos. Esta demostración es particular para cada caso pero siempre se puede demostrar, sin embargo a mi no me interesa adentrar en teoría matemática en este curso, así que ustedes deberán asumir que lo que digo es cierto y se cumple.
Lo importante es que, para un tipo inductivo hay que definir tres cosas:

  • El tipo puede ser eventualmente vacío: Si lo aplicamos a la fila de personas podría no haber ninguna persona en ella. Si lo aplicamos a una lista encadenada esta podría no contener ningún elemento.
  • El tipo puede ser no vacío: o sea, puede contener uno o más elementos.
  • Eso conforma todas las posibles formas de dicho tipo, o sea, o es vacío o no lo es.


ste último punto también se demuestra. Si pensamos en los números naturales (CARDINAL), o sea, los que van de 0 en adelante, es decir: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 …. N; podemos tener el 0, que representa la nada, lo vacío, lo nulo; o bien podemos tener otro número. Esto es lo que nos ayuda a definir nuestros casos base. Por lo general, el caso base está representado por la nulidad, es decir, por la forma nula o vacía de nuestro tipo de datos. Si trabajamos con una lista encadenada, un caso base sería la lista vacía.

Entonces, veremos un poco de cómo nos definimos estos puntos para trabajar con recursividad. Esto es algo que en general no encontrarán por la web ni en ningún libro o manual que hable de recursividad. Si alguno ha encontrado algo, entonces léalo y complemente esa lectura con esta. Yo intentaré que este manual sea suficiente.

Insertar un número al final de una lista de enteros:

Veremos entonces, dada una lista de números enteros, cómo hacer para insertar un número al final de la misma. Veremos entonces más de una forma de hacer lo mismo, indicando cuál es la mas correcta. El hecho de que se presente más de un ejemplo acerca de una misma cosa es para evitar los errores más comunes que cometen los programadores novatos, errores difíciles de captar y que luego dan un enorme dolor de cabeza cuando el programa no hace las cosas como queremos y no sabemos por qué.

Veremos primero la forma iterativa de lograr esto, y luego la forma recursiva. Tendremos entonces una función que recibe como parámetros una lista de números enteros, un entero y devuelve la misma lista pero con el entero agregado.

Aquí es donde tenemos un punto a discutir: vamos a agregar un número en una lista encadenada. ¿Devuelvo la misma lista o devuelvo otra lista que es copia de la primera y además agrega el nuevo número? O sea ¿modifico la lista que me pasan como parámetro o creo una nueva dejando la otra intacta?

Supongan que la lista es de tipo IntegerList como se declara a continuación:

Código:
TYPE
   IntegerList= POINTER TO NodoInteger;
   NodoInteger= RECORD
                 numero: INTEGER;
                 siguiente: IntegerList;
              END;


Entonces supongan que tenemos la función AgregarNumeroLista declarada como sigue:

Código:
PROCEDURE AgregarNumeroLista(l: IntegerList; n: INTEGER): IntegerList;


En esa firma no queda para nada claro si modificamos la lista original o retornamos una nueva. Esto lo discutiremos mucho en todos los casos, y veremos como hacer esto más claro. En primer lugar, si a ustedes le pasan esa firma y les dicen que tienen que implementar esa función no sabrá cuál es el comportamiento correcto. Parecería más adecuado que se modifique la lista que nos pasan como parámetro, pero en realidad no lo sabemos. Puede que el cliente quiera que no sea así.

Por esto es muy importante que las cosas estén siempre claras. De este modo, quien escribió la firma de esa función, que seguramente fue un diseñador, debe aclarar con comentarios cuál debe ser el comportamiento. Sin embargo veremos luego alguna sutileza que nos pueda ayudar a saber qué hacer.

En este ejemplo, haremos los dos casos para que ustedes vean cómo se hace

Caso 1 iterativamente:

Aquí retornaremos la misma lista modificada, o sea, no haremos una copia.

Código:
PROCEDURE AgregarNumeroLista(l: IntegerList; n: INTEGER): IntegerList;
VAR
   iter: IntegerList;
BEGIN
   IF l=NIL THEN
      NEW(l);
      l^.numero:= n;
      l^.siguiente:= NIL;
   ELSE
      iter:= l;
      WHILE iter^.siguiente<>NIL DO
         iter:= iter^.siguiente;
      END;
      NEW(iter^.siguiente);
      iter:= iter^.siguiente;
      iter^.numero:= n;
      iter^.siguiente:= NIL;
   END;
   RETURN l;
END AgregarNumeroLista;


Veamos entonces. Recibimos como parámetro por valor una lista l. ¿Qué significa esto? Pues, supongamos que tenemos una lista llamada Lista que contiene cuatro números, como vemos a continuación:



Como siempre, una lista es un puntero al primer elemento, luego cada elemento apunta al siguiente, y así, hasta que uno no apunta a nada, o sea, a NIL. Entonces, imaginen este llamado a la función AgregarNumeroLista:

Código:
AgregarNumeroLista(Lista,22)


O sea, lo que queremos hacer allí es agregar el 22 al final de nuestra lista Lista. Como Lista es pasado por copia, lo que tenemos dentro de AgregarNumeroLista es justamente una copia de la variable Lista, o sea, un puntero l que apunta al mismo lugar que Lista, es decir, un alias. De este modo, dentro de la función tendríamos esto:



Deben tener bien claro que aunque Lista es una variable global y es accesible desde dentro de la función, nosotros no debemos acceder a ella nunca, sino que debemos arreglarnos con los parámetros. Si dentro de la función usamos explícitamente a Lista, estaríamos volviendo dependientes de lo que pasa fuera de la función, y esa no es la idea de los subprogramas. Si luego a alguien se le antoja cambiarle el nombre de Lista a MiLista, debería cambiar también toda la implementación de AgregarNumeroLista.

Entonces, como l es un parámetro por valor, al pasar como parámetro efectivo a Lista, lo que obtenemos es una copia del valor de Lista, o sea, otro puntero que apunta al mismo lugar que Lista. Esto, con punteros es muy tramposo, porque si nosotros modificamos a lo que apunta l, estamos modificando a lo que apunta Lista ya que ambas variables miran a un mismo lugar de memoria. Es casi como si fuera pasaje de parámetros por referencia, pero no lo es. Algunos lenguajes no tienen el pasaje de parámetros por referencia ya que manejan punteros y pues, como ven, es casi lo mismo. Sin embargo nosotros haremos énfasis en ambas cosas y tendremos pasaje de parámetros por referencia incluso con punteros.

Imaginen que dentro de AgregarNumeroLista hacemos DISPOSE(l):



Liberamos el lugar de memoria al que apunta l dejando a este indefinido. Como Lista apuntaba al mismo lugar queda también indefinido. ¿Y el resto de la lista? Pues queda perdido en algún lugar de la nada e inaccesible ya que nadie apunta a ella y por ende nadie sabe llegar hasta allí. Esa memoria será liberada más adelante por el sistema operativo ya que este se dará cuenta de que eso no está referenciado por nadie y lo tomará como basura. Sin embargo, eso sucederá después, no es bueno tener programas que no liberan bien la memoria porque la llenaremos, y les aseguro que la llenaremos rápidamente sin importar cuanta tengamos disponible.

Lo que allí figura como un signo de interrogación en realidad no es nada, las variables no apuntan a ningún lado de memoria, pero tampoco valen NIL, por lo tanto no podemos trabajar con ellas hasta que les demos un valor, sea NIL, sea el mismo valor de otro puntero, o que les hagamos NEW.

Ahora bien, dado que l es un parámetro por valor, si en vez de hacer DISPOSE hacemos NEW(l), tendríamos esto:



Como l es un puntero que apunta inicialmente al mismo lugar que Lista, al hacer NEW(l) simplemente lo estamos redefiniendo. De este modo ahora l apunta a otro lado pero Lista sigue intacto. Si l fuera un parámetro por referencia sí habríamos afectado a Lista porque Lista y l serían la misma variable. Como ven, esto es super complejo. Hay que tener muchísimo cuidado con lo que estamos haciendo en todo momento.

Teniendo esto bien claro, analicemos el código. Como podrán ver, tenemos un IF...ELSE principal, el cual divide el código en dos casos: La lista es vacía o bien no lo es.

Si es vacía, o sea, si el parámetro l inicialmente está apuntando a NIL, creamos entonces un nuevo lugar de memoria mediante NEW, le asignamos el valor de n a l^.numero y además decimos que no hay siguiente elemento, o sea, l^.siguiente:= NIL.



O sea, Lista apunta a NIL. Como pasamos la variable Lista como parámetro efectivo en el llamado a AgregarNumeroLista, el parametro l también queda apuntando a NIL.
Entonces, dentro del IF nuestra primera sentencia es esta:
Código:
NEW(l);


Con lo cual creamos un nuevo lugar de memoria para almacenar algo del tipo NodoInteger, lo cual es un registro con dos campos, un número y un puntero a otro NodoInteger. Si ilustramos, tenemos esto:



De este modo teníamos inicialmente esto:

  • Lista sigue apuntando a NIL, o sea, no la hemos modificado en absoluto.
  • El nuevo registro generado, al que apunta la variable puntero l, existe pero no tiene inicializados ninguno de sus campos.


Luego, tenemos estas asignaciones:

Código:
l^.numero:= n;
l^.siguiente:= NIL;


Lo que hacen es justamente inicializar los campos del nuevo registro creado. Con eso tendríamos esto:



Eso finaliza con las instrucciones del IF, entonces ahí vamos a la sentencia final de nuestra función y vemos un RETURN l. Lo que estamos haciendo allí es devolver la dirección a la que apunta l. En síntesis, si la lista está vacía la inicializamos con un nuevo “objeto” y le asignamos al mismo los valores correspondientes.

De este modo, si nosotros queríamos modificar la misma lista que teníamos (en este caso nula), el llamado a la función AgregarNumeroLista debía ser así:

Código:
Lista:= AgregarNumeroLista(Lista,22);


O sea, asignamos a la variable Lista el valor que devuelve AgregarNumeroLista pasándole justamente la misma variable Lista como parámetro.

Esto es sumamente importante. Imaginen si tenemos dos variables del tipo IntegerList.



¿Qué pasa si hacemos este llamado a AgregarNumeroLista?
Código:
Lista2:= AgregarNumeroLista(Lista1,10);





Le estamos pasando a AgregarNumeroLista como parámetro efectivo la variable Lista1 y el número 10, como si le quisiéramos agregar dicho número a Lista1. Sin embargo estamos asignando el resultado a Lista2, que ya tiene dos números.

Como Lista1 es vacía, dentro de la función l valdrá NIL, entonces estaremos dentro del IF como en el ejemplo anterior. De este modo ya sabemos que la función creará una nueva lista apuntada por l con el número pasado, en este caso tendríamos esto:



Entonces, al llegar al final de la función tendremos RETURN l, o sea, retornamos la dirección hacia donde apunta l. Como quién recibe este valor será Lista2, tendríamos esto:



Lista2 recibió una nueva dirección de memoria hacia la cual apuntar, por lo tanto perdió la anterior. ¿Qué pasa con los registros que contienen al 9 y al 25? Quedan perdidos en memoria, inaccesibles pero ocupando espacio. Eso no debe pasar. Entonces ya sabemos que para el caso en que pasamos como parámetro una lista vacía debemos utilizar también esa misma lista para la asignación, o sea, esto:

Código:
MiLista:= AgregarNumeroLista(MiLista,numero);


Debemos ver entonces qué pasa cuando la lista que pasamos como parámetro no es vacía, es decir, tiene al menos un elemento. Supongamos entonces que pasamos la lista que teníamos como primer ejemplo, y como número pasamos el 22:



Como no es vacía, entramos entonces en el ELSE de nuestro código. La primera instrucción es:

Código:
iter:= l;


como iter está declarada del tipo IntegerList, podemos hacer esa asignación. Tenemos encones esto:



Entonces tenemos este WHILE:

Código:
WHILE iter^.siguiente<>NIL DO
    iter:= iter^.siguiente;
END;


¿Qué hace? Se fija si el lugar al que apunta iter tiene o no un siguiente. En caso afirmativo hace que iter apunte al siguiente. Veámoslo, partiendo de la posición de la ilustración anterior:

La condición del WHILE dice iter^.siguiente<>NIL, en este caso no es así, entonces hacemos que iter apunte hacia el siguiente mediante la asignación iter:= iter^.siguiente:



El WHILE volverá a su encabezado y se fijará si el siguiente a iter es vacío. No lo es, entonces iter apuntará justamente a ese:



Pasará lo mismo hasta apuntar al -15:



Llegada esta instancia, el WHILE se fijará si el siguiente a iter no es NIL. Como sí es NIL se detendrá, dejando a iter apuntando justo al último elemento de la lista. Habiendo salido del WHILE tenemos esta sentencia:

Código:
NEW(iter^.siguiente);


Lo que hace es pedir un nuevo lugar de memoria asignándoselo al siguiente a iter, o sea, el puntero que apunta a NIL ya no apuntará a NIL sino que tendremos un nuevo elemento:



Luego tenemos esta asignación que lo que hace es que iter apunte al nuevo lugar creado:

Código:
iter:= iter^.siguiente;




Finalmente actualizamos los valores del nuevo registro:

Código:
iter^.numero:= n;
iter^.siguiente:= NIL;




Finalmente retornamos el valor de l, que como podrán observar sigue apuntando al mismo lugar desde el principio.
Aquí debemos hacer lo mismo que si Lista fuera vacía, o sea, el llamado a la función debía ser este:

Código:
Lista:= AgregarNumeroLista(Lista,22);


Cabe destacar que Lista ya estaba modificada. Si ustedes miran la ilustración, Lista sigue apuntando a la lista original, lo que nosotros hicimos fue modificar dicha lista, casi como si fuera un parámetro por referencia. ¿Por qué digo esto? Porque Lista fue pasado como parámetro por valor y sin embargo la lista a la que apuntaba cambió al agregársele un elemento.

De esta manera, el llamado de más arriba es redundante, ya que estamos asignando a Lista el mismo valor que ya posee.
Si volvemos al ejemplo de las dos listas, pero intercambiamos de lugar Lista1 y Lista2 en el llamado, pasaría esto:

Recuerden



El llamado sería este:
Código:
Lista1:= AgregarNumeroLista(Lista2,22);


Lista2 apuntaría a la misma lista pero con el nuevo elemento, y asignaríamos a Lista1 justamente ese valor:



Como ven, se agregó el elemento a la lista y ambas variables, Lista1 y Lista2, quedaron apuntando al mismo lugar. Esto, tal vez sería interesante para algo, pero no es la idea. De este modo, el llamado a AgregarNumeroLista debe ser siempre asignando el retorno a la misma variable que se pasa como parámetro. Eso debe ir aclarado en los comentarios de la función.

Algo que tal vez alguno de ustedes se pregunte es ¿por qué uso un puntero llamado iter para recorrer la lista? ¿Por qué no uso el mismo parámetro l?

Es cierto, puedo recorrer la lista usando l para insertar el nuevo número ya que si cambio el valor de l no cambio el de Lista. Ahora bien, supongan que recorremos la lista usando l y no iter, al final tendríamos esto:



La variable Lista apunta al inicio de la lista y l al final. Aparentemente todo está en orden, pero... ¿qué devolvemos en nuestra instrucción RETURN? Si ponemos RETURN l como hicimos hasta el momento, devolveríamos un puntero al final de la lista, en este caso al 22, sin poder acceder al resto de la misma porque no podemos navegar hacia atrás. Dentro de la función, quién traía el puntero al inicio de la lista era l, pero lo modificamos y ya no tenemos más esa dirección.

Es por eso que usé un puntero auxiliar al que llamé iter, para mantener a l apuntando al inicio de la lista y luego retornar ese valor. Mucho ojo siempre con lo que están haciendo, los punteros son de lo peor para generar errores y sobretodo para detectarlos. No saben las hojas y hojas que he gastado en mi vida haciéndome estos dibujitos al seguir la ejecución de mis programas para detectar qué es lo que está fallando.



Caso 1 recursivamente:

Veremos entonces exactamente la misma función pero utilizando recursión. Cambiaremos la implementación, no la funcionalidad, o sea, seguirá recibiendo los mismos parámetros y retornará la lista modificada.
Esta es una de las ventajas de modularizar los programas, o sea, quiero cambiar la implementación de una funcionalidad por otra mejor. Perfecto, lo hago, cambio la forma en que trabaja AgregarNumeroLista manteniendo la misma firma. De este modo solo cambio su código y no tengo que tocar más nada, o sea, no se cuantas veces se usa esa función en otras partes del programa ni me importa, modifico su código y listo, si lo hice bien todo seguirá funcionando.

Esta ventaja se extenderá aún más cuando comencemos a programara módulos por separado, sin embargo debemos primero terminar con esto de recursión.

Código:
PROCEDURE AgregarNumeroLista(l: IntegerList; n: INTEGER): IntegerList;
VAR
   aux: IntegerList;
BEGIN
   IF l=NIL THEN
      NEW(l);
      l^.numero:= n;
      l^.siguiente:= NIL;      
   ELSIF l^.siguiente= NIL THEN
      NEW(l^.siguiente);
      l^.siguiente^.numero:= n;
      l^.siguiente^.siguiente:= NIL;      
   ELSE
      aux:= AgregarNumeroLista(l^.siguiente,n);
   END;
   RETURN l;
END AgregarNumeroLista;


Veamos esto. Lo primero que tenemos que hacer para comenzar a formular un algoritmo recursivo es definirnos los casos base. Siempre los casos base son aquellos que pueden resolverse de inmediato, sin necesidad de realizar tareas extra.

  • La lista es vacía: Para lo cual simplemente creo el nuevo elemento tal como en la versión iterativa y lo retorno.
  • La lista tiene un único elemento: Para lo cual simplemente creo el nuevo elemento en el puntero siguiente.


Para este caso yo me definí dos casos base:

Si la lista tiene más de un elemento ya no tengo una solución inmediata porque debo recorrerla hasta llegar al final y así poder agregar el nuevo elemento. Es allí donde tendré el llamado recursivo.

De este modo tenemos un IF que captura el primer caso base, un ELSIF que captura el segundo caso base y finalmente el ELSE que tiene el llamado recursivo.

Esta versión tiene algo que es bastante sucio. Me he declarado un puntero aux (en vez de llamarse iter lo llamé aux porque no es un iterador) el cual recibe el retorno de la función en cada llamado recursivo. ¿Por qué esto? Porque como justamente es una función cada vez que es llamada debe retornar algo. Si fuera un procedimiento no hace falta eso, pero las funciones tienen esa propiedad que las diferencia.

Para que vean la idea, el llamado recursivo pasa como parámetro el puntero siguiente al actual en la lista, o sea, pasa una lista que inicia una posición más adelante que la actual. El parámetro n siempre es el mismo.

Si han entendido los ejemplos hasta el momento, no será muy difícil seguir este. Me tomaré la molestia de hacer un paso paso porque se que esto es nuevo y pues, los ejemplos anteriores no aplicaban recursividad cuando debemos devolver un valor.
Supongan entonces que tenemos una lista llamada Lista la cual es vacía, o sea, apunta a NIL:



El llamado a AgregarNumeroLista es así:
Código:
Lista:= AgregarNumeroLista(Lista,20).


Entonces al entrar en la función tendremos el primer caso base, con lo cual se generará un nuevo registro y se retornará su dirección. Esto es idéntico al caso iterativo.

Ahora imaginen una lista Lista con un único elemento:



Si hacemos el llamado pasando esta lista tendremos el segundo caso base y pues no aplicamos recursión allí sino que generamos directamente el nuevo registro en la lista.

Veamos entonces una lista con tres elementos:



El llamado es así:
Código:
Lista:= AgregarNumeroLista(Lista,40);


Este es el primer llamado, tenemos entonces el puntero l hacia el primer nodo de la lista. Como no es ninguno de los caso base, vamos al ELSE de nuestra función. Allí le asignamos a aux el valor de llamar a la función con el siguiente nodo de la lista. De este modo, como hemos hecho un llamado recursivo nuestro programa recuerda que

  • l apunta al nodo que contiene el 50.
  • aux está esperando recibir un valor.
  • Queda pendiente la instrucción RETURN l al final del código.




Bien, hemos entrado al segundo llamado. El parámetro l en esta instancia apunta ahora al segundo nodo de la lista. Como no es ninguno de los casos base tenemos la misma situación anterior:
  • l apunta al nodo que contiene el 20.
  • aux queda a la espera del resultado del nuevo llamado.
  • Queda pendiente la instrucción RETURN l al final.




Como verán he tomado otra ilustración; no coloco los registros de recuerdos aparte, sino que les dibujo allí mismo lo que va quedando pendiente en cada llamado.

Estamos entonces en el tercer llamado, donde l apuntará al tercer nodo de la lista. Esto representa un caso base, o sea, el siguiente al tercer nodo es vacío, por lo tanto creamos el nodo. Como ahí no tenemos llamado recursivo, pasamos a la instrucción final que es el retorno de l. En esta instancia l apunta al tercer nodo, por lo tanto estamos devolviendo esa dirección al aux que estaba esperando en el llamado anterior. Aquí comienza la ida hacia atrás.

En el segundo llamado aux estaba esperando recibir un valor. En el tercer llamado justamente retornamos ese valor y por tanto aux ya no espera nada. Como eso está hecho, el programa hará lo otro que tenía pendiente, o sea retornar l. Veamos la situación ilustrada cuando el tercer llamado se ejecuta, crea el nuevo nodo y devuelve el valor a aux:



Como ven, el aux del segundo llamado ahora apunta al nodo que tiene el numero 30, justo al que apuntaba el l del tercer llamado. Vayan con cuidado leyendo esto porque se que se complica. Estoy intentando hacerlo lo más claro posible.

Estando de nuevo en el segundo llamado y habiendo aux recibido su valor, recordemos lo que estaba en los recuerdos de ese llamado:
  • l apunta al nodo que contiene el 20.
  • aux queda a la espera del resultado del nuevo llamado.
  • Queda pendiente la instrucción RETURN l al final.


Allí vemos que solo tenemos pendiente retornar el valor de l. Como vemos allí, el l de esta instancia apunta al nodo con el número 20, entonces retornamos ese valor al aux del llamado anterior. En la ilustración creo que se ve bien. Entonces, la situación cuando el segundo llamado culmina y volvemos a estar en el primero es esta:



El parámetro aux de esa instancia recibe su valor y por lo tanto solo queda pendiente retornar el valor de l en ese momento. Como ven allí, el l del primer llamado apunta al nodo con el 50, justo al primero de la lista. Ese es el valor que retornamos y por tanto el valor que recibe Lista. Es así que Lista sigue apuntando a donde apuntaba y tiene además el nuevo nodo agregado.

¿Para qué sirve aux? Pues simplemente es una variable auxiliar para la vuelta atrás de la recursión ya que a mí solo me interesa retornar el l del primer llamado. Por eso capturo todos los retornos de los llamados recursivos en esa variable auxiliar y no los uso para nada. Luego veremos otros casos donde sí utilizamos el retorno, pero vamos poco a poco. La cosa se complica cada vez más.

Esto que yo he hecho con aux es un método un tanto sucio, pero responde al mal diseño de la función. Por esto les mostraré cómo se hacer correctamente.

NOTA: Aunque ya lo dije varias veces y está implícito en las explicaciones lo recalco: Cada nuevo llamado recursivo tiene sus propios parámetros y sus variables locales. Es así que el l y el aux del primer llamado no son el mismo l ni el mismo aux que los del segundo llamado sino que son independientes, variables a parte. Esto significa que lo que hace el lenguaje es duplicar las variables en cada llamado recursivo y almacenarlas en el stack.

Eso ha sido todo por esta lección. Queda otra con un segundo ejemplo, el correcto, antes de ir a los ejercicios de aplicación, que desde ya les adelanto que no serán sencillos. Luego comenzaremos con la programación modular.

Saludos.

Volver arriba
Ver perfil del usuario Enviar mensaje privado
Sebastián Marcos
Usuario Inquieto


Registrado: 04 Oct 2011
Mensajes: 133

Mensaje Publicado: Jueves 15 Mar 2012 20:02

Título del mensaje: Re: Programando desde 0: 36- Aplicando Recursividad - Ejempl

Responder citando

Hola a todos !!!
Estimado Kyshuo, estoy estudiando este tema de recursión, y se me presentó una duda en uno de los ejemplos, aunque no precisamente en un ejemplo recursivo, sino que es una duda de pasaje de listas como parametros en procedimientos.
En la versión iterativa del programa AgregarNumeroLista, que agrega un elemento entero al final de la lista, se menciona lo siguiente:

"Entonces, como l es un parámetro por valor, al pasar como parámetro efectivo a Lista, lo que obtenemos es una copia del valor de Lista, o sea, otro puntero que apunta al mismo lugar que Lista. Esto, con punteros es muy tramposo, porque si nosotros modificamos a lo que apunta l, estamos modificando a lo que apunta Lista ya que ambas variables miran a un mismo lugar de memoria. Es casi como si fuera pasaje de parámetros por referencia, pero no lo es. Algunos lenguajes no tienen el pasaje de parámetros por referencia ya que manejan punteros y pues, como ven, es casi lo mismo. Sin embargo nosotros haremos énfasis en ambas cosas y tendremos pasaje de parámetros por referencia incluso con punteros."

En este caso, "l" es un puntero que apunta al mismo lugar que "Lista". Si es que "l" se pasa por valor, no me queda claro por qué al modificar el valor de "l" dentro del procedimiento también se modifica el valor de "Lista" ?. Entiendo que "l" y "Lista" son alias, pero si "l" se pasa por valor, yo pensaría que no importa lo que haga con dicho parámetro dentro del procedimiento (asignar otro valor, hacer DISPOSE de él, etc), y que de todos modos "Lista" no se modificaría. Si, encontraría razonable que se modificaría si se pasara por referencia.

Entiendo que mi confunsión proviene de que el trabajo con punteros es más delicado que el trabajo con otros tipos de variables, pero esa parte no me queda del todo claro.

Saludos a todos.

Volver arriba
Ver perfil del usuario Enviar mensaje privado
Kyshuo Ayame
Moderador Global


Registrado: 07 Ene 2011
Mensajes: 1043

Mensaje Publicado: Jueves 15 Mar 2012 22:50

Título del mensaje: Re: Programando desde 0: 36- Aplicando Recursividad - Ejempl

Responder citando

Sebastián Marcos escribió:
Si es que "l" se pasa por valor, no me queda claro por qué al modificar el valor de "l" dentro del procedimiento también se modifica el valor de "Lista"


Justamente porque no estás modificando el valor de l, sino que estás modificando el valor de lo que apunta l. Tal como cualquier variable, l o Lista guardan un valor, dicho valor es una dirección de memoria expresada en hexadecimal (no nos importa).

Modificar el valor de l sería asignarle otro valor al que ya tiene, por ejemplo, hacer NEW(l). Eso modifica su dirección de memoria (no lo que hay en esa dirección), es decir, modifica la flecha pero no lo que apuntaba la flecha.

En ese caso has modificado el valor de l pero Lista seguirá apuntando al mismo lugar que antes.

Imagina esto:

Código:
TYPE punteroEntero= POINTER TO INTEGER;

VAR p: punteroEntero;

BEGIN

   NEW(p);
   p^:= 10;
. . .


La sentetncia NEW(p) le asigna un valor a mi variable p que es un puntero a INTEGER, es decir, le da una flecha que apunte a un lugar de memoria que ha sido reservado para guardar un entero. Decimos que el valor de p es entonces esa flecha (una dirección de memoria, por ejemplo 0x008440A0). El valor de p es algo horrible como lo que te escribí.

La asignación p^:= 10 ¿modifica p?

Pues no, no modifica p porque su valor seguirá siendo 0x008440A0. Esa asignación modifica a p^, es decir, modifica lo apuntado por p, no hacia donde apunta.

De este modo, y regresando a tu pregunta, en el pasaje de parámetros por valor (copia), l y Lista no se interfieren entre sí, solo que l tendrá el mismo valor horrible que Lista, pero si a l le cambias ese valor Lista seguirá igual. Lo que pasa es que si modificas l^ entonces modificas Lista^ porque justamente l y Lista son referencias a ese lugar de memoria.

No se si he sido claro. Cualquier cosa dime y te lo explico de otro modo.

Lo que hay que grabarse es que las variables puntero guardan un valor dirección de memoria, no guardan lo que apuntan. Mi variable p no guarda el valor 10 sino que guarda el valor 0x008440A0. Si yo luego hago

Código:
p^:= 850;


la variable p seguirá valiendo 0x008440A0, lo que he modificado es lo que está guardado en la dirección apuntada por p, es decir, en la dirección 0x008440A0.

Volver arriba
Ver perfil del usuario Enviar mensaje privado
Sebastián Marcos
Usuario Inquieto


Registrado: 04 Oct 2011
Mensajes: 133

Mensaje Publicado: Viernes 16 Mar 2012 06:13

Título del mensaje: Re: Programando desde 0: 36- Aplicando Recursividad - Ejempl

Responder citando

Muchas gracias Kyshuo por la explicación, muy clara como simpre. Había interpretado mal la frase "porque si nosotros modificamos a lo que apunta l, estamos modificando a lo que apunta Lista ya que ambas variables miran a un mismo lugar de memoria".
Nuevamente gracias.

Volver arriba
Ver perfil del usuario Enviar mensaje privado
sr floyd
Usuario Activo


Registrado: 05 Sep 2011
Mensajes: 196

Mensaje Publicado: Miércoles 26 Sep 2012 11:02

Título del mensaje: Re: Programando desde 0: 36- Aplicando Recursividad - Ejempl

Responder citando

EXCELENTE LECCIÓN! saqué muchos apuntes de ella, impecable!
Super

Volver arriba
Ver perfil del usuario Enviar mensaje privado MSN Messenger
mupaxett



Registrado: 09 Jun 2013
Mensajes: 2

Mensaje Publicado: Domingo 09 Jun 2013 03:50

Título del mensaje: Re: Programando desde 0: 36- Aplicando Recursividad - Ejempl

Responder citando

Hola, estoy siguiendo tu tutorial que me está pareciendo buenísimo hasta el momento, y muy bien detallado.

Ahora, me surgió una duda también con el tema del pasaje por valor de punteros a un procedimiento.

En los prácticos de la facultad me recomendaron que cada vez que modifique la estructura que entra al procedimiento, pase el puntero como referencia,
pero con la intención de averiguar cuales eran realmente las diferencias entre uno y otro, me puse a investigar como era que funcionaba todo.

Tengo muy en cuenta que el puntero alias (llamémoslo l ) es una copia del puntero original (llamémoslo L).

Bien, resulta que el contenido de l (el cual será el mismo que L), lo modifico dentro de un procedimiento (que llamo PP).

Si agrego nuevos nodos a la lista desde l, modifica la estructura de L, y ademas si cambio los valores de cualquiera de los nodos de la lista, cada uno de los cambios se mantendrá. (hasta ahi va todo perfecto, ya que aunque el pasaje sea por valor, el acceso a la memoria será igualmente válido ya que lo que modificamos es las cosas a las que apuntamos, y no los punteros).

El problema, recae en que si hago dispose a cualquiera de los nodos de la lista desde l, NINGUNO de los nodos de la estructura se destruye.
De hecho puedo referirme a cualquiera de las posiciones y a la estructura misma desde L una vez terminado el procedimiento, como si nunca hubiera aplicado Dispose sobre algun nodo.

No importa hacia donde quede apuntando l al final del procedimiento, ya que L al no ser pasada como referencia seguiria apuntando a una posicion supuestamente destruida (apuntaria a un slot con basura).

Mi pregunta es: como puede quedar viva esta estructura? No deberia dar error el programa al querer referirme al elemento de L que supuestamente destruí al hacer Dispose(l) dentro del procedimiento?

Para el que le interese, dejo el código.

Código:


MODULE DisposePorValor;
 
FROM SWholeIO IMPORT ReadCard,WriteCard;
FROM STextIO  IMPORT WriteLn, WriteString;
FROM Storage  IMPORT ALLOCATE, DEALLOCATE;
 
CONST
  N = 10;
TYPE
 
  PTe = POINTER TO Te;
 
  Te = RECORD
           e : CARDINAL;
           sig:PTe;
       END;
 
PROCEDURE PP (l:PTe);
BEGIN
  (*el valor cambia*)
  l^.e:=6;
 
  (*el nodo siguiente se va a crear*)
  NEW(l^.sig);
  l^.sig^.sig:=NIL;
  l^.sig^.e:=5;
 
  (*pero el dispose no funciona a pesar de apuntar a lo mismo que el puntero original*)
  DISPOSE(l);
 
END PP;
 
 
VAR
  L: PTe;                                                                     
BEGIN
 
   NEW(L);
   L^.sig:=NIL;
   L^.e:=5;
   PP(L);
 
   WriteCard(L^.e,1);WriteLn;
   WriteCard(L^.sig^.e,1);
 
END DisposePorValor.




La teoria que tenia hasta ahora es que al hacer dispose, no se borraba el contenido de una celda por ser justamente basura, y el valor de una celda sea borrado solo cuando precise mas memoria el programa o el sistema operativo.

Pero no, descartado eso ultimo de que si me refiero a algo de una celda borrada pueda aun asi acceder a el, ya que algo borrado con dispose, debe dar error si o si al querer referirme a el, ya que en la teoria aprendimos que un puntero pasado por valor es como pasarle una estructura por referencia, solo que lo unico que no comparte es el puntero en si, al cual solo le pasamos la direccion de memoria y se la asignamos teniendo en claro que no es el puntero original.

Pero por lo visto, misteriosamente está haciendo copia de la estructura a la que apunta.

La demostracion es el codigo anterior, sumado a éste, en el cual sí da error al querer referirme a una celda basura a la que le hice dispose:

Código:

MODULE algo;
TYPE
  point= POINTER TO HT;
  HT = RECORD
        e:CARDINAL;
        sig:point;
       END;
VAR
    Q:point;
BEGIN
 
  NEW(Q);
  Q^.e:=10;
  DISPOSE(Q);
  WriteCard(Q^.e,1);
 
END algo.



Estoy muy errado al pensar que un puntero pasado por valor no deberia hacer copia de la estructura a la que apunta?



EDIT: acabo de averiguar otra cosa. la estructura SÍ se va a modificar aun cuando se le pasa un puntero por valor, lo unico que pierde valor es el dispose. Si uno se fija bien en el primer código, si con el puntero pasado por valor (l), le haces un cambio de valor al cardinal que contiene L, ese cambio lo hace. La estructura la puede cambiar tranquilamente, tambien puede agregar nuevos nodos a la cola, aun con el parametro pasado por valor y los efectos van a permanecer.

Mas te digo, para no ponerme pesado y demostrar que lo unico que pierde efecto es el dispose (y no en todos los casos, ahora lo voy a demostrar)

Código:
MODULE disposesig;

FROM SWholeIO IMPORT ReadCard,WriteCard;
FROM STextIO  IMPORT WriteLn, WriteString;
FROM Storage  IMPORT ALLOCATE, DEALLOCATE;

CONST
  N = 10;
TYPE

  PTe = POINTER TO Te;

  Te = RECORD
           e : CARDINAL;
           sig:PTe;
       END;

PROCEDURE PP (l:PTe);
BEGIN
  (*el valor cambia*)
  l^.e:=6;

  DISPOSE(l^.sig);
  DISPOSE (l)

END PP;


VAR
  L: PTe;
BEGIN
  (*se crea 1er nodo*)
   NEW(L);
   L^.sig:=NIL;
   L^.e:=5;


  (*el nodo siguiente se va a crear*)
  NEW(L^.sig);
  L^.sig^.sig:=NIL;
  L^.sig^.e:=5;

  (*llama procedimiento*)
  PP(L);

  (*salida*)

  WriteCard(L^.e,1);WriteLn;
  WriteCard(L^.sig^.e,1);

END disposesig.


En este codigo, (que es casi el mismo que el primero solo que modifiqué el procedimiento y alguna pavada mas), se crea el nodo L y su siguiente nodo antes de entrar al procedimiento. Y ya dentro del mismo, borro el nodo al que apunta originalmente L, y antes el que seria el siguiente, y al hacerle dispose, efectivamente lo borra el siguiente pero no el primero.

El programa muestra el valor del primer nodo, y al solicitar acceso al valor del siguiente, da error en tiempo de ejecucion.


Por lo tanto, el pasaje por valor, sí modifica la estructura. Pero por alguna razon, a ese primer nodo en especial parece como si se le hiciera una copia del mismo [o sea, a lo que apunta especificamente]. (Mas que copia, hace un seguro de vida manteniendo todo cambio no destructivo que se haga sobre él dentro del procedimiento) y el puntero original como ya sabemos apuntando hacia él. Con cambio no destructivo me refiero por ej, que su valor tambien puede ser modificado [en esl caso del primer codigo de este post, por ej, se modifica el cardinal dentro del nodo, y al salir, este cambio permanece]

Y de hecho si debuggean eso, se van a dar cuenta en la salida de la pantalla que efectivamente borró todo elemento menos el primero.



...

Ahora, para terminar, otro dato, si en un procedimiento borras primero el primero nodo, y DESPUES todos los que le siguen, hace respaldo de toda la estructura y no solo del primer nodo. Por eso pasa lo de que si queres borrar iterativamente de uno en uno, te guarda toda la estructura.

Pero si borras al reves, del ultimo al primero, se borran todos menos el primer nodo.


Código de lista que se respalda enteramente:

Código:
MODULE disposeIter;
 
FROM SWholeIO IMPORT ReadCard,WriteCard;
FROM STextIO  IMPORT WriteLn, WriteString;
FROM Storage  IMPORT ALLOCATE, DEALLOCATE;
 
CONST
  N = 10;
TYPE
 
  PTe = POINTER TO Te;
 
  Te = RECORD
           e : CARDINAL;
           sig:PTe;
       END;
 
PROCEDURE PP (l:PTe);
VAR aux:PTe;
BEGIN
 
  (*el valor cambia*)
  l^.e:=6;
 
  WHILE l # NIL DO
    aux:=l;
    l:=l^.sig;
    DISPOSE (aux);
  END;
 
END PP;
 
 
VAR
  L: PTe;
BEGIN
  (*se crea 1er nodo*)
   NEW(L);
   L^.sig:=NIL;
   L^.e:=5;
 
 
  (*el nodo siguiente se va a crear*)
  NEW(L^.sig);
  L^.sig^.sig:=NIL;
  L^.sig^.e:=5;
 
  (*llama procedimiento*)
  PP(L);
 
  (*salida*)
 
  WriteCard(L^.e,1);WriteLn;
  WriteCard(L^.sig^.e,1);
 
END disposeIter.



Que viaje xDDD



Por ultimo, para marearme mas: otra curiosidad del pasaje procedimiento por valor.

Hice un procedimiento (no funcion) que pasandole un puntero por valor, logra que el puntero original pase a apuntar a la misma direccion que quedó apuntando el puntero auxiliar dentro del procedimiento:

Código:
MODULE disposeIter;
 
FROM SWholeIO IMPORT ReadCard,WriteCard;
FROM STextIO  IMPORT WriteLn, WriteString;
FROM Storage  IMPORT ALLOCATE, DEALLOCATE;
 
CONST
  N = 10;
TYPE
 
  PTe = POINTER TO Te;
 
  Te = RECORD
           e : CARDINAL;
           sig:PTe;
       END;
 
PROCEDURE PP (l:PTe);
VAR aux:PTe;
BEGIN
 
  (*l en 1er nodo, el valor cambiado permanece. Se intenta borrar primer nodo y l pasa al 2do nodo*)
  l^.e:=6;
  aux:=l;
  l:=l^.sig;
  DISPOSE (aux);
 
  (*l en 2do nodo*)
  l^.e:=10;
  NEW(l^.sig);
  l:=l^.sig;
 
  (*l en 3er nodo*)
  l^.e:=15;
  l^.sig:=NIL;
 
END PP;
 
 
VAR
  L: PTe;
BEGIN
  (*se crea 1er nodo*)
   NEW(L);
   L^.e:=1;
 
  (*el 2do nodo se va a crear*)
  NEW(L^.sig);
  L^.sig^.e:=2;
  L^.sig^.sig:=NIL;
 
  (*llama procedimiento enviandole L*)
  PP(L);
 
  (*salida: Solicito imprimir en pantalla el primer nodos de la lista.
    La salida imprime 15, el cual dado los efectos
    del procedimiento PP deberia ser el contenido del 3ER nodo de la lista y no
    del primero, ya que el valor del primero se cambia a 6 y no a 15.
    Por lo tanto L pasó a apuntar al mismo lugar que quedó apuntando l
    en el procedimiento PP*)
 
  WriteCard(L^.e,1);WriteLn;
 
END disposeIter.

Volver arriba
Ver perfil del usuario Enviar mensaje privado
Kyshuo Ayame
Moderador Global


Registrado: 07 Ene 2011
Mensajes: 1043

Mensaje Publicado: Lunes 10 Jun 2013 03:16

Título del mensaje: Re: Programando desde 0: 36- Aplicando Recursividad - Ejempl

Responder citando

Pues amigo, te has mandado toda una investigación y eso es GENIAAAAAL. Y por supuesto que todo esto te ha dado lugar a confusión.

Déjame decirte que como bien afirmaste al inicio, si pasas un puntero por valor a una operación (sea función o procedimiento) y luego dentro de ella haces DISPOSE del parámetro pues también estás eliminando a lo que apuntaba la variable original.

Y tú dirás "¿Pero si yo te demuestro eso con mi procedimiento PP?" Pues sí, tú en tu procedimiento PP liberas la memoria de tu parámetro y luego puedes acceder a L.

Pasa lo siguiente y esto es muy importante y puede llevar a problemas en tiempo de ejecusión cuando menos lo esperas: Al liberar memoria se le indica al sistema operativo que dicha memoria ya no se necesita y que él puede disponer de ella. En algunos casos el sistema operativo puede dejarla aún allí sabiendo que podrá reclamarla cuando quiera. De esto modo, cuando tú haces DISPOSE(l) tu sistema operativo sabe que puede reclamar ese lugar de memoria pero no lo libera de inmediato, por tanto puedes luego acceder desde L.

Intenta esta prueba:

Código:
  1. NEW(L);
  2. L^.sig:=NIL;
  3. L^.e:=5;
  4. PP(L);
  5.  
  6. FOR i:=0 TO 30000 DO
  7. WriteLn(L^.sig);
  8. END;


Intentamos acceder a L 30001 veces luego de haber liberado ese lugar desde el procedimiento PP. Sería muy posible que el sistema caiga en algún momento. Prueba también, mientras corre ese FOR a abrir algún otro programa en tu PC para obligar al sistema a reclamar memoria.

Como verás, es muy peligroso confiarse de esto, porque normalmente el sistema reclama memoria de inmediato, pero a veces no, sobretodo si no la necesita en ese momento.

¿Por qué si yo hago esto el error sale de inmediato?

Código:
  1. NEW(Q);
  2. Q^.e:=10;
  3. DISPOSE(Q);
  4. WriteCard(Q^.e,1);


Pues porque estás usando DISPOSE sobre la propia Q y luego quieres acceder a la propia Q. La operación DISPOSE indica que la memoria puede ser liberada y marca a Q como indefinido. Sin embargo cuando usas un puntero pasado por valor sucede que usas DISPOSE en tu l y este queda marcado como indefinido, pero L no es afectado en absoluto, seguirá manteniendo su mismo valor (apuntará al mismo lugar), por tanto no quedará marcada como indefinida y seguirás accediendo a ella hasta que a tu sistema se le ocurra liberar definitivamente esa memoria.

Así, por tanto descarto esta afirmación

Cita:
acabo de averiguar otra cosa. la estructura SÍ se va a modificar aun cuando se le pasa un puntero por valor, lo unico que pierde valor es el dispose. Si uno se fija bien en el primer código, si con el puntero pasado por valor (l), le haces un cambio de valor al cardinal que contiene L, ese cambio lo hace. La estructura la puede cambiar tranquilamente, tambien puede agregar nuevos nodos a la cola, aun con el parametro pasado por valor y los efectos van a permanecer.


Entonces, si bien con tu investigación podrías afirmar tus demostraciones, te faltaba ese detalle: Es el Sistema Operativo quién gestiona los recursos (memoria, disco duro, etc) y es él quién tiene la desición final sobre cuando liberarlos u ocuparlos. La operación NEW por lo general es ejecutada de inmediato ya que la petición de memoria es prioritaria. No tendría sentido pedirle memoria al sistema y que este me la de cuando se le antoje. La única falla posible para NEW es que no haya más memoria disponible con lo cual en general fallará el sistema operativo completo (en general primero usará memoria virtual para intentar completar la petición y si no puede saldrá algún mensaje como "MEMORIA INSUFICIENTE" y se colgará todo).

Cita:
Ahora, para terminar, otro dato, si en un procedimiento borras primero el primero nodo, y DESPUES todos los que le siguen, hace respaldo de toda la estructura y no solo del primer nodo. Por eso pasa lo de que si queres borrar iterativamente de uno en uno, te guarda toda la estructura.


Así también refuto esta afirmación. Todo está ligado a lo mismo.

¿Y por qué no lo dijiste desde un principio? Pues para obligarlos a usar NEW y DISPOSE en todo momento sin confiarse en cosas como estas y para generar menos confusión.

Una investigación excelente, de verdad. Si tienes objesiones sobre mis afirmaciones o cosas que discutir pues BIENVENIDAS SEAAAAN!!! Me encanta eso... que analices y concluyas por tí mismo dando tus argumentos que son totalmente válidos. Me encantó eso. Un excelente trabajo. Sigue adelante.

Volver arriba
Ver perfil del usuario Enviar mensaje privado
mupaxett



Registrado: 09 Jun 2013
Mensajes: 2

Mensaje Publicado: Lunes 10 Jun 2013 18:29

Título del mensaje: Re: Programando desde 0: 36- Aplicando Recursividad - Ejempl

Responder citando

Gracias por la rápida contestación.

Lo tuve en cuenta en realidad. Habia puesto algo de "La teoria que tenia hasta ahora es que al hacer dispose, no se borraba el contenido de una celda por ser justamente basura, y el valor de una celda sea borrado solo cuando precise mas memoria el programa o el sistema operativo. "

Pero bueno, no habia hecho ningun test de petición de memoria hasta ahora para ver si la celda de L quedaba sin valor alguno y me saltaba algo distinto.

Acabo de hacer dos pruebas, y los resultados no me agradaron mucho como para sacar conclusiones. A no ser que no haya hecho correctamente los tests, ya que de alguna manera sigo pudiendo acceder a dicho valor.


Prueba 1 - Solo trato de acceder al elemento del nodo siguiente muchas veces, especificamente "2 * MAX(CARDINAL)" veces:

Código:
MODULE DisposePorValorTest;
 
FROM SWholeIO IMPORT ReadCard,WriteCard;
FROM STextIO  IMPORT WriteLn, WriteString;
FROM Storage  IMPORT ALLOCATE, DEALLOCATE;
 
CONST
  N = 10;
TYPE
 
  PTe = POINTER TO Te;
 
  Te = RECORD
           e : CARDINAL;
           sig:PTe;
       END;
 
PROCEDURE PP (l:PTe);
BEGIN
  (*el valor cambia*)
  l^.e:=6;
 
  (*el nodo siguiente se va a crear*)
  NEW(l^.sig);
  l^.sig^.sig:=NIL;
  l^.sig^.e:=5;
 
  (*pero el dispose no funciona a pesar de apuntar a lo mismo que el puntero original*)
  DISPOSE(l);
 
END PP;
 
 
VAR
  L: PTe;
  i:CARDINAL;
BEGIN
 
  NEW(L);
  L^.sig:=NIL;
  L^.e:=5;
  PP(L);
 
  WriteString('****************************************');WriteLn; WriteLn;
  WriteString('* Pido "p^sig.e" MAX(CARDINAL) veces   *');WriteLn; WriteLn;
  WriteString('* por prueba. (Son 2 pruebas en total) *');WriteLn; WriteLn;
  WriteString('* Tiempo de prueba - 4:30 min aprox    *');WriteLn; WriteLn;
  WriteString('****************************************');WriteLn; WriteLn;
 
  WriteString('**********************************');WriteLn; WriteLn;
  WriteString('*        Primera prueba          *');WriteLn; WriteLn;
  WriteString('**********************************');WriteLn; WriteLn;
 
  FOR i:=1 TO MAX(CARDINAL) DO
 
    IF i MOD 1000000000 = 0 THEN
     WriteCard(i,1);WriteString(' ');
     WriteCard(L^.sig^.e,1);WriteLn;
    END
  END;
 
  WriteString('**********************************');WriteLn; WriteLn;
  WriteString('*         Segunda prueba         *');WriteLn; WriteLn;
  WriteString('**********************************');WriteLn; WriteLn;
 
 
 
 
  FOR i:=1 TO MAX(CARDINAL) DO
 
    IF i MOD 500000000 = 0 THEN
     WriteCard(i,1);WriteString(' ');
     WriteCard(L^.sig^.e,1);WriteLn;
    END
  END;
 
 
  WriteString('Prueba finalizada ');
 
 
 
END DisposePorValorTest.



Prueba 2 - Pido memoria para crear y destruir una lista auxiliar Q, unas "2 * MAX(CARDINAL)" veces. A continuacion solicito el valor de L^.sig^.e.

Código:
MODULE DisposePorValorTest2;

FROM SWholeIO IMPORT ReadCard,WriteCard;
FROM STextIO  IMPORT WriteLn, WriteString;
FROM Storage  IMPORT ALLOCATE, DEALLOCATE;

CONST
  N = 10;
TYPE

  PTe = POINTER TO Te;

  Te = RECORD
           e : CARDINAL;
           sig:PTe;
       END;

PROCEDURE PP (l:PTe);
BEGIN
  (*el valor cambia*)
  l^.e:=6;

  (*el nodo siguiente se va a crear*)
  NEW(l^.sig);
  l^.sig^.sig:=NIL;
  l^.sig^.e:=5;

  (*pero el dispose no funciona a pesar de apuntar a lo mismo que el puntero original*)
  DISPOSE(l);

END PP;



VAR
  L,Q: PTe;
  i:CARDINAL;
BEGIN

  NEW(L);
  L^.sig:=NIL;
  L^.e:=5;
  PP(L);

  WriteString('******************************************');WriteLn; WriteLn;
  WriteString('* Creo y destruyo Q, MAX(CARDINAL) veces *');WriteLn; WriteLn;
  WriteString('* por prueba. (Son 2 pruebas en total)   *');WriteLn; WriteLn;
  WriteString('* Tiempo de prueba - 4:30 min aprox      *');WriteLn; WriteLn;
  WriteString('******************************************');WriteLn; WriteLn;

  WriteString('**********************************');WriteLn; WriteLn;
  WriteString('*        Primera prueba          *');WriteLn; WriteLn;
  WriteString('**********************************');WriteLn; WriteLn;

  FOR i:=1 TO MAX(CARDINAL) DO
    IF i MOD 1000000000 = 0 THEN
     NEW(Q);
     DISPOSE(Q);
    END
  END;

  WriteString('**********************************');WriteLn; WriteLn;
  WriteString('*         Segunda prueba         *');WriteLn; WriteLn;
  WriteString('**********************************');WriteLn; WriteLn;

  FOR i:=1 TO MAX(CARDINAL) DO
    IF i MOD 1000000000 = 0 THEN
     NEW(Q);
     DISPOSE(Q);
    END
  END;



  WriteString('Prueba finalizada. L^.sig^.e = ');WriteCard(L^.sig^.e,1);



END DisposePorValorTest2.



Resultado de la prueba 2:

i193.photobucket
.com/albums/z246/mathias_dipaulo/SegundoTest_zps3db7d9e4
.png



PD: Voy a buscar material sobre Asignacion de memoria y sobre Heap. Asi de paso me puedo informar mas aun sobre el tema.





---------------------------------------------------------------------------------
----------------------------------


EDITO: Realicé una tercera prueba, la cual da un resultado distinto.

La maquina usa casi toda la memoria disponible, [solo una variable se cambia de acuerdo a la memoria que posea cada uno en su pc, que está adentro de un FOR, en mi caso la cota superior es 245034].


Luego de consumir la memoria, El valor del elemento de L queda guardado (6), pero L^.sig pasa a valer de 5 a 0, (Si el ultimo for tuviera una cota superior relativamente baja, el valor de L.sig.e se mantendria en 5) aunque aun seguimos teniendo acceso a ambos.



Código:
MODULE DisposePorValorTest3;

FROM SWholeIO IMPORT ReadCard,WriteCard;
FROM STextIO  IMPORT WriteLn, WriteString;
FROM Storage  IMPORT ALLOCATE, DEALLOCATE;

CONST
  N = 10;
TYPE

  PTe = POINTER TO Te;

  Te = RECORD
           e : CARDINAL;
           sig:PTe;
       END;

PROCEDURE PP (l:PTe);
BEGIN
  (*el valor cambia*)
  l^.e:=6;

  (*el nodo siguiente se va a crear*)
  NEW(l^.sig);
  l^.sig^.sig:=NIL;
  l^.sig^.e:=5;

  (*pero el dispose no funciona a pesar de apuntar a lo mismo que el puntero original*)
  DISPOSE(l);

END PP;



VAR
  L,Q: PTe;
  i:CARDINAL;
BEGIN

  NEW(L);
  L^.sig:=NIL;
  L^.e:=5;
  PP(L);

  Q:=L^.sig;

  FOR i:=1 TO 245034 DO (*i = "cantidad donde de error el debugger, menos uno".
                          Si hago i de 1 a 1, el valor siguiente se mantiene en 5.
           Aumentar i hasta saber hasta cuanto llega sin dar error, y ahi veremos como L^.sig^.e cambia a 0*)
     NEW(Q^.sig);
     Q:=Q^.sig;
  END;

  (*Valor de L queda guardado, pero L^.sig pasa a valer de 5 a cero, aunque aun seguimos teniendo acceso a ambos*)
  WriteString('L^.e = ');WriteCard(L^.e,1);WriteLn;
  WriteString('L^.sig^.e = ');WriteCard(L^.sig^.e,1); WriteLn;


END DisposePorValorTest3.

Volver arriba
Ver perfil del usuario Enviar mensaje privado
xRoki
Usuario Inquieto


Registrado: 22 Ago 2013
Mensajes: 71

Mensaje Publicado: Sábado 05 Oct 2013 04:45

Título del mensaje: Re: Programando desde 0: 36- Aplicando Recursividad - Ejempl

Responder citando

EXCELENTEEEEEEEEE LECCION !! en esta leccion aprendi mas de punteros y recobine y volvi a la leccion de punteros de tanto run y run xD y hacer ejrcicios por mi imaginacion los entendi perfectamente como usarlos , buscarlos y todo xd gracias a ti

Volver arriba
Ver perfil del usuario Enviar mensaje privado
jlrods
Usuario Inquieto


Registrado: 03 May 2014
Mensajes: 60

Mensaje Publicado: Martes 31 Mar 2015 15:31

Título del mensaje: Programando desde 0: 36- Aplicando Recursividad - Ejemplo 1

Responder citando

Hola Kyshou, ya he revisado varias veces los ejemplos y estoy tratando de iniciar con los ejercicios propuestos pero tengo algunas dudas. Creo que esto de recursividad mas punteros llegan casi al limite de mi pensamiento abstracto.

La primera duda que tengo es: como podemos leer una lista encadenada desde la entrada estadar, cuyo largo sea definido por el usuario?

Los ejercicos que hecho hasta ahora con punteros, siempre defino un valor fijo que limita las iteraciones para moverse hasta el final de la lista y guardar un valor en cada nodo. No se como decirle a un loop WHILE o REPEAT que deban detenerse cuando llegue al final de la linea...

La segunda duda es conrespecto a los ejemplos de recursion. En este caso, la duda tambien es referente a punteros: Por que en ambas versiones recursivas (Caso1 recursivamente y Caso2 recursivamente) usas la siguiente expresion:

Cita:

ELSIF l^.siguiente= NIL THEN
NEW(l^.siguiente);
l^.siguiente^.numero:= n;
l^.siguiente^.siguiente:= NIL;


Mientras que en las versiones iterativas cuando usas el iterador "iter" en ningun momento aparace un doble acento "^".

Comprendo como funcionan los punteros y entiendo que dada una variable "p" del tipo puntero a INTEGER no es lo mismo que "p^". La primera almacena la ubicaion en memoria de la variable p^ y esta segunda almacena el valor del entero como tal.

Pero dado este caso, donde "l" es del tipo IntegerList (un puntero que apunta a un registro, el cual tiene un puntero del mismo tipo), cual es la diferencia entre l.siguiente y l^.siguiente?

Mas aun... cual es el significado de l^.siguiente^.numero?

En casos previos, donde usualmente utilizabamos un auxiliar para recorrer las listas encadenadas (a veces llamado aux y otras veces apuntaActual), siempre que queriamos modificar algun nodo lo haciamos a traves de dicho auxiliar y por ende bastaba con definir sus parametros asi:

Código:

aux^.numero:= 10;
aux^.siguiente:= NIL;


Como no he podido aclarar estas dudas, aun no he podido enfrentar la recursividad para el ejercicio numero 1, ya que no tengo claro los argumentos que pasare al llamado recursivo.

Muchas gracias como siempre por el valioso apoyo.

Saludos.

Volver arriba
Ver perfil del usuario Enviar mensaje privado
Responder al Tema
Mostrar mensajes anteriores:   
Ir a:  
Todas las horas están en GMT + 2 Horas

Temas relacionados

Tema Autor Foros Respuestas Publicado
El foro no contiene ningún mensaje nuevo

Buenas desde el sur del sur =)

Maugarni Preséntate a la comunidad 1 Jueves 22 Ago 2019 14:09 Ver último mensaje
El foro no contiene ningún mensaje nuevo

Hola desde bcn

Dav2k6 Preséntate a la comunidad 2 Miércoles 26 Jun 2019 19:22 Ver último mensaje
El foro no contiene ningún mensaje nuevo

Ejemplo de código para detectar macros de Office

Medardo Visual Basic .NET 1 Martes 02 Abr 2019 18:17 Ver último mensaje
El foro no contiene ningún mensaje nuevo

Existen problemas al descargar musica desde you...

SusanaP Tu PC 2 Martes 26 Mar 2019 19:22 Ver último mensaje
El foro no contiene ningún mensaje nuevo

hola!! los saludo desde argentina

mery Preséntate a la comunidad 2 Jueves 13 Dic 2018 17:28 Ver último mensaje
Panel de Control
No puede crear mensajes, No puede responder temas, No puede editar sus mensajes, No puede borrar sus mensajes, No puede votar en encuestas,