[ Foro de Pascal ]
Estuve leyendo el hilo sobre ordenamiento usando listas, específicamente el código cuyo link es el siguiente:
http://www.aprendeaprogramar.com/mod/resource/view.php?id=483
Hay una parte que, la verdad, no entiendo nada y, es a la referente a la recursividad. La parte del código que no entiendo es la referente al procedimiento InsertarLista.
Entiendo bien hasta la parte de InsertarLista(1,2), pero, estoy desesperado porque no entiendo nada en la parte de InsertarLista(1,6):
Allí se producen una serie de llamadas recursivas, por el hecho de que 6 es mayor que cualquier valor apuntado por Lista. Así, se producirían las siguientes llamadas al mismo procedimiento:
InsertarLista(Lista(apunta a 2), 6);
___InsertarLista(Lista(apunta a 3), 6);
________InsertarLista(Lista(apunta a 5), 6);
_______________InsertarLista(Lista(apunta a nil), 6);
Como Lista apunta a nil, entonces entraríamos al siguiente else:
else { Si no hay lista }
begin { deberá crearla }
new(r); { reserva espacio }
r^.numero := valor; { guarda el dato }
r^.sig := nil; { no hay nada detrás y }
lista := r
por lo que se reserva espacio para un nuevo elemento, el campo número será igual a 6, y el campo sig igual a nil. Pero, ESTO NO LO ENTIENDO, lista se hace igual a la dirección de esa dirección. Yo me pregunto ¿no se perdería la lista al apuntar la variable lista a 6 y no al primer elemento que debería ser aquel cuyo campo número vale 2?. POR FAVOR, PROFESOR, ESTOY MUY CONFUNDIDO, LE PIDO QUE ME EXPLIQUE.
Muchos saludos.
Le pido al prof. Nacho Cabanes que me de una explicación de lo que hace el programa cuando se llama al procedimiento InsertaLista(l,6). Porque, haciendo el seguimiento del programa, a mí me da como resultado que lista termina apuntando a 6, y sig apunta a nil. El resultado debería ser que el nodo cuyo valor es 5 apunte a al nodo de valor 6 y, lista apunte al nodo de valor 2. Pero mi seguimiento del procedimiento no me da así.
Por favor, prof., explíqueme, es que estoy trabado en ese punto y, de esto depende que entienda otras cosas en cuanto al punto de Recursividad.
Un gran saludo.
Los programas que manejan memoria dinámica son los más difíciles de analizar. Si quieres entender el funcionamiento, hay dos alternativas:
- La más efectiva, pero más trabajosa, es hacer la traza del programa a mano: coger un lápiz y un papel, ir "imitando la ejecución" línea a línea y apuntando el estado de la lista (o la estructura que sea) en cada paso.
- La alternativa "mala" es hacer exactamente lo mismo, pero de forma automática: ampliar el programa para que sea él mismo quien te muestre por dónde va pasando y qué valores tiene cada variable.
El problema es que mostrar el valor de un puntero es algo que no permiten todos los compiladores. Por ejemplo, si intentas mostrar un puntero con Free Pascal obtendrás un error "Error: Can’t read or write variables of this type".
Aun así, intento crearte mañana una versión que muestre parte de su avance, por si te ayuda a seguirlo mejor.
El matiz más importante, que tienes que tener en cuenta: en la llamada recursiva "lista" no se refiere al principio de la lista sino a la posición actual en la que estás insertando o comprobando.
Aquí tienes un ejemplo con el fuente "ampliado con write" para que muestre por dónde va pasando. He tenido que hacer un par de trucos para conseguir que muestre la dirección de memoria en la que se encuentra: "write(ofs(lista^))" en vez de "write(lista)"
---
program EjemploDeListasRetocado;
type
puntero = ^TipoDatos;
TipoDatos = record
numero: integer;
sig: puntero
end;
function CrearLista(valor: integer): puntero; {Crea la lista, claro}
var
r: puntero; { Variable auxiliar }
begin
new(r); { Reserva memoria }
r^.numero := valor; { Guarda el valor }
r^.sig := nil; { No hay siguiente }
CrearLista := r { Crea el puntero }
end;
procedure MuestraLista ( lista: puntero );
begin
if lista <> nil then { Si realmente hay lista }
begin
write(lista^.numero, ' - '); { Escribe el valor }
MuestraLista (lista^.sig ) { Y mira el siguiente }
end;
writeln;
end;
procedure InsertaLista( var lista: puntero; valor: integer);
var
r: puntero; { Variable auxiliar }
begin
writeln('Insertando valor: ',valor, ' Desde: ', ofs(lista^));
write('Parte restante de la lista: ');
MuestraLista(lista);
if lista <> nil then { Si hay lista }
if lista^.numero<valor { y todavía no es su sitio }
then { hace una llamada recursiva: }
begin
writeln('Mayor: Llamada recursiva');
InsertaLista(lista^.sig,valor); { mira la siguiente posición }
end
else { Caso contrario: si hay lista }
begin { pero hay que insertar ya: }
new(r); { Reserva espacio, }
r^.numero := valor; { guarda el dato }
r^.sig := lista; { pone la lista a continuac. }
lista := r; { Y hace que comience en }
writeln('Menor: guardado en ', ofs(r^))
end { el nuevo dato: r }
else { Si no hay lista }
begin { deberá crearla }
new(r); { reserva espacio }
writeln('Creando lista: pos ',ofs(r^));
r^.numero := valor; { guarda el dato }
r^.sig := nil; { no hay nada detrás y }
lista := r; { hace que la lista comience }
end { en el dato: r }
end;
var
l: puntero; { Variables globales: la lista }
begin
l := nil;
InsertaLista(l, 5); { Crea una lista e introduce un 5 }
writeln('Creada la lista en: ', ofs(l^) );
InsertaLista(l, 3); { Inserta un 3 }
writeln('Ahora la lista comienza en: ', ofs(l^) );
InsertaLista(l, 2); { Inserta un 2 }
writeln('Ahora la lista comienza en: ', ofs(l^) );
InsertaLista(l, 6); { Inserta un 6 }
writeln('Ahora la lista comienza en: ', ofs(l^) );
MuestraLista(l) { Muestra la lista resultante }
end.
-----------------
El resultado sería algo como (ligeramente retabulado)
Insertando valor: 5 Desde: 0
Parte restante de la lista:
Creando lista: pos 22276752
Creada la lista en: 22276752
Insertando valor: 3 Desde: 22276752
Parte restante de la lista: 5 -
Menor: guardado en 22276768
Ahora la lista comienza en: 22276768
Insertando valor: 2 Desde: 22276768
Parte restante de la lista: 3 - 5 -
Menor: guardado en 22276784
Ahora la lista comienza en: 22276784
Insertando valor: 6 Desde: 22276784
Parte restante de la lista: 2 - 3 - 5 -
Mayor: Llamada recursiva
Insertando valor: 6 Desde: 22276768
Parte restante de la lista: 3 - 5 -
Mayor: Llamada recursiva
Insertando valor: 6 Desde: 22276752
Parte restante de la lista: 5 -
Mayor: Llamada recursiva
Insertando valor: 6 Desde: 0
Parte restante de la lista:
Creando lista: pos 22276800
Ahora la lista comienza en: 22276784
2 - 3 - 5 - 6 -
-----------------
A partir de ahí puedes ampliar el cuerpo del programa para hacer pruebas con más datos y ver cómo influyen los cambios en la traza de la ejecución.
Muchas gracias por la respuesta. Gracias por tomarse el tiempo de realizar todo ese seguimiento del programa, pero lamentablemente no responde a mi pregunta.
Todo el seguimiento que usted hizo es similar al que yo había hecho. Pero vamos a tomar los resultados que obtuvo para plantear mi duda con más claridad.
Estamos claros en que la lista comienza en el valor 2 cuya dirección es 22276784. Pero vamos a trasladarnos a la parte en la que se realiza la última llamada recursiva, la cual es:
insertaLista(nil, 6); acá entramos a la parte del procedimiento que dice así:
else
begin
new(r);
writeln('Creando lista: pos ',ofs(r^));
r^.numero := valor;
r^.sig := nil;
lista := r;
end
Ahora, si examinamos un poco lo que hace esta parte, vemos que la lista se crea en la posición:
22276800
r^.numero = 6
r^.sig = nil
lista = 22276800 ESTO ES LO QUE NO ENTIENDO.
¿CÓMO LLEGA LISTA A TENER EL VALOR 22276784, SI COMO VIMOS, LISTA FINALIZA CON EL VALOR 22276800?
¿EN QUÉ MOMENTO SE LE ASIGNÓ A LISTA EL VALOR 22276784?
POR FAVOR, EXPLÍQUEME. ES QUE ESTOY ESTUDIANDO RECURSIVIDAD Y YO CREÍA QUE HABÍA APRENDIDO ALGO, PERO AL VER LO QUE SUCEDE EN ESTE CÓDIGO ME DEJÓ DESCONCERTADO.
Agradezco todo el interés y el tiempo que ha tomado en la explicación.
Un gran abrazo y muchos saludos.
Ten en cuenta que, al ser una llamada recursiva, "lista" no es lo mismo que "l": ya no estás en la "cabeza" de la pila, sino mucho más abajo, de modo que no modificas el valor de la "cabeza".
Esa es la parte dificil de recursividad: entender que en cada pasada estás trabajando con datos distintos, aunque la variable se llame igual. Por ejemplo, en este caso si insertas 2 y luego 3, el 3 no lo estás guardando en "l" sino en "l^.sig", porque ya has avanzado por la estructura.
Prueba a hacer la traza de alguno de los ejemplos clásicos de recursividad, como el del factorial. Te ayudará a entenderlo. Piensa cómo se calcular el factorial de 4 de forma recursiva y qué pasos intermedios supone eso, porque en cada nueva pasada se generan datos temporales intermedios, en variables que "aparentemente se llaman igual" pero que no están en la misma posición de memoria, sino que son "nuevas copias".
Como compilador, he usado FreePascal, pero quizá funcione también en TurboPascal, que también tiene la función "ofs", que dice la posición de memoria ("offset") en que se encuentra una variable, con la diferencia de que en MsDos la memoria estaba dividida en segmentos, así que para conocer la posición de memoria hay que saber a qué segmento pertenece, "seg(variable)", además del desplazamiento dentro de ese segmento, "ofs(variable)"
En cuanto al paso del nodo 5 al nodo 6: cuando se inserta el 6, se va avanzando hasta llegar al último nodo, y se ve que su campo "siguiente" es "nil", de modo que se pasa al fragmento:
else { Si no hay lista }
begin { deberá crearla }
new(r); { reserva espacio }
writeln('Creando lista: pos ',ofs(r^));
r^.numero := valor; { guarda el dato }
r^.sig := nil; { no hay nada detrás y }
lista := r; { hace que la lista comience }
end { en el dato: r }
Es decir, se reserva espacio, se guarda el valor, se apunta que no tiene siguiente (su siguiente es nil), y se hace que el valor desde el que se ha llamado, que era "el siguiente de 5" ya no sea "nil" sino "r", es decir, la posición de memoria que el compilador nos ha reservado para el dato "6".
Recuerda que en este fuente, "lista" (posición actual) no es lo mismo que "l" (lista resultante). Al ser una llamada recursiva, el valor de "lista" va cambiando (posición actual), y al llegar a este punto no es la cabecera la toda la lista, sino la posición en la que insertamos ese último dato.
En este fuente, el nombre "lista" no es muy afortunado. Sería mejor "sublista", o "posicionActual", "posicionDeInsercion", "posicionDePartidaDelAnalisis", pero cuanto más detallemos con el nombre de las variables, más largas quedan las líneas y puede acabar resultando incómodo de leer y ser contraproducente. Tómalo como "sublista" si quieres, pero sobre todo, recuerda que es un valor "cambiante".
Tu problema está aquí:
Lo que no logro entender es en qué momento el campo sig del nodo de valor 5 guarda la dirección del último nodo insertado, el cual es de valor 6. No entiendo esto, porque la última llamada es
insertarLista(nil,6);
Cuidado con eso. No es
insertarLista(nil,6);
sino
insertarLista(posicionActual,6);
donde posicionActual valía nil y ahora va a cambiar de valor, para pasar a ser la posición del dato recién creado.
¡Wow!!!. Estoy super agradecido con su explicación, la verdad es que dio en el clavo, eso era precisamente lo que no había entendido. De todas maneras déjemelo explicárselo con mis propias palabras y, usted me responde si es lo correcto o no:
Al haber declarado el parámetro formal "lista" como un parámetro por referencia, cualquier cambio de "lista" se reflejará en el parámetro real, o sea al que llama al procedimiento. En el caso que estamos considerando, la última llamada al procedimiento insertaLista(lista^.sig,valor), le pasa los siguientes valores:
lista^sig(del nodo 5) valdrá nil (al igual que lista del nuevo nodo) y
valor valdrá 6;
esto provoca que se ejecute la última parte del código del procedimiento (o sea el bloque del último else).
Allí, se reserva espacio en memoria para el registro y su dirección se almacena en r.
Ahora, el campo "numero" de r^ se le asignará el valor 6 y,
al campo "sig" de la misma variable dinámica se le asigna "nil".
POR ULTIMO, HACEMOS QUE lista SE LE ASIGNE LA DIRECCION DE r. PERO, COMO SE TRATA DE UN PARAMETRO POR REFERENCIA, ESE VALOR TAMBIÉN LO TENDRÁ LA LLAMADA AL PROCEDIMIENTO insertaLista(lista^.sig,valor).
lista^.sig, PARA LA ÚLTIMA LLAMADA, ESTABA RELACIONADA CON EL NODO CUYO VALOR ES 5, POR LO QUE AHORA DICHO NODO TENDRÁ LA DIRECCIÓN DEL NODO DE VALOR 6, A CAUSA DE ESTA ÚLTIMA LLAMADA Y POR TRATARSE DE VARIABLES POR REFERENCIA.
¿Estoy en lo cierto, sí o no?.
Muy agradecido por su ayuda. Le debo mucho!!!.
Abrazos y saludos.
(No se puede continuar esta discusión porque tiene más de dos meses de antigüedad. Si tienes dudas parecidas, abre un nuevo hilo.)