Fecha y hora actual: Domingo 25 Ago 2019 04:19
Í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: 35- El Stack en Recursión

Responder al Tema

Índice del Foro > Programación en general > Programando desde 0: 35- El Stack en Recursión

Autor Mensaje
Kyshuo Ayame
Moderador Global


Registrado: 07 Ene 2011
Mensajes: 1043

Mensaje Publicado: Martes 01 Nov 2011 17:38

Título del mensaje: Programando desde 0: 35- El Stack en Recursión

Responder citando

Bien, seguimos entonces con este tema tan engorroso, pero créanme que no hay otra opción más que aprenderlo, y yo creo que la mejor manera es hacerlo lentamente. Ojalá vallan siguiendo las lecciones anteriores, tal vez alguien comente en algún momento.

El Stack en Recursión:

Teniendo una idea básica de lo que pasa en el stack de memoria y de cómo hace nuestro programa para “recordar” las cosas cada vez que hay una invocación a un subprograma, veremos qué sucede con la recursión. Recordemos entonces este ejemplo recursivo:

Código:
PROCEDURE Proc(X: CARDINAL);
BEGIN
   WriteCard(X,1);
   WriteString(“ “);
   Proc(X+1);
END Proc;


Supongan el mismo llamado de aquella vez, o sea, Proc(0). En ese momento el programa genera un registro para recordar en qué linea fue hecho el llamado. No hay mucho más para recordar porque no hay variables globales ni nada de lo que haya que recordar valores, por tanto ese registro de memoria será pequeño. Entonces haré lo siguiente, iré numerando los llamados hechos a Proc y nombrando qué es lo que el programa recuerda para cada llamado.

Llamado 1: Estamos en el bloque principal donde asumimos que como única instrucción está el llamado a Proc(0). Al llegar ahí nuestro programa genera un registro más o menos así:

A recordar:

  • No hay variables globales.
  • Proc(0) llamado desde la instrucción 1 del bloque principal.


Llamado 2: Estamos dentro de Proc(0). Imprimimos el 0, el espacio en blanco y llegamos al llamado recursivo Proc(X+1). Como X vale 0, esto equivale a Proc(1). Al llegar ahí, como es un llamado a un subprograma, nuestro programa se genera este registro y lo guarda en el Stack:

A recordar:
  • No hay variables globales.
  • X vale 0.
  • Proc(1) llamado desde la instrucción 3 dentro de Proc(0).


Llamado 3: Estamos dentro de Proc(1). Imprimimos el 1, el espacio en blanco y llegamos a la tercera línea donde tenemos el llamado a Proc(X+1). Como el X del llamado actual vale 1, Proc(X+1) equivale a Proc(2). Al llegar ahí nuestro programa genera este registro:

A recordar:
  • No hay variables globales.
  • X vale 1.
  • Proc(2) llamado desde la instrucción 3 dentro de Proc(1).


Llamado 4: Estamos dentro de Proc(2). Imprimimos el 2, el espacio en blanco y llegamos a la tercera línea donde tenemos el llamado Proc(X+1). Como el X del llamado actual vale 2, Proc(X+1) equivale a Proc(3). Al llegar ahí nuestro programa genera este registro:

A recordar:
  • No hay variables globales.
  • X vale 2.
  • Proc(3) llamado desde la instrucción 3 dentro de Proc(2).


Si continuáramos con la ejecución, nuestro programa seguiría generando registros de cosas a recordar, agregándolos al Stack hasta que este se llenara porque claro está que no es infinito porque la memoria RAM de nuestro ordenador no lo es. Es por este motivo que cuando llenamos la pila de memoria, o sea, nos vamos hasta el cuerno de registros que recordar, el programa cae al intentar guardar un nuevo registro en un lugar donde ya no cabe más nada.

La capacidad de la pila dependerá de su computadora, del sistema operativo que estén usando, del compilador que utilicen para trabajar con Modula 2, y de algunas otras cosas. Lo importante es que hay una pila donde se registran las cosas a recordar la cual no es infinita. Si dibujáramos este ejemplo tendríamos algo así:



Cada recuadro representa un registro de las cosas que se deben recordar. Como verán, el programa coloca cada registro arriba del que estaba anteriormente, y sigue así subiendo en la pila. En este ejemplo, cuando tenemos el llamado número i, o sea, llamamos a Proc(i) desde dentro de Proc(i-1), estaríamos llenando el Stack.
Para que entiendan esto de i, supongan que i es el valor número 15200, o sea, estaríamos llamando a Proc(15200) desde Proc(15199), por eso la notación Proc(i) desde Proc(i-1).

Luego tendríamos el llamado número N, el cual genera ele registro en rojo, que está fuera del Stack esperando a ser agregado. Cuando el programa intenta cargarlo en la pila, como esta está llena, sucede el error Stack Overflow.

