Recursión

INCLUDE:HEADER INCLUDE:TOP Contenido 1. Carlos Grant 1.1. Carlos Grant 2. Enrique Lindenbaum 2.1. Vera Rex 3. Carlos Grant 4. Daniel Ajoy 4.1. Carlos Grant 4.1.1. Daniel Ajoy 5. Daniel Ajoy 6. Daniel Ajoy 7. Carlos Grant 8. Daniel Ajoy 9. Carlos Grant 10. Preguntas, Dudas, Comentarios, Peticiones 11. Enlaces

1. Carlos Grant

IMPORTANTE:

Un vicio muy común de los LOGUEROS es abusar de la recursión. Las modernas versiones de LOGO proveen estructuras iterativas tales como MIENTRAS, HASTA, etc. que permiten resolver problemas iterativamente. MicroMundos tiene la estructura CUMPLEVECES y el Comenius LOGO tiene otras estructuras que están presentes en los lenguajes más avanzados tales como PASCAL y C++.

Aún la vieja estructura REPITE también se puede usar.

Sin embargo, muchos LOGUEROS suelen usar recursión en la forma más retorcida que uno se pueda imaginar y da como resultado programas crípticos que luego ni el mismo autor los puede comprender.

La recursión debe usarse cuando se está recorriendo un árbol pero si se está repitiendo muchas veces un mismo proceso (por ejemplo, hacer una pregunta y evaluar la respuesta, que es nuestro caso), es mucho más natural emplear una estructura iterativa tal como MIENTRAS o HASTA.

Carlos Grant

1.1. Carlos Grant

Estimados Colisteros:

Hace ya tiempo que estoy sosteniendo con muchos logeros una discusión acerca de lo que podemos llamar "abuso de la recursión".

Por ejemplo, el ejemplo de "caminar" que dio Eduardo que se puede escribir como:

Aquí se incluyó la instrucción de corte de la recursión, suponiendo que se camina hasta llegar a la coordenada 100.

Pero si empleamos iteración por medio de la estructura MIENTRAS, que existe en todas las versiones actuales de LOGO, este procedimiento se puede escribir en una forma más clara:

El funcionamiente de "MIENTRAS" no creo que sea difícil de comprender. Al menos me parece mucho más simple que el de la recursión.

Está clarísimo que para recorrer árboles lógicos la recursión es insustituible, pero en los casos de acciones repetitivas (lo que ocurre en la inmensa mayoría de los casos) la iteración es muchísimo más simple que la recursión y mucho más comprensible.

Como yo no soy docente ni tengo ninguna experiencia en la enseñanza de programación con niños o adolescentes, me gustaría saber la opinión de ustedes sobre este tema.

Desde ya estoy agradecido por sus aportes.

CARLOS GRANT

2. Enrique Lindenbaum

... Y nos estamos metiendo en terreno bravo. Carlos nos pregunta si mientras ó recursión. Ambas son duras de entender para el lego, pero prefiero la recursión. Precisamente porque es más dificil. A medida que uno avanza en el arte de la programación, la recursión es una herramienta muy potente, entonces, enseñarla desde el ejemplo más sencillo ayuda a comprenderla y pensarla. Y cuando empezamos a "ver" la recursión, estamos en un nivel avanzado de programación. Ojo, a nivel escolar esto significa 11,12,13 años, no se si las estructuras lógicas están desarrolladas antes de esa edad para tratar de entenderla. O sea que podemos usar y sacarle el jugo a buena parte del logo antes de llegar a este punto. pero si queremos avanzar en la programación, hay que meterse con la recursión.

Me estoy poniendo denso, dejemos cosa para mañana o pasado.

Para entender la recursión, primero hay que entender la recursión.

(Si falló la primera vez, intente de vuelta)

Un abrazo, :)

Enrique Lindenbaum

2.1. Vera Rex

Hola a todosssss

Para entender la recursión primero hay que entender la recursión... eso dice "el colo", Enrique, desde el bello sur de Argentina.

Bueno, cuando yo empecé a aprender con Logo, me dijeron que la recursión de cola (hacer que el programa se llame a si mismo desde la última línea) se llamaba recursion SIMPLE.

