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: 33- Recursión - Introducción

Responder al Tema

Índice del Foro > Programación en general > Programando desde 0: 33- Recursión - Introducción

Autor Mensaje
Kyshuo Ayame
Moderador Global


Registrado: 07 Ene 2011
Mensajes: 1043

Mensaje Publicado: Martes 18 Oct 2011 20:33

Título del mensaje: Programando desde 0: 33- Recursión - Introducción

Responder citando

Habiendo dejado atrás los ejercicios de aplicación, asumiré que ya se llevan bien con Modula y su forma de trabajo. De este modo estaré centrado en enseñarles las nuevas metodologías de programación y no en cómo utilizar el lenguaje.

El tema que comienza aquí me llevará varias lecciones ya que es muy extenso, complejo y sobretodo me obliga a ir lentamente para que se entienda.

Este tema es base esencial del curso y de todo programador, por lo cual lo utilizaremos mucho una vez que lo aprendamos, tanto así que veremos estructuras donde no tenemos más remedio que aplicar recursividad.

Deberán leerlo con mucha atención y preguntar mucho. El trabajo de aprender es de ustedes.

Luego de esto comenzaremos de una vez por todas con la programación modular.

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

Recursión

Recursión, Recursividad, Recurrencia, son todos sinónimos para nosotros. Debo decirles francamente que este es uno de los temas más difíciles de entender y sobretodo, una vez que creemos que lo hemos entendido, de utilizar. Lamentablemente, si no lo entienden ahora, el resto del tutorial será inabordable porque estará basado fuertemente en este tema, haciendo mucho énfasis en sus aplicaciones. Es por esto que les pediré que presten especial atención, que le pongan muchas ganas y sobretodo que practiquen, hagan los ejercicios y me pregunten cada duda que les surja.

En mi experiencia personal, me costó mucho comprender este tema. Intentaba siempre resolver los ejercicios sin utilizar la recursividad, y no me detenía a mirar los ejemplos porque lleva largo rato comprenderlos. Sin embargo llega un momento donde esta herramienta se hace indispensable y por ende sin ella no podemos resolver lo que se nos plantea.

Ha sido un problema para mí resolver cómo enseñarles esto en un manual, cómo hacer que sea entendible, cómo lograr que se comprenda de la manera más sencilla posible, y pues, no se si lo lograré, pero pondré todo mi esfuerzo en ello.

Este tema implica cierta matemática avanzada para ser dado de forma teóricamente correcta, sin embargo intentaré omitir eso y darlo de manera intuitiva, explicando cómo funciona paso a paso, dando ejemplos en todo momento y siguiéndolos paso a paso. Espero entonces que sea leve, jeje.

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

¿Qué es la Recursión?

Dicho de manera “sencilla”, y lo digo bien entre comillas, la recursión es la capacidad que tiene una función o un procedimiento de llamarse a sí mismo dentro de su propio código. Es simplemente eso: un subprograma que se invoca a sí mismo. Si les diera un ejemplo bien general, sería algo así:
Código:

   PROCEDURE FuncionRecursivaEjemplo(parametros): Tipo;
   
   . . . (*Variables y demás*)
   BEGIN
      . . .(*Insturcciones*)
      variable:= FuncionRecursivaEjemplo(parametros);
      . . .(*Instrucciones*)
   END;

Ese es un ejemplo bien genérico. Básicamente tenemos una función llamada FuncionRecursivaEjemplo que tiene alguna lista de parámetros que no nos importan y devuelve algún dato de algún tipo que tampoco nos importa. Entrando en su código tenemos alguna declaración de tipos, constantes y demás que no nos interesan. Luego, en su bloque principal podemos tener instrucciones y luego vemos que a una variable se le asigna el resultado de volver a llamar a la misma FuncionRecursivaEjemplo con alguna lista de parámetros. Debajo de esta llamada pueden haber más instrucciones.