Entonces, veremos qué pasa con el Stack en el ejemplo correcto:

Código:
PROCEDURE Proc2(X: CARDINAL);
BEGIN
   IF X=0 THEN
      WriteCard(X,1);
   ELSE
      WriteCard(X,1);
      WriteString(“ “);
      Proc2(X-1);
   END;
END Proc2;


Asumiremos que el bloque principal de nuestro programa es este:

Código:
BEGIN
   Proc2(5);
END ProgramaPrincipal;


Entonces veremos paso a paso a paso qué pasa con el Stack de memoria en este programa, esto les ayudará también a terminar de comprender los ejemplos anteriores.

Al iniciar el programa ya se genera un registro con el estado inicial, o sea, cuantas variables, cuáles son, qué valores tienen, qué constantes hay, etc. Eso no me interesa ahora, lo que me importa es lo referente a los llamados a subprogramas.

Nuestro programa comienza entonces y lo primero que ve es un llamado a Proc2(5). Ahí genera un registro para recordar los valores de las variables y demás (el estado del programa), y a su vez recordar en qué instrucción fue llamado Proc2, en este caso, la primera instrucción del programa principal. Digamos que estaríamos en una situación como esta:



Entonces, ahora que se generó el registro número 1 con cosas a recordar, el programa cede el control a Proc2, entrando en su código fuente y dejando para después lo que hubiera debajo de la invocación. En este caso, no hay nada luego, pero bien podría haberlo.
Entrando en Proc2 tenemos que X vale 5, como no es el caso base, imprimimos el 5, el espacio en blanco y nos encontramos nuevamente con un llamado a Proc2. En este caso el llamado dice Proc2(X-1), que equivale a Proc2(5-1) lo cual es Proc2(4). Entonces tenemos un nuevo registro generado, por lo tanto la situación es la siguiente:



Como podrán observar, el registro número 2 recuerda que no hay variables globales, que el valor de X en ese momento es 5 y que Proc2(4) fue llamado desde la línea 8 del procedimiento, de este modo, cuando termine de hacer lo que Proc2(4) debe hacer, sabrá desde dónde continuar y cómo estaban las cosas en ese momento.

Ahora entramos en Proc2(4). Nuevamente no estamos frente al caso base, por lo cual imprimimos el 4 y el espacio en blanco y llegamos al nuevo llamado Proc2(X-1). Como el X en ese momento es 4 este llamado equivale a Proc2(3). Veamos entonces cómo es la situación en el Stack:



Llegamos entonces a Proc(3). Repitiendo lo anterior, como 3 no es caso base, imprimimos su valor, luego el espacio en blanco y llegamos al llamado Proc(X-1) que equivale a Proc(2). Como eso corresponde a un nuevo llamado, se genera un nuevo registro y se guarda en la pila de memoria:



Si van entiendo todo esto, que es más de lo mismo, sería sencillo ver los registros generados hasta el llamado a Proc(0) dentro de Proc(1) son todos los que pueden verse en la imagen siguiente:



Entonces, en este punto estamos ahora dentro de Proc2(0). Como es el caso base, no entramos en el ELSE sino que nos quedamos en el IF donde solo imprimimos un valor. Como no hubo nuevo llamado a nada no se generó ningún nuevo registro. Entonces, cuando imprimimos el 0 no queda nada por hacer dentro de Proc2(0). Entonces, cuando Proc2(0) termina, el programa va al tope de la pila y se fija qué es lo que tenía que recordar. En este caso, está el registro número 6 que le recuerda que Proc2(0) había sido llamado desde la línea 8 dentro de Proc2(1). Esto es super delicado e importante, así que por favor les pido que lo lean con suma atención:

En esta instancia volvemos entonces a estar dentro de Proc2(1), por tanto el programa recuerda que X valía 1. Se fija que más había para hacer debajo del llamado a Proc2(0), como no había nada, termina entonces con Proc2(1) y borra ese registro de la pila. Si hubieran instrucciones debajo del llamado a Proc2 entonces estas serían ejecutadas, recuerden esto porque lo usaremos luego.
Ahora se fija qué más había por recordar, entonces encuentra el registro número 5 porque el 6 ya fue borrado. Ahí recuerda que Proc(1) había sido llamado desde la línea 8 de Proc(2) y que X en ese momento valía 2. Se fija entonces que hay debajo del llamado a Proc(1) y como no encuentra nada, borra el registro 5 del stack.

Esto continúa así hasta que el programa llega al registro número 1, donde el programa recuerda que Proc2(5) había sido llamado desde la instrucción 1 del bloque principal del programa, continuando entonces desde ahí. En este caso, terminaría su ejecución porque no hay más nada por hacer, pero si lo hubiera, entonces se ejecutaría.