En cambio, cuando la llamada a ESE MISMO PROGRAMA se hacía en medio del procedimiento ( y esa llamada activaba una rutina o subprocedimiento que se cumplía una determinada cantidad de veces, generalmente limitada por la presencia de algún condicional) pues... entonces se la llamaba recursión AVANZADA.

Esta clase de programas son en general dificiles de comprender, pero es aún mas dificil de saber cuándo aplicar... bueno... para mi... jejeje...

Una buena explicación - o más bien una analogía poderosa - la encontré leyendo a Marvin Minsky en su libro "La sociedad de la mente" en la que el autor describe a la mente como un sistema, un conjunto organizado y descentralizado de "agentes" cada uno de los cuales cumple una pequeña función en determinado nivel. Cuando un agente termina de cumplir su parte "entrega" al nivel que sigue, y así una tarea compleja se ejecuta rápidamente y siguiendo ciertos patrones.

Para las amas de casa modernas (como yo ;))) una recursión avanzada es la que hacemos cunado nos proponemos una limpieza general de la casa...

No sé si es muy académico, pero es bastante más comprensible al sentido común que los programas de árboles, que son tan bellos cuando se ejecutan en pantalla, pero bastante "duros" para mirar el código.

Y para terminar:

AUNQUE VOS

• no uses Logo ahora
• no lo "enseñes" en tu escuela
• no te atraiga mucho este tema...

una recomendación: copiar el procedimiento para hacer árboles en cualquier Logo y verlo "en acción". Probar un poco...modificar algunas cosas...lo que sea más fácil. Eso es recursión en vivo. Si no entendés la recursión ¡qué mas da! Es tan bello ver que unas pocas líneas de código hacen florecer tu pantalla!

Saluti a tutti y ADELANTE 100 Vera

Prof. Vera M. Rexach Monte Grande Buenos Aires ARGENTINA

3. Carlos Grant

HOLA TODOS

Esta es una discusión muy interesante.

Aquí surge una controversia que yo tengo con la "cultura LOGO": la recursión de "cola" o la "falsa recursión". Esto ocurre cuando un procedimiento se llama a sí mismo desde la última línea.

Por ejemplo, para listar los elementos de una lista en LOGO se suele escribir:

pero esto es lo que yo llamo "falsa recursión" o iteración disfrazada. Es lo mismo que podría haber sido escrito en la forma:

si existiera una instrucción del tipo "SALTAR" que hace lo mismo que el GO TO, es decir, una bifurcación incondicional. Esto no es recursión, sino iteración. Es decir, la recursión de "cola" escrita más arriba, al llamarse un procedimiento a sí mismo en la última línea, es una iteración disfrazada.

Tiene como característica principal que LOGO al convertirla en iteración no gasta memoria en la pila de recursión, por lo que su costo de memoria de pila es cero. Es por esto que también la llaman "recursión infinita", lo que confunde aún más todo el tema, porque en realidad es una "bifurcación infinita".

El problema de todo esto es que produce en los docentes y alumnos que aprenden LOGO una falsa noción de lo que es recursión. Por ejemplo, algunos escriben en un programa que comienza a ejecutarse en un procedimiento "inicio" , que llama a un procedimiento ProcA y luego comienza de nuevo desde "inicio" en la forma:

Me han llegado reclamos de gente que había programado esto y me preguntaba por qué casi siempre, después de haber reiniciado el programa un cierto número de veces, les daba un mensaje del tipo "agotamiento de pila de recursión". Yo les tuve que explicar que ellos no estaban usando la recursión sino abusando de ella. Además encontrar un error en un programa como éste es una hazaña.

Lo que pasa es que en la mayoría de los casos la cultura LOGO confunde recursión con bifurcación. Piensan que llamar al procedimiento "ProcA" es lo mismo que escribir "SALTAR ProcA" o "GO TO ProcA". Y esta confusión proviene porque la "recursión de cola" en LOGO no funciona como una recursión sino como una bifurcación a la primera línea, por lo que todo el mundo termina creyendo que cualquier llamado a un procedimiento no es más que una bifurcación e éste.

La verdadera recursión no se produce cuando un procedimiento se llama a sí mismo desde su última línea, sino cuando se recorren árboles, como por ejemplo:

En este caso, la recursión es imprescindible. Esto no se puede hacer facilmente usando bifurcación ni las estructuras MIENTRAS, REPITE, etc.