¿Cómo funciona esto? Si la función se llama a sí misma dentro de su código estamos volviendo a empezar, o sea, volvemos a entrar en la función y por lo tanto no se ejecutan las instrucciones que están debajo de la llamada recursiva. Como volvimos a entrar, llegará un punto en el que volveremos a llamar nuevamente a la función con lo cual volveremos a entrar. Esto continuaría infinitamente si no fuera porque la memoria del sistema no es infinita, entonces, continuará hasta que el sistema genere tantas llamadas recursivas que la memoria RAM se llenará y el programa caerá en tiempo de ejecución con un error Stack Overflow (Desbordamiento de pila).

¿Por qué se llena la memoria? ¿Qué es una pila? ¿Qué se desborda?
Todas esas preguntas serán respondidas poco a poco. Primero, debemos ver un ejemplo concreto de una función o procedimiento recursivo mal hecho para que empiecen a comprender esto desde lo básico.

Código:
PROCEDURE Proc();
BEGIN
   WriteString(“*”);
   Proc();
END Proc;


Ese es un procedimiento recursivo llamado Proc. Como ven, no tiene declaración de variables ni nada, ni tampoco recibe parámetros. Su bloque principal consta únicamente de dos instrucciones, una que imprime un asterisco en pantalla y otra que es un llamado recursivo al propio procedimiento.

Vean entonces este programa:

Código:
MODULE Ejemplo;
FROM STextIO IMPORT WriteString;

PROCEDURE Proc();
BEGIN
   WriteString(“*”);
   Proc();
END Proc;

BEGIN
   Proc();
END Ejemplo.


En ese programa tenemos declarado el procedimiento Proc, y lo único que hacemos en el bloque principal es hacer un llamado a Proc.

¿Qué resultado obtienen si ejecutan ese código? Pues verán infinitos asteriscos dibujarse en pantalla hasta que el programa se cae con el error que les comenté antes. Veamos que pasa entonces, paso a paso, al ejecutar ese código.

En nuestro bloque principal tenemos un llamado a Proc. Bien, entonces entramos en el bloque principal de nuestro procedimiento. ¿Qué tenemos? Una instrucción WriteString(“*”), entonces se imprime el asterisco. Luego tenemos un llamado recursivo a Proc, entonces volvemos a entrar en el procedimiento. ¿Qué hacemos? Imprimimos un nuevo asterisco y tenemos nuevamente un llamado a Proc. Volvemos a entrar, imprimimos otro asterisco y volvemos a entrar. Esto es un bucle infinito. No hay nada que le diga a Proc cuando debe dejar de llamarse a sí mismo, por lo tanto sigue llamándose hasta que llena el Stack de memoria (ya veremos que es eso).

Ahora veremos un ejemplo más completo, pero aún erróneo. Modificaremos un poquito el código de Proc para que muestre en pantalla cuántas veces se va llamando a sí mismo. Esto hará que comiencen a ver un poco más claramente lo que hay detrás de la recursividad.

Código:
MODULE Ejemplo2;
FROM STextIO IMPORT WriteString;
FROM SWholeIO IMPORT WriteCard;

PROCEDURE Proc(x: CARDINAL);
BEGIN
   WriteCard(x,1);
   WriteString(" ");
   Proc(x+1);
END Proc;

BEGIN
   Proc(1);
END Ejemplo2.


Analicemos bien este ejemplo. En primer lugar, ahora nuestro procedimiento Proc recibe como parámetro un CARDINAL; dicho parámetro lo llamamos x. Lo primero que hace nuestro procedimiento es imprimir el valor de x en pantalla, luego imprime un espacio en blanco para finalmente llamarse a sí mismo. El truco de la recursión está justamente en el llamado recursivo. Si se fijan bien, Proc se llama a sí mismo pero pasando como parámetro el valor de x más 1. Entonces, analicemos lo que pasa al ejecutar nuestro programa:

-----1. Entramos en el bloque principal de nuestro programa, o sea, lo que hay luego del BEGIN. Allí lo único que tenemos es un llamado a Proc pasando como parámetro el número 1.

