Recursión

Contenido

Imagen: re cu rs ion 02



1. Carlos Grant

From: grant at cnea.edu.ar
Date: Tue, 19 May 1998 23:29:40 -0300

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

From: grant, grant at cnea.gov.ar
Date: Tue, 16 Feb 1999 22:01:35 -0300

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:

PARA CAMINAR
ADELANTE 1
SI COORDX > 100 PARAR
CAMINAR
FIN

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:

PARA CAMINAR
MIENTRAS [COORDX <= 100] [ADELANTE 1]
FIN

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

[ arriba ]

2. Enrique Lindenbaum

From: Flia. Lindenbaum, lindenbaum at bariloche.com.ar
Date: Sun, 6 Feb 2000 01:04:56 -0300

... 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

From: vera at rex.wamani.apc.org
Date: Tue, 8 Feb 2000 21:43:20 -0300

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.

HABIA UNA VEZ UN GATO 
CON LA CABEZA DE TRAPO
Y LOS OJOS AL REVÉS 
¿TE LO CUENTO OTRA VEZ?
HABIA UNA VEZ UN GATO...

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...

PARA LIMPIEZA_GENERAL
RECOGER TODO LO QUE HAY TIRADO
LIMPIAR COMEDOR
LIMPIAR COCINA
LIMPIAR HABITACION DE LOS CHICOS
 si los chicos están en casa durante el procedimiento
 hay que hacer una recursión aqui: volver a recoger cosas
 volver a limpiar la cocina (quiero jugo, quiero un sandwich, 
 quiero ver la tele, dale ma...)
 este paso de la recursion dura hasta que decimos !QUEDENSE AFUERA 
 hasta que mamá termine!!!
 AHI sigue el proceso...
LIMPIAR HABITACION DE LOS GRANDES
LIMPIAR PATIO
FIN

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

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!

Imagen: re cu rs ion 01

Saluti a tutti y ADELANTE 100 Vera

Prof. Vera M. Rexach Monte Grande Buenos Aires ARGENTINA

[ arriba ]

3. Carlos Grant

From: carlos grant, grant at cnea.gov.ar
Date: Sun, 6 Feb 2000 16:23:28 -0300

HOLA TODOS

Esta es una discusión muy interesante.

Enrique Lindenbaum escribió:

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.

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:

PARA LISTAR :L
  si vacía? :L parar
  esc primero :L
  LISTAR MenosPrimero :L
  FIN

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:

PARA LISTAR :L
arriba:
  si vacía? :L parar
  esc primero :L
  hacer "L MenosPrimero :L
  SALTAR arriba
  FIN

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:

PARA inicio
  ...
  ProcA
  ...
  FIN

PARA ProcA
  ...
  si :r = "otra inicio
  ...
  repite :N [etc. etc.  ... si :empezar_de_nuevo inicio]
  ...
  FIN

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:

para arbol :a
  si :a < 10 volver
  hacer "a :a / 2
  iz 30 ad :a de 30 arbol :a iz 30 at :a de 30
  de 30 ad :a iz 30 arbol :a de 30 at :a iz 30
  fin

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

[ arriba ]

4. Daniel Ajoy

From: dajoy at openworldlearning.org
Date: Mon, 7 Feb 2000 05:04:26 -0300

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.

Entonces resulta que el feature (característica ventajosa) de los logos que transforman la recursión por la cola en bifurcación automáticamente es en realidad un bug (característica mala) porque confunde a las personas.

Siguiendo ese razonamiento quizá esto se podría ir corrigiendo si, en los programas que tienen recursión infinita por la cola, luego de un tiempo apareciera:

"agotamiento de pila de recursión"

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.

En realidad se usa "recursión verdadera" como tú le llamas cuando un procedimiento se llama a si mismo desde una línea intermedia. Es decir que luego de la llamada a sí mismo hay más sentencias que deben ser ejecutadas. Eso es todo. Esas sentencias DEBEN ser ejecutadas cuando termina de correr una llamada más interna por ejemplo aquí:

mostrar palindromo "alderredor
( palindromo "alderredor )
 ( palindromo "lderredo )
  ( palindromo "derred )
   ( palindromo "erre )
    ( palindromo "rr )
     ( palindromo " )
      palindromo retorna "verdad
    palindromo retorna "verdad
   palindromo retorna "verdad
  palindromo retorna "verdad
 palindromo retorna "falso
palindromo retorna "falso
falso
para palindromo :n
 si 2 > contar :n [resp "cierto]
 resp y ((primero :n) = (ultimo :n)) (palindromo menosprimero menosultimo :n)
fin

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:

12321
 ^^^

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

12321
^   ^

son iguales. La comparación:

(primero :n) = (ultimo :n)

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

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

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.

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.

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

From: carlos grant, grant at cnea.gov.ar
Date: Mon, 7 Feb 2000 09:07:56 -0300

HOLA TODOS

DANIEL escribió

Entonces resulta que el feature (característica ventajosa) de los logos que transforman la rescursión por la cola en bifurcación automáticamente es en realidad un bug (característica mala) porque confunde a las personas.

Siguiendo ese razonamiento quizá esto se podría ir corrigiendo si, en los programas que tienen recursión infinita por la cola, luego de un tiempo apareciera:

"agotamiento de pila de recursión"

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

From: dajoy at openworldlearning.org 
Date: Mon, 7 Feb 2000 22:23:12 -0300

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.

Si existiera lo posibilidad de hacer bifurcaciones y existeria la posibilidad de hacer recursión. Y se expusiera a los alumnos ambas cosas, saltaría la duda inmediantamente: Ud. me dice que la recursión y la bifurcación son dos cosas diferentes pero yo las veo igualitas Qué es lo que las diferencia? Qué es lo que no estoy entendiendo?

Lo malo es que la técnica de bifurcar tiene muy mala fama y lo único que se escucha es "Nunca debes usar GOTOs, ni los mires, ni pienses en ellos. Cualquier uso de GOTOs lleva a crear código espaguetti". Entonces no hay chance de comparar.

La bifurcación es una técnica sencilla para hacer que la ejecución de un programa salte de una parte del código a otra. Es tan sencilla y compresible que parece ser que los alumnos que aprenden a programar entienden bifurcación cuando los profesores quieren decir recursión.

Lo que pasa es que cuando se abusa de la bifurcación los programas terminan siendo una maraña de saltos de aquí para allá y no se entienda nada. Eso se llama código espaguitti.

Para evitar que los programadores principiantes abusen de la bifurcación se inventó la programación estructurada: si...sino, mientras, repetir, hastaque, etc. Estas estructuras reeplazan al uso de la bifurcación y hacen programas más legibles.

No sé de donde salió la programación funcional pero este tipo de programación es una alternativa a la programación estructurada. Los lenguajes de programación moderna permiten hacer tanto programación estructurada como funcional. Y por eso en Logo se puede utilizar tanto el "mientras" como la recursión.

Daniel

Esto es lo que yo entiendo sobre este tema y no es de ninguna manera la verdad absoluta y santificada.

[ arriba ]

5. Daniel Ajoy

From: dajoy at openworldlearning.org 
Date: Mon, 7 Feb 2000 22:23:12 -0300

Qué lindo!: Feedback.

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

Carlos dice:

"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."

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

hacer "n 0

para recurro
 escribir :n
 si :n = 10 [parar]
 hacer "n :n + 1
 recurro
fin
recurro
0
1
2
3
4
5
6
7
8
9
10

Y esto también:

hacer "n 0

para recurro
 escribir :n
 hacer "n :n + 1
 recurro
fin
recurro
0
1
2
3
4
...

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:

hacer "n 0

para recurro
 escribir :n
 si :n = 2 [parar]
 hacer "n :n+1
 recurro
 escribir [todavia faltaba esto]
fin
recurro
0
1
2
todavia faltaba esto
todavia faltaba esto

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

[ arriba ]

6. Daniel Ajoy

From: dajoy at openworldlearning.org 
Date: Tue, 15 Feb 2000 03:33:53 -0300

Daniel escribió:

Que bueno. Me alegra mucho. Existen en realidad dos tipos de recursión pero la diferencia entre las dos para una persona que programa en Logo no es de mucha importancia.

Carlos escribió:

Al contrario, creo que tiene importancia. Yo lo veo por la cantidad de veces que me envían programas que "no funcionan" por un supuesto error de programación en el LOGO GRÁFICO (que por supuesto los debe tener) y es por los dislates que hacen muchas personas al creer que para saltar al comienzo de un programa que empezó a ejecutarse en el procedimiento "inicio" basta con volver a llamarlo desde cualquier lugar. Y lo llaman desde los lugares más insólitos. El resultado es el agotamiento de la memoria en la pila de recursión y un programa que es imposible de depurar.

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.

La diferencia es muy simple: en la recursión de la última línea, al no necesitar más guardar algo pues se va a abandonar el procedimiento que se llama a sí mismo, LOGO realiza un bifurcación a la primera línea, con lo cual el costo de memoria es cero. En estos casos se puede programar lo mismo mediante el uso de otra estructura tal como REPITE, MIENTRAS, etc. etc. y hasta con una bifurcación incondicional en alguna versión de LOGO que la tenga.

En cambio, en los programas recursivos que recorren un árbol, la recursión es inevitable.

En el ejemplo que dí en un mail anterior:

para arbol :a
  si :a < 10 volver
  hacer "a :a / 2
  iz 30 ad :a de 30 arbol :a iz 30 at :a de 30
  de 30 ad :a iz 30 arbol :a de 30 at :a iz 30
  fin

Este procedimiento es imposible o muy engorroso hacerlo usando REPITE, MIENTRAS, SI.. SINO.., o cualquier otra estructura. Lo más natural y sencillo es usar aquí recursividad.

Insisto una vez más: no está mal usar la recursión de cola o recursión infinita.

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

para recurro 
 escribir :n 
 si :n = 10 [parar] 
 hacer "n :n+1 
 recurro 
fin
recurro 
0 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 

Pero hay que tener muy en cuenta su diferencia con la recursión desde líneas intermedias de un procedimiento, pues las personas que no son expertas en programación tienden a confundir de esta manera recursión con bifurcación.

Eso es lo que confunden efectivamente: recursión con bifurcación. La diferencia entre recursión por la cola y recursión "real" no es importante a mi criterio para las personas que programan en Logo.

Cúal es la importancia, para las personas que programan en Logo, de saber de qué tipo es una recursión? Toda recursión es "recursión". Una recursión NO es una bifurcación.

Si las personas creadoras de algún Logo quieren hacer optimizaciones de memoria a esto:

para recurro1 
 escribir :n 
 si :n = 10 [parar] 
 hacer "n :n+1 
 recurro1 
fin

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:

para recurro2 
 escribir :n 
 si :n = 10 [parar] 
 hacer "n :n+1 
 recurro2 
 escribir [falta esto]
fin

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.

Este tema debe ser muy bien aclarado en los cursos de LOGO por causa de la gran confusión que puede crear en los programadores principiantes. Al menos es lo que yo he observado el recibir gran cantidad de programas en donde la recursión se emplea de una manera totalmente disparatada.

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

[ arriba ]

7. Carlos Grant

From: Carlos Grant, grant at cnea.gov.ar
Date: Fri, 21 Jul 2000 16:44:49 -0300

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

[ arriba ]

8. Daniel Ajoy

From: dajoy at openworldlearning.org 
Date: Tue, 15 Feb 2000 11:07:24 -0500

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

[ arriba ]

9. Carlos Grant

From: carlos grant, grant at cnea.gov.ar
Date: Tue, 15 Feb 2000 22:22:48 -0300

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:

para contar :n
  escribir :n
  contar :n + 1
  FIN

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

func sum :n
  si :n > 0  respuesta :n + sum :n -1
  respuesta 0
  FIN

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.

[ arriba ]

10. Preguntas, Dudas, Comentarios, Peticiones

Nombre:
Ciudad y País:
Email:
 
[ arriba ]

11. Enlaces

Página Principal

[ arriba ]

Generado con PureJoy.
Fecha: 17:48 - Sep 03, 2010