Entonces, si han logrado entender esto veremos cómo quedaría el código para que los números se impriman en orden ascendente y no como sucede ahora, por eso yo les había dicho que imprimir los números en forma descendente complicaba las cosas, porque había que comprender antes el funcionamiento del Stack de memoria y cómo Modula lo utiliza para “recordar” lo que estaba haciendo en cada llamado recursivo.

Código:
PROCEDURE Proc(X: CARDINAL);
BEGIN
   IF X=0 THEN
      WriteCard(X,1);
   ELSE
      Proc2(X-1);
      WriteString(“ “);
      WriteCard(X,1);
   END;
END Proc;


Como podrán observar, lo único que ha cambiado es que he puesto las instrucciones de imprimir en pantalla debajo del llamado recursivo y a su vez las he invertido, o sea, antes imprimíamos primero el número y luego el espacio en blanco pero ahora lo hacemos al revés. Seguiré un ejemplo sencillo aunque sin ilustraciones, sobre el funcionamiento de este procedimiento que en vez de llamarlo Proc2 simplemente lo llamé Proc porque es bastante molesto tener que poner el 2 al final de cada vez que nombro a Proc2, jeje, la mitad de las veces me olvidaba de hacerlo.
Supongan entonces que Proc es llamado desde el bloque principal de esta manera:

Código:
BEGIN
   Proc(2);
END ProgramaPrincipal;


Hago el llamado con un simple 2 para acortar el seguimiento del ejemplo ya que la idea es que terminen de comprender todo lo que les he ido explicando hasta el momento:

Al llegar entonces al llamado a Proc(2) nuestro programa se genera un registro que dice:

Registro 1:
  • Proc(2) fue llamado desde la instrucción 1 del bloque principal.

Esto es simplemente para recordar desde donde continuar luego de Proc(2) termine su ejecución.

Bien, entrando entonces en Proc(2), tenemos que X vale 2. Como no es caso base, entonces vamos al ELSE de nuestro IF. Allí tenemos un llamado recursivo Proc(X-1), o sea, Proc(1). En ese momento se crea el nuevo registro y entraremos a Proc(1). ¿Qué pasará entonces con las instrucciones que hay debajo? Pues serán ejecutadas luego, cuando nuestro programa comience la regresión mirando qué es lo que debía recordar en cada momento. El registro que tenemos ahora es:

Registro 2:
  • Proc(1) fue llamado desde la instrucción 6 dentro de Proc(2).
  • X vale 2.


Entramos ahora en Proc(1), como tampoco es caso base, pasamos al ELSE donde tenemos enseguida el llamado a Proc(X-1), o sea Proc(0). Nuevamente queda pendiente realizar las instrucciones de impresión en pantalla, sin embargo serán realizadas luego. El registro generado es este:

Registro 3:
  • Poc(0) llamado desde la instrucción 6 dentro de Proc(1).
  • X vale 1.


Entramos entonces en Proc(0). Este es el caso base, por tanto entramos en el IF y lo único que tenemos es la instrucción WriteCard(X,1), por lo tanto se imprime el 0 en pantalla. Como no hay nada más por hacer, Proc(0) termina su ejecución. Entonces ahora el programa automáticamente va al Stack y se fija qué hay allí. Se encuentra con el Registro 3 ya que fue el último en ingresar a la pila. Allí recuerda que Proc(0) había sido llamado desde la instrucción 6 dentro de Proc(1) y que X en ese momento valía 1. Entonces avanza a la instrucción 7 y allí imprime un espacio en blanco y luego el valor de X. Como el programa recuerda que X valía 1, entonces imprime el 1. En pantalla entonces tenemos ahora: 0 1.

Habiendo entonces terminado con las instrucciones de Proc(1), se borra el registro del Stack y el programa se fija ahora que más hay ahí. Se encuentra entonces con el Registro 2. Ahí tiene que Proc(1) había sido llamado desde la instrucción 6 dentro de Proc(2), por lo tanto volvemos a estar dentro de Proc(2). El programa recuerda también que X en ese momento valía 2, entonces, avanza a la instrucción 7, imprime el espacio en blanco y luego el valor de X, o sea el 2.

Terminamos entonces con Proc(2) por lo tanto se borra el Registro 2. El programa va entonces al Registro 1 donde lo único que había era que Proc(2) había sido llamado desde la instrucción 1 del bloque principal, o sea que sigue desde allí. Como no hay nada más por hacer, se borra ese registro y el programa termina su ejecución.

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

De todo esto se desprende un viejo dicho: La recursión tiene un proceso de ida y otro de vuelta.

El proceso de ida es aquel en donde se van realizando las tareas antes de los llamados recursivos y se van generando los registros en el Stack a modo de recordar lo que queda pendiente por hacer luego de cada llamado.

El proceso de vuelta es aquel en el que el programa comienza a ver los registros y hace lo que estaba pendiente en cada uno.
En nuestro ejemplo donde imprimíamos todos los números en orden descendente hacíamos las tareas “a la ida” de la recursión. En el ejemplo que acabamos de ver, hacemos las cosas “a la vuelta” de la recursión.
¿Es posible hacer cosas a la ida y a la vuelta? Pues sí. Entonces escriban ustedes el procedimiento Proc que dado un número CARDINAL imprima en pantalla todos los CARDINAL desde ese número hasta el 0 y desde el 0 hasta ese número. Por ejemplo, si le pasamos el número 5 en pantalla saldría esto:

5 4 3 2 1 0 1 2 3 4 5
Si fuera el 10 tendríamos esto:

10 9 8 7 6 5 4 3 2 1 0 1 2 3 4 5 6 7 8 9 10

Esto no es más que unir los ejemplos que ya les dí, pero les servirá como primer ejercicio recursivo.

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

Bien, lo demás vendrá en la siguiente lección que lamentablemenete no será la última acerca de este tema.

Saludos a todos y a todas.

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


Registrado: 05 Sep 2011
Mensajes: 196

Mensaje Publicado: Jueves 20 Sep 2012 06:27

Título del mensaje: Re: Programando desde 0: 35- El Stack en Recursión

Responder citando

Muy claro todo! Exquisito! Ok

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



Registrado: 12 Abr 2013
Mensajes: 3

Mensaje Publicado: Viernes 12 Abr 2013 04:27

Título del mensaje: Re: Programando desde 0: 35- El Stack en Recursión

Responder citando

Sos un genio locoooooo! No imaginas lo que me esta ayudando tu curso de Modula 2 en la facultad! Mil gracias! Saludos de Uruguay Ok Sol

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


Registrado: 07 Ene 2011
Mensajes: 1043

Mensaje Publicado: Viernes 12 Abr 2013 19:12

Título del mensaje: Re: Programando desde 0: 35- El Stack en Recursión

Responder citando

Ese es uno de los objetivos... Gracias por comentar que a tí te está dando resultados. Yo también sufrí con la FIng (y sigo sufriendo) y justamente trato en este curso completar los baches que dejan los profesores.

Saludos.

Volver arriba
Ver perfil del usuario Enviar mensaje privado
Juan333



Registrado: 20 Abr 2013
Mensajes: 4

Mensaje Publicado: Sábado 20 Abr 2013 22:12

Título del mensaje: Re: Programando desde 0: 35- El Stack en Recursión

Responder citando

Estan muy buenas tus lecciones me estan ayudando pila para las entregas de prog 2 muchas gracias!!

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 00:56

Título del mensaje: Re: Programando desde 0: 35- El Stack en Recursión

Responder citando

Okey , E llegado hasta auqi :D wuhu !! ESTA LECCIONN EXCELENTE !! LA ENTENDI SIN DUDAS JAJA XD y la respuesta de como hacerlo es solo un cambio de posicion y ya

Código:
PROCEDURE Proc(X: CARDINAL);
BEGIN
   IF X=0 THEN
      WriteString(' ');
      WriteCard(X,1);
   ELSE

      WriteString(' ');
      WriteCard(X,1);
      Proc(X-1);
      WriteString(' ');
      WriteCard(X,1);
   END;
END Proc;

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


Registrado: 28 Dic 2014
Mensajes: 105

Mensaje Publicado: Sábado 11 Mar 2017 18:17

Título del mensaje: Programando desde 0: 35- El Stack en Recursión

Responder citando

El procedimiento seria
Código:

PROCEDURE Proc(x:CARDINAL);
BEGIN
IF x=0 THEN
 WriteCard(x,1);
ELSE
 WriteCard(x,1);
 WriteChar(' ');
 Proc(x-1);
 WriteChar(' ');
 WriteCard(x,1);
 END;
END Proc;

Como siempre perfectamente explicado, aunque me parece que se complicara mucho cuando tengamos que hacer algo mas complejo

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


Registrado: 07 Ene 2011
Mensajes: 1043

Mensaje Publicado: Domingo 12 Mar 2017 02:10

Título del mensaje: Programando desde 0: 35- El Stack en Recursión

Responder citando

Está bien hecho. Si logras dominar la recursividad ya no habrá quién te pare. Pocos programadores la utilizan. Como ves es un tema complicado hasta que uno lo entiende.

Me alegra que sigas avanzando.

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

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
El foro no contiene ningún mensaje nuevo

Llamada a web service desde form

mrrobot2 Programación Web en general 1 Martes 14 Nov 2017 00:50 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,