-----2. Entramos entonces a nuestro procedimiento, por tanto x vale 1. Si miramos el cuerpo principal de Proc, tenemos una instrucción WriteCard(x,1) que lo que hace es imprimir el valor de x, en este caso, 1. Luego tenemos una instrucción WriteString(“ “) que lo único que hace es imprimir un espacio en blanco. Y luego tenemos un llamado recursivo a Proc pero pasando como parámetro el valor de x+1.

-----3. Mucha atención a este paso. El llamado a Proc fue con parámetro x+1. Entonces volvemos a entrar a Proc pero ahora x vale 2. ¿Qué? Sí, vale 2. ¿Pero por qué? Porque entramos con x+1, como x valía 1, entonces 1+1 es 2, por tanto en este caso Proc(x+1) es igual que Proc(2).

Entonces, vamos al cuerpo principal, encontramos WriteCard(x,1) con lo cual escribimos el valor de x en pantalla. Luego escribimos un espacio en blanco y tenemos un nuevo llamado a Proc con x+1. Como x vale 2, entonces este llamado equivale a Proc(3).

-----4. Volvemos a entrar a Proc, pero ahora x vale 3 porque fue con el valor con el que entramos. Entonces imprimimos un 3 en pantalla, un espacio en blanco y llamamos a Proc(x+1), como x vale 3 esto equivale a Proc(4).

-----5. Entramos ahora entonces con x valiendo 4. Imprimimos un 4, un espacio en blanco y luego llamamos a Proc(x+1), o sea, Proc(5).

-----6. Seguimos así hasta que se llena el Stack de memoria y el programa cae porque Proc no sabe cuando detenerse.


Si ustedes corren este programa en su computadora, entonces verán al final, el número de veces que se ejecutó Proc, incluyendo la llamada inicial desde el programa principal. En mi caso, veo un 15553, pero ustedes pueden ver cualquier otra cosa. Dependerá de su Stack de memoria en ese momento.

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

Siguiendo un ejemplo con el Debugger:

El depurador del XDS funciona casi exactamente igual al de Free Pascal. Para correrlo tienen dos opciones:

**Van al menú Debug → Run

**Presionan el botón Run Debugger en la barra de herramientas.

Al iniciar, el programa de depuración les mostrará una pantalla con su código fuente en distintos colores resaltando en verde fluorescente el código importante en ese momento de la ejecución. Verán una barra de color lila o rojo oscuro indicando donde está el puntero de ejecución, o sea, qué instrucción se ejecutará, tal como en Free Pascal.

En el menú Run del Debbuger tienen muchas opciones, tales como:


  • Run: Muestra la ejecución del programa en el depurador, pero a velocidad normal, o sea, no podrán ver casi nada.
  • Execution trace: Muestra la ejecución del programa en el depurador, pero a una velocidad prudente para poder ver más o menos lo que va pasando.
  • Step into: Al igual que en Free Pascal, avanza una instrucción. Si justo esta es la llamada a un subprograma, entra en él para que podamos correrlo paso a paso también.
  • Step over: Al igual que en Free Pascal, avanza una instrucción. Si justo esta es la llamada a un subprograma, lo ejecuta por completo, y continúa hacia abajo, o sea, no entra.
  • Restart: Reinicia el depurador y nuestro programa.


Todas estas opciones tienen teclas de acceso rápido, todas visibles en el menú.

Luego, en el menú Show tienen la opción Add watch para añadir una variable a visualizarla, y la opción Show watch window para ver la pantalla de las variables que añaden y quieren ver. Generalmente al añadir variables mediante Add watch, la ventana Watches se abre por sí sola.

Si ustedes no añaden variables como lo hacían en Free Pascal, el depurador les mostrará dos ventanas, una llamada Locals y otra llamada Globals, donde verán TODAS las variables locales y TODAS las variables globales respectivamente, para la porción de código que estén ejecutando. Esto significa que si están ejecutando un procedimiento verán sus variables locales allí, pero si luego entran en otro, las variables locales cambiarán automáticamente. De este modo, Add watch se utiliza muy poco.

En todo momento pueden usar puntos de quiebre (breakpoints), para que el programa se ejecute hasta donde ustedes quieren. Si ustedes colocan un breakpoint mediante el menú Breaks → Breakpoint, su código se ejecutará hasta ahí, luego se ejecutará desde ahí hasta el próximo breakpoint que hayan colocado. De este modo pueden ir probando su código por porciones. Igualmente, yo no los utilizo mucho, pero es algo que tienen ahí.

El depurador, además les abre automáticamente la consola de salida para que puedan ir viendo lo que sale en pantalla y para que, en caso de que haga falta, ingresen datos. Dentro del depurador también pueden ajustar el tamaño y la posición de las ventanas que tienen allí dentro.

De este modo, quiero que como ejercicio ejecuten el programa Ejemplo2 con el depurador, colocando como watch a x, o sea, vayan al menú Show → Add watch y escriban x. Luego ejecuten el programa con F7, o sea, con Step into y vean como se da la ejecución.

Claro está que deben hacerlo solo un poco, porque a mano no llegarán nunca al final de la ejecución.

Ahora quiero que hagan lo mismo, pero antes, vallan al menú Data → Stack. Eso les abrirá la ventana que muestra el Stack de memoria. Son símbolos raros, pero lo que quiero que vean es que cada vez que se ejecuta un llamado recursivo se agregan cosas a esa ventana, sumando y sumando, creando una lista larguísima que se va llenando. El programa cae cuando eso llega a su tope. ¿Qué es lo que se agrega allí y qué es ese Stack? Lo veremos luego.

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

Iteración en el Stack:

La iteración ustedes ya la conocen, es la manera que conocían hasta ahora para repetir bloques de código. Existen tres estructuras iterativas: FOR, WHILE y REPEAT.

La recursión es otra manera de repetir código. Como han podido ver, lo que hicimos en el ejemplo es repetir el código de Proc tantas veces como nos permite nuestro equipo. Ese programa básicamente imprimía números en pantalla, desde el 1 en adelante. Veamos su versión iterativa, o sea, usando WHILE o REPEAT:
Código:

PROCEDURE Proc(x: CARDINAL);
BEGIN
   WHILE TRUE DO
      WriteCard(x,1);
      WriteString(“ “);
      x:= x + 1;
   END;
END Proc;


Este procedimiento no debería ser problema para ustedes, salvo tal vez porque he puesto como condición del WHILE la palabra TRUE, o sea, una condición que siempre será verdadera. Eso hace que el WHILE no tenga condición de parada. En efecto, eso es lo que pasa con Proc, nunca le dimos condición de parada, tanto en su versión recursiva como en su versión iterativa.

Lo importante aquí, es que quiero que ahora corran su programa con el depurador habiendo cambiado el código interno de Proc por este que les muestro aquí, y se fijen que pasa con el Stack. Verán que no se llena, que se agregan “cosas” cuando hacemos el llamado a Proc desde el programa principal pero luego no se agrega más nada, queda igual. De este modo, el programa no se detendrá nunca, imprimirá números en pantalla hasta que lo detengamos nosotros mismos.

Esto lo único que nos dice por ahora, es que cada vez que llamamos a una función o a un procedimiento, se agrega algo en ese Stack. Sigue pendiente ver qué es esto y por qué sucede.

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

Por esta lección es suficiente. Seguiremos desarrollando este tema en la próxima.

Saludos.

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


Registrado: 05 Sep 2011
Mensajes: 196

Mensaje Publicado: Miércoles 19 Sep 2012 08:47

Título del mensaje: Re: Programando desde 0: 33- Recursión - Introducción

Responder citando

Aún no he hecho los ejercicios de la lección anterior, pero he echado una primera lectura a este tema y es recursivamente FASCINANTE!!! Ojos

Volver arriba
Ver perfil del usuario Enviar mensaje privado MSN Messenger
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,