En la cultura LOGO se abusa de la recursión y se la usa aún en casos en que la iteración es mucho más simple y más eficiente. Incluso se hace un "fetichismo" de la recursión, lo que comprobé el día en que un docente para evaluar un trabajo de programación de un alumno dijo: sí, es muy lindo, pero no usa recursión. Y yo le contesté que por eso merecía un premio, pues no había usado recursión donde no hacía falta usarla.

Carlos GRANT

4. Daniel Ajoy

Funciona bajo el principio de que un número es palindrómico si el número que queda sin los extremos es palindrómico Y los dígitos de los extremos son palindrómicos también. Ejemplo:

123321 es palindrómico porque esto:

es un número palindrómico, Y estos:

son iguales. La comparación:

(primero :n) = (ultimo :n)

y la operación "Y" se ejecutan después de la llamada recursiva a palindromo

Bueno si es "imprescindible" por definición no se puede hacer de otra forma y siempre hay forma de convertir una recursión en una iteración.

Creo que es debido a una tendencia a hacer programas utilizando programación funcional pura. La pureza es bella dicen algunos. Pero en la práctica implica no utilizar iteración ni tampoco utilizar "hacer". Algunos dicen que eso es complicarse la vida de gana. Pero otros dicen que allí está el reto :)

Daniel

4.1. Carlos Grant

HOLA TODOS

No creo que la recursión de cola sea un "bug", o sea un error de programación. Creo que es un recurso que puede ser utilizado con muchas ventajas, pero teniendo una clara noción sobre lo que hace. Esto debe ser muy bien aclarado en los cursos de LOGO para evitar todo tipo de confusiones.

4.1.1. Daniel Ajoy

5. Daniel Ajoy

Qué lindo!: Feedback.

Creo que Carlos anda de viaje. Así que cualquier error en esta contestación es achacable solamente a mí.

Esto es recursión por la cola (también llamada, según Carlos, falsa recursión):

Y esto también:

En ninguno de los dos casos Logo se quejará de que se le acabó el "stack" (la pila, que viene de apilar, no de batería :) porque es recursión por la cola.

Esto es recursión verdadera:

Cómo funciona:

el primer recurro escribe 0 y llama al segundo recurro. Pero no se olvida que todavía le faltan cosas por hacer (tiene que escribir lo que todavía le falta), así que lo _apila_ en la memoria: "no tengo que olvidarme de que cuando el segundo recurro termine tengo que continuar desde aquí, me falta aún escribir lo que falta". Bueno, el segundo recurro escribe 1 y llama al tercer recurro. Pero el segundo recurro tampoco se olvida que tiene cosas pendientes, así que _apila_ lo que le falta terminar. El tercer recurro escribe 2 pero ya no llama a ningún otro recurro porque tiene que parar.

El tercer recurro termina entonces. ( Aquí viene lo importante OJO ). El tercer recurro termina Y LE DEVUELVE EL CONTROL al segundo recurro. En ese instante el segundo recurro se despierta de su estado de invernación (desapila "su estado"), y continua desde donde se quedó, es decir, escribe lo que faltaba. El segundo recurro termina Y LE DEVUELVE EL CONTROL al primer recurro. En ese instante el primer recurro despierta y desapila su estado, escribe lo que falta.

La diferencia entre la recursión verdadera y la falsa es que en la falsa ya no queda nada por hacer y entonces no debería apilarse nada. Para qué tenemos que despertar a los llamadores si ya no tienen nada que hacer?

Los Logos entienden eso y no apilan nada y por eso la recursión por la cola no produce "stack overflow" pero la recursión verdadera sí, siempre y cuando se apilen tantas cosas que la memoria que se llene.

Daniel

6. Daniel Ajoy

Daniel escribió:

Carlos escribió:

En el ejemplo del parrafo anterior tu expones la confusión que tienen las personas entre recursión y bifurcación, no entre recursión por la cola y recursión "real" como tu le llamas. Estas personas, según creo, tienen una idea vaga de lo que es recursión (cualquier tipo) y creen que es lo mismo que bifurcación.

Más abajo, en el mismo mensaje que escribí esa vez, creo decir (ya lo perdí) que la diferencia entre bifurcación y recursión es muy importante y hago una explicación de la diferencia.

No es lo mismo decir recursión por la cola que recursión infinita:

Está bien. Pero eso debe tener sin cuidado a los programadores en Logo. Aquí ellos están usando recursión y los resultados que obtienen son los que obtendrían usando recursión.

Y aquí siguen usando recursión. Porque la sintaxis de la llamada interna a recurro no ha cambiado:

Que el implementador del Logo haga diferencia entre recurro1 y recurro2 para hacer una optimización de memoria no me parece que sea tan importante para el/la que escribió recurro1 y recurro2.

En mi opinión, no hay que aclarar la diferencia entre recursión por la cola y recursión "verdadera" sino que: cuando se llama a un procedimiento este procedimiento, cuando termina, regresa SIEMPRE el control al procedimiento que lo llamó y este último continúa desde donde se quedó. El que un procedimiento se llamé a sí mismo NO es excepción. Cuando termine deber regresar el control al que lo llamó y ese continuará desde donde se quedó.

Por eso las recursiónes infinitas me causan una sensación extraña porque un procedimiento llama a un clon de si mismo y ese a un clon y ese a un clon ... hasta el infinito. Pero cuando llegue al infinito Logo todavía no ha terminado su trabajo porque cuando el último (el que está al final, al final del infinito) termine, deberá OBLIGATORIAMENTE (porque esa es la regla) retornar el control al clon que lo llamó, y ese al clon que lo llamó ...

Parece metafísica, no? :)

Daniel

7. Carlos Grant

Estimados logueros:

Los que tienen la paciencia y el aguante de leer los mails míos y de Daniel en esta discusión sobre iteración y recursión podrán tener una falsa imagen como que yo tengo "puesta la camiseta" de la iteración y me opongo al uso de la recursión.

Sin embargo, en otra ocasión tuve que proponer el uso de la recursión para resolver un problema de mi trabajo contra lo que era usual en toda la comunidad de la programación científica.

Como trabajo en la Comisión Nacional de Energía Atómica en el desarrollo de software para la simulación del funcionamiento de reactores nucleares, uno de los problemas que tenemos que resolver es el del decaimiento radiactivo. Este consiste en que un elemento (o isótopo) si no es estable o reacciona con alguna partícula que esté por alrededor (normalmente un neutrón) o fisiona (se parte en dos o más pedazos), decae o se transmuta en otros elementos, lo que podrían ser dos o tres o más elementos diferentes. Luego, cada uno de éstos, al ser inestables pueden decaer en otros dos o tres más y así sucesivamente hasta llegar a elementos estables.

Por ejemplo, cuando un átomo de Uranio 235 fisiona se subdivide en sus productos de fisión (que pueden ser muchos) y éstos a su vez se van transmutando a otros elementos después de unos instantes que pueden durar desde segundos hasta miles de años. Y los nuevos elementos pueden volver a decaer en otros hasta llegar a un elemento estable.

El problema era cómo se programa esto en una computadora. Un día se lo planteé a una maestra "loguera", de esas que usaban los viejos LOGOS de la TI99, Talent, etc y me díjo lo que se cae de maduro: "¡¡¡Pero esto es recursivo!!" Y sí, tenía razón, es recursivo. Es el típico problema de recorrer un árbol.

Sin embargo, en los textos de estudio del Instituto Balseiro, donde se forman los ingenieros y físicos nucleares, el problema estaba resuelto en forma iterativa. Para eso tuvieron que introducir en el problema un montón de hipótesis simplificativas y aún a pesar de eso se llegaba a unas fórmulas larguísimas y muy complicadas que además eran bastante problemáticas para programar.

Esto se debía a que los programadores que modelan problemas científicos toda la vida usaron (y siguen usando) el lenguaje FORTRAN, creado en 1957. Y este lenguaje hasta 1995 no admitía recursividad, por lo cual no podían aprovechar esta opción.

Este problema lo programé en PL/1 alrededor de 1982, que es un lenguaje que siempre admitió recursividad, con un procedimiento muy sencillo que con unas poquísimas fórmulas resolvía exactamente el problema y lo publiqué y lo sorprendente es que resultó ser la gran novedad.

Es increíble, pero durante muchos años la recursividad era conocida por los niños de la escuela primaria a través de LOGO, pero era totalmente ignorada por los científicos, pues los lenguajes que éstos empleaban no la admitían.

Claro, como LOGO proviene de un lenguaje de la inteligencia artificial, que es el LISP, en sus primeras versiones casi no tiene estructuras iterativas, excepto el famoso "repite", usado para generar el no menos famoso cuadrado.

Es por eso que existe en los logueros una gran tendencia a abusar de la recursión y resolver los problemas que son de naturaleza iterativa con procedimientos recursivos mediante artificios retorcidos. O lo que es peor, usar la recursión como si fuese un "GO TO", una bifurcación, es decir, sin entenderla cabalmente.

Hoy día las versiones actuales de LOGO traen estructuras iterativas y es una pena que no sean aprovechadas. Con más razón cuando existe una gran cantidad de problemas que pensados iterativamente pueden ser resueltos con mucha mayor facilidad que pensados recursivamente. O al revés. Y en cada caso se debe utilizar lo que sea más adecuado y natural y no recurrir a artificios complicados para ajustar todo a un dogma.

Carlos GRANT

8. Daniel Ajoy

Lo que le interesa al usuario (programador) del Logo:

	Llamada a un procedimiento	Bifurcación ( GOTO o SALTAR, no existe en Logo )
El procedimiento llamado es diferente al que llama	Cuando el procedimiento llamado termina, automáticamente retorna el control al procedimiento que llama.	Si un procedimiento tiene una bifurcación y esta bifurca a otro procedimiento. Cuando termine este último procedimiento terminará el programa. (A menos que haya otra bifurcación que haga que el programa continúe en otro sitio).
El procedimiento llamado es el mismo procedimiento que el que llama	Lo mismo que en el caso de arriba. Se llama RECURSION.	Igual que en el caso de arriba solamente que la bifurcación bifurca hacia el inicio del mismo procedimiento. Ni en este ni en el caso de arriba existen regresos automáticos al procedimiento que tiene la bifurcación

Lo que le interesa al hacedor (implementador) del Logo:

	Recursión "línea interior"	Recursión por la cola
Finita (tiene condicional)	Es necesario apilar "el estado" del procedimiento que llama para poder retornar a él cuando el procedimiento llamado termine. Si el condicional se cumple en "pocos" niveles de recursión, entonces la memoria no se llena y todo funciona bien.	No es necesario apilar "el estado" del procedimiento que llama porque ya no es necesario retornarle el control porque ya no tiene nada que hacer.
Infinita	En algún momento la memoria se llena porque se siguen apilando estados hasta el infinito. La memoria es una dispositivo físico finito. Hay un error seguramente en este tipo de programa porque nunca se podrá completar lo que está después de la llamada a la recursión.	Lo mismo que en el caso de arriba. Si el implementador decide no apilar "el estado" y utiliza el método de la bifurcación para simular la recursión por la cola entonces la memoria no se llenará y este programa podría seguir funcionando días y días, semanas y semanas.

Daniel

9. Carlos Grant

Me parecieron excelentes los cuadros que mostró Daniel para clasificar los diferentes tipos de llamados a procedimiento y de recursión.

Yo solamente le haría dos modificaciones:

Donde dice "Lo que le interesa al programador en Logo" yo pondría "Lo que le interesa al principiante en LOGO". Por ejemplo, en la escuela elemental no tendría sentido ninguno hablar de "pilas de recursión" y otras complicaciones.

En segundo lugar, donde dice "Lo que le interesa al hacedor del Logo" yo escribiría "Lo que debe aprender el programador LOGO avanzado". Por ejemplo, si enseñamos a adolescentes de la escuela secundaria o en los cursos más avanzados para docentes. Pues creo que quien programa LOGO y usa la recursión (en última línea o desde línea intermedia) debe saber por qué LOGO funciona como funciona. Por ejemplo, debe entender por qué el procedimiento:

no para nunca y por qué la función que calcula la suma de los primeros :n números:

para un valor de :n suficientemente grande agota la memoria de pila.

Es por eso que pienso que un programador LOGO experimentado, sin necesidad de ser un especialista en computación, debe conocer bien cómo funcionan los llamados de LOGO.

El cuadro que hizo Daniel, que como dije antes, reproduce muy bien los diferentes tipos de llamados que se pueden hacer en LOGO.

10. Preguntas, Dudas, Comentarios, Peticiones

11. Enlaces

---