Recursividad en SuperBASIC

La recursividad es uno de esos temas que la mayoría de la gente con poca experiencia en programación seguramente ha oído hablar, pero pocos lo comprenden verdaderamente. Si pregunta a esa gente que ha oído hablar de la recursividad probablemente le conteste que la recursividad es algo así como “una rutina que se llama a si misma”.

Esa es una descripción razonable, aunque es algo más que eso. Si una rutina se llamara a si misma continuamente (como en el siguiente ejemplo), ésta se estaría ejecutando de forma indefinida, o al menos mientras el ordenador no agote su memoria.


1000 DEFine PROCedure MENU
1010 MENU
1020 END DEFine MENU

Además de ser una rutina, que se llama a sí misma (o se describe en el términos de sí misma), una rutina recursiva debe tener un mecanismo para garantizar las circunstancias en las se debe llamar a sí misma y cuando se debe proceder a una salida de dicha rutina o un retorno del mencionado procedimiento (o función). Como la recursividad es un tema difícil de explicar clara y brevemente en palabras sencillas, voy a presentar unas pocas rutinas de ejemplo para demostrar los usos de la recursividad en la programación en SuperBASIC.

La mayoría de los programadores que comprenden y utilizan la recursividad son capaces de detectar las tareas que requieren el uso de la recursividad, casi por instinto, pero pocos son capaces de explicar exactamente cómo llegaron a esa decisión. Sin embargo, una vez dominada la recursividad, ésta puede ser una poderosa y eficiente herramienta de programación.

La recursividad puede ser pensada como un proceso en el que una tarea puede ser desglosada en partes más manejables y pequeñas de una forma ordenada. Por lo tanto, la solución a esa tarea o problema se describe en términos de soluciones a problemas similares más pequeños. En este punto, los cerebros de muchas personas tienden a fundirse tratando de seguir las explicaciones, por lo que vamos a considerar un ejemplo muy simple para tratar de ilustrar lo que esto significa.

Supongamos que usted tiene un ejército. Su oponente tiene también un ejército con el mismo número de soldados que usted, por lo que seguramente no le guste la idea de entrar en una batalla donde existe un alto riesgo de que muchos de sus mejores soldados puedan ser asesinados o heridos. Así que decide optar por la estrategia de dividir a su enemigo en grupos más pequeños para simplificar el ataque. Esta estrategia podría ser denominada “divide y vencerás” – la reducción de un problema por medio de la división en varias secciones más pequeñas hasta que se haya terminado.

define procedure Conquista (grupos)
Si todos divididos entonces retornar
Dividir en otra sección (grupos - 1)
Conquistar ese grupo
end define

Tomemos ahora un ejemplo simple de la impresión de una serie de números del 1 al valor ‘n’ (cualquier número entero). Normalmente, enfocaremos el problema simplemente llamado a un procedimiento o instrucción de IMPRIMIR dentro de un bucle FOR. Sin embargo, podríamos escribir lo mismo mediante una rutina recursiva. Lo que estamos tratando de hacer es muy simple para intentar concentrarnos en la teoría y no en el problema en sí mismo. Empezaremos por desglosar el proceso en componentes más simples. Tenemos que imprimir los números, cada uno de los cuales es más grande que el tiene ante sí.

define procedure imprimir_numero (valor)
  Si hemos alcanzado el límite, entonces salir 
       de este prodecimiento
  Imprimir el siguiente número con imprimir_numero
       (valor - 1)
  Imprimir el número en la pantalla
end define

Esto es un pseudocódigo. Ahora vamos a escribir el código en un correcto SuperBASIC.

10 CLS : Print_Number_Up_To 10
20 :
100 DEFine PROCedure Print_Number_Up_To (value)
110   IF value = 0 THEN RETurn
120   Print_Number_Up_To value-1
130   PRINT value
140 END DEFine Print_Number_Up_To

La línea 110 comprueba si se debe ejecutar una vez más el bucle o si se deja de ejecutar la llamada. La línea 120 llama al mismo procedimiento 10 veces, y en cada llamada se decrece el valor pasado al procedimiento en 1 (al igual que un bucle al contar). Esto se va ejecutando hasta que el valor sea igual a 0 (10 veces). En definitiva se está llamado al mismo procedimiento para imprimir pero con 10 parámetros diferentes, cada llamada tiene un parámetro que es diferente a la llamada anterior, en este caso es el valor de la llamada anterior menos 1. Una vez que los 10 valores se calculan, hay 10 procedimientos, cada uno listo para imprimir su propio valor. Después de la décima definición, cuando el valor del parámetro “valor” se ha convertido en 0, los retornos comienzan a entrar en vigor de tal forma que hay 10 vueltas atrás. Recuerde que cada retorno vuelve a la llamada más reciente al procedimiento definido, de modo que la impresión se sucede en el orden inverso a aquel en el que los números se han definido.

La línea 10 hace una primera llamada al procedimiento con el valor más alto (en este caso 10). En esta primera llamada, el valor es 10, por lo que el retorno no es ejecutado. El programa a continuación pasa a la línea que contiene la llamada a imprimir un número pero especificando un nuevo valor. El próximo número en dicha llamada es el 9, con lo que el procedimiento se llama de nuevo con “valor-1”, o 10-1 en este caso. Esta llamada aún no retorna ya que el valor que se le pasa a la rutina sigue sin ser 0, con lo que se invocará de nuevo a si mima con el valor 9-1 u 8. Este se ejecuta una y otra vez hasta que se alcanza el valor 0, entonces los beneficios de la rutina recursiva empieza a entrar en acción. Cuando se alcanza el 0, la llamada que retoma su ejecución era cuando el parámetro pasado tenía el valor 1, por lo que éste se imprime en primer lugar. Luego retornará cuando el valor contenía 2, y así sucesivamente hasta retornar a la primera llamada donde el valor tenía 10. Espero que todo esto tenga sentido para usted. En caso de que no, aquí va una traza de la ejecución del programa.

10 llamada a Print_Number_Up_To con “value” = 10
100 definición del procedimiento, se le da el valor 10
     a la variable llamada "value"
110 se evalúa la expresión si "value" ha alcanzado
    el valor de 0
120 el valor 0 no se ha alcanzado, entonces llamamos al
    procedimiento otra vez con el valor de 10-1, (o 9)
100 regresa a la definición del procedimiento. 
    Esta vez, value=9
110 comprueba si se ha alcanzado 0, en este caso aun no.
120 se invoca de nuevo al procedimiento con 
    value-1 (9-1, u 8)
100 ... y así sucesivamente hasta que el value=0
110 se llega en este momento a value=0, así que se retorna 
    desde este procedimiento a la llamada anterior donde
    el valor previo de value era 1 (recuerde que nosotros 
    llamamos la última vez en la línea 120 convalue=1)
130 ahora se imprime el valor (1)
140 end define - fin de llamada al procedimiento, así 
    que se retorna a la llamada anterior, esta llamada fue
    ejecutada cuando value contenía el valor de 2. 
    Retornando a la siguiente sentencia después de 
    la línea 120 que contenía la llamada.
130 se imprime el valor actual (2) y así sucesivamente
    hasta que se imprimen los 10 valores.

Por supuesto, enfocar este problema de imprimir números de esta manera es como utilizar un martillo para cascar una nuez. Pero me parece que ayudan a explicar la técnica porque se trata de un ejemplo corto y bastante fácil de seguir paso a paso. Escribir cada paso sobre el papel le ayudará a entenderlo.

La recursividad a menudo se utiliza cuando se necesita una rutina similar para una serie de operaciones o donde los cálculos que se exijan sólo contienen una ligera diferencia en cada llamada a la rutina, pero donde la rutina sea suficientemente capaz de hacer frente a estas variaciones y las condiciones finales son suficientemente bien conocidas por ser claramente definibles. Esto es muy importante en la recursividad, la prueba a realizar cuando la rutina tiene que dejar de llamarse a si misma es vital para garantizar el correcto funcionamiento y el éxito en la finalización correcta. El siguiente ejemplo no es un programa real (¡no intente ejecutarlo como un programa BASIC!), es un “recorte” de código que le ayudará a mostrar el algoritmo de una forma simplificada de cómo funciona de forma general una rutina recursiva.

DEFine PROCedure Rutina_Recursiva (parámetro)
  LOCal lista de valores locales
  ... aquí se coloca el código que se precise
  IF fin condición THEN RETurn
  Rutina_Recursiva con parámetros variable
  Acciones que se ejecutan mientras
     se desenreda la llamada recursiva
END DEFine

La rutina establece el valor de sus propias variables cada vez que se ejecuta la llamada, además comprueba si el final de condición se cumple o no, entonces se llama a sí misma de nuevo con datos ligeramente diferentes, según sea necesario. Una cosa que podría ser no obvio es la necesidad de variables locales en el procedimiento. Si necesita crear variables temporales para calcular o apoyar a los valores que difieren en cada llamada al procedimiento, es necesario que las diferentes variables en cada llamada no destruyan los valores con que hemos trabajado, esto en muchas ocasiones es difícil de establecer.

En esta etapa, puede que no sea obvio el por qué alguien necesite o quiera usar la recursividad. La primera vez que me enfrenté a la recursividad hace algunos años, me pareció una especie de técnica repetitiva inventada por alguien muy inteligente que quería impresionar a los demás con una especie de código mágico que nadie pudiera entender. Siempre parece como si hubiera una forma más simple de hacer las cosas sin un código tan enrevesado. De alguna manera esto es cierto, por lo general hay una forma no recursiva de resolver un problema implementado como una llamada recursiva, pero por lo general suele ser más largo, menos elegante y menos eficiente (por no hablar de más lento). El arte reside en ser capaz de detectar los casos en que la recursividad es un beneficio para el programador. En cierta medida, este viene con experiencia y con conocimiento de un “estándar” en aplicaciones y rutinas donde se utiliza la recursividad. En términos de los procesos del pensamiento, usted tiene que meditar repetidamente patrones en los que se debería aplicar, o cuestionarse si una tarea se puede dividir y hacer más eficiente en secciones (de tipo “divide y vencerás”). Recuerdo que en una lectura de un libro de texto, hace algún tiempo, se mencionaba que la recursividad es un acto de fe, ya que es muy difícil seguir exactamente lo que uno hace en una rutina recursiva, es difícil estar seguro de que la rutina se llevará a cabo exactamente como usted espera o como piensa que se llevará a cabo. Seguramente cuando usted escriba la rutina al final se sorprenderá a si mismo de lo que la rutina está haciendo realmente.

A continuación le presentaré algunos ejemplos reales de rutinas recursivas, algunas usarán funciones y otros procedimientos. Espero que al menos algunos de estos ejemplos le ayude a ver cómo funciona la recursividad, y el motivo por el cual la recursividad puede ser una técnica de programación muy útil.

– Factoriales. Esta rutina matemática es uno de los ejemplos clásicos de la recursividad como técnica de programación. Se trata de calcular el total de una serie de productos de números, desde 1 hasta n. n! que es pronunciado como “n factorial”, consiste en el producto de todos los números enteros desde 1 hasta n.

n! = n * (n-1) * (n-2) … * 2 * 1

– Exploración de un sub-directorio. La rutina permite explorar todos lo ficheros que cuelgan de todos los sub-directorios de un disco duro (o disquete de alta capacidad). Sólo funciona en sistemas con «nivel 2» de directorios (creados con el comando MAKE_DIR básico, por ejemplo).

– Una rutina de ordenación de cadenas muy rápida, llamada “Quicksort”, donde los datos se van dividiendo en grupos más pequeños, cada uno de los cuales se van ordenando y dividiendo hasta quedar la lista totalmente ordenada. El algoritmo consiste en una rutina que se llama a si misma para ir ordenando los pequeños grupos que se van creando.

– Una rutina de relleno, donde polígonos irregulares se pueden rellenar con un determinado color. Esta rutina no es tan rápida como otras que se puedan encontrar en programas comerciales, pero funcionan correctamente. Desafortunadamente se requiere un toolkit para el uso de una instrucción que nos da el color de un pixel de la pantalla. Yo he usado mi propia extensión, PIXEL% x,y (donde x e y son las coordenadas de un punto en una pantalla estándar del QL, 512×256) pero se puede utilizar rutinas equivalentes como las de Simon N. Goodwin, las cuales se pueden llamar cambiando la instrucción y empleando los parámetros adecuados. De hecho, hay dos rutinas, una muy simple, que ilustra el principio básico (que funciona, pero no es muy eficiente), y la segunda, que incluye un elemento de buffering (o apilado) para reducir el coste general y llamar a la rutina de trabajo más rápidamente que el primer ejemplo.

– El rompecabezas llamado Torres de Hanoi. Consiste en tres varillas verticales y un número indeterminado de discos que determinarán la complejidad de la solución. No hay dos discos iguales, están colocados de mayor a menor en la primera varilla ascendentemente, y no se puede colocar ningún disco mayor sobre uno menor a él en ningún momento. El juego consiste en pasar todos los discos a la tercera varilla colocados de mayor a menor ascendentemente. Las reglas son: 1) Sólo se puede mover un disco cada vez, 2) un disco de mayor tamaño no puede descansar sobre uno más pequeño que él mismo y 3) sólo puedes desplazar el disco que se encuentre arriba en cada varilla. No es un problema muy complejo de resolver, pero muestra cómo utilizar las técnicas de recursividad para resolver el rompecabezas de una manera elegante.

1. Factoriales

Esta rutina nos permite calcular el producto de una serie de números hasta llegar a un valor dado. El término “n!” (pronunciado n factorial) se utiliza para representan este producto.

n! = n * (n-1) * (n-2) … hasta … * 2 * 1

Así por ejemplo 5! es 5*4*3*2*1, que resulta 120. Esto se puede codificar con un bucle FOR de la siguiente manera:

INPUT 'Factorial de > ';n
LET factorial = 1
FOR number = n TO 1 STEP -1
  LET factorial = factorial*number
END FOR number

Esto es perfectamente válido, pero vamos a hacer lo mismo empleando una función recursiva. El cálculo se puede realizar siguiendo las mismas etapas tal cual está escrito en la fórmula anterior, la multiplicación de un número por un número menos de la secuencia hasta llagar a 1. Por lo tanto, la secuencia incluye (i) el cálculo del número próximo, (ii) la actualización del valor total multiplicando el total por el próximo valor hasta que lleguemos hasta el último valor que es 1.

100 INPUT 'Factorial de > ';n : PRINT Factorial(n)
110 DEFine FuNction Factorial (num)
120   IF num = 1 THEN RETurn 1
130   RETurn num * Factorial (num - 1)
140 END DEFine

Esta rutina en realidad es algo más extensa que la primera, aunque se debe en parte a la definición de la función. Esta función devuelve el primer número multiplicado con la llamada a si misma con el siguiente valor descendente como parámetro. Cuando se llega a 1 tenemos simplemente que devolver ese valor 1 (línea 120) en lugar del cálculo de la multiplicación con el siguiente número de la serie (línea 130).

2. Lectura de subdirectorios

Esta rutina sólo tiene sentido para aquellos que tengan instalados en sus QL las facilidades de manejo de subdirectorio. Esto incluye la Gold Card, Super Gold Card, QXL, los emuladores de Atari ST-QL, también son validos aquellos sistemas con Trump Cards o SuperQBoards con una actualización nivel-2 de la ROM (actualización de Jurgen Falkenburg o Jochen Merz).

Al hacer un DIR de un disquete o disco duro que contiene directorios se obtienen los archivos del directorio actual y los nombres de los posibles subdirectorios, los cuales se muestran precedidos del símbolo ‘->’. Para obtener una lista de los archivos de esos subdirectorios se tiene que hacer otro DIR de ellos. Si esa lista contiene a su vez otros subdirectorios se deben ejecutar de forma sucesiva los comandos DIR sobre ellos para obtener la lista completa de todos los ficheros y subdirectorios del disco. Nos será útil plantear, para evitar esto, un procedimiento o rutina para explorar todos los archivos de todos los directorios a partir de un directorio concreto especificado. Así cuando empezamos a rastrear siguiendo adelante debemos explorar todos los subdirectorios, pero una vez agotado un camino debemos iniciar otros caminos si los hubiera hasta completar toda la exploración. De esta forma lograríamos enumerar todos los archivos y subdirectorios.

Aquí hay un resumen de cómo vamos a construir la rutina:

procedure extender_dir (unidad,directorio)
  Variables locales
  Abrir directorio
  Si fallo, retornar
  Leer todo los nombres en directorio
    ¿se ha terminado? si es así, cerrar directorio y salir del bucle
    obtener seiguiente fichero
    ¿es un nombre de directorio?
      si, hacer extender_dir en ese direcotorio llamada recusriva 
      no, imprimir ahora el fichero
    fin si
  final del bucle de lectura de nombres
fin de procedure

y así es como he decidido escribir la rutina en SuperBASIC:


100 REMark extended dir of all sub-directories
110 Extended_DIR 'win1_',''
120 :
130 DEFine PROCedure Extended_DIR (drive$,directory$)
140   LOCal loop,ch,d$,fp,n$
150   ch = FOP_DIR (drive$&directory$) : REMark open channel to directory
160   IF ch  0 THEN 
220       REMark a directory length of 0 may be a deleted file
230       BGET #ch: REMark file type byte
240       IF CODE(INKEY$(#ch)) = 255 THEN 
250         REMark this name is a subdirectory, so we need to DIR this
260         REMark if you want directory names printed, add this
270         REMark PRINT d$;' ->'
280         Extended_DIR drive$,d$
290       ELSE 
300         PRINT d$
310       END IF 
320     END IF 
330     fp = fp + 64
340   END REPeat loop
350 END DEFine Extended_DIR

Tenga en cuenta que la rutina, tal como está, no imprime los nombres de directorios sino sólo los nombres de archivo. Para imprimir los nombres de directorios, al igual que un comando DIR, debe eliminar la declaración REMark de la línea 270. Recuerde que la llamada a la rutina debe hacerse con dos parámetros, el primer parámetro con la unidad y el segundo con el nombre del directorio. Éstos se usan por separado dentro del cuerpo de la rutina.

3. Rutina de ordenación Quicksort

La rutina “quicksort” es una de las rutinas de ordenación más rápidas que pueden ser programadas en SuperBASIC. He encontrado dos variantes. La primera variante es más fácil de usar, pero no es tan rápida como la segunda variante, que tiene ciertos requisitos especiales que la hacen un poco menos conveniente en cuanto a su uso.

Quicksort hace su trabajo barajando punteros a las secciones de datos que van a ser ordenados y ordenando esas en secciones más pequeñas. Esto reduce el número total de pasadas a través de los datos que ralentiza otras rutinas de ordenación tales como el método “Burbuja” (Bubble Sort). Ya hemos utilizado la frase “divide y vencerás” para describir cómo trabajan algunas rutinas recursivas, y esto es precisamente lo que hace esta rutina de ordenación.

Esta rutina no es un ejemplo de rutina recursiva muy fácil de seguir – si usted desea seguir paso a paso el funcionamiento del programa, trate de asignar un pequeño conjunto de datos que se vayan a ordenar y trate de hacer un seguimiento, en cada parte del programa, de cómo se van clasificando dichos datos hasta conseguir el objetivo de ordenar la lista completa.

Este procedimiento en SuperBASIC está diseñado para ordenar cadenas; para ordenar arrays de números simplemente cambie las cadenas en la rutina (el nombre termina con $) por variables numéricas (enteros, finalizando con %, o variables de coma flotante). El segundo parámetro es el índice inferior del array que va a ser ordenado, generalmente 0, y el tercer parámetro es el índice más alto de dicho array (NO el total de número de items) generalmente el número total de elementos-1, siempre y cuando el primer subíndice sea 0.

100 Q_Sort array_name$,0,entries%-1
110 :
120 DEFine PROCedure Q_Sort (array$,bottom,top)
130   LOCal sort_loop,low,high,ptr
140   low  = bottom
150   high = top
160   ptr  = bottom
170   REPeat sort_loop
180     IF low >= high THEN EXIT sort_loop
190     IF array$(low) > array$(high) THEN
200       REMark need to swap these strings
210       temp$        = array$(low)
220       array$(low)  = array$(high)
230       array$(high) = temp$
240       REMark how do we shuffle pointers to sections
250       IF ptr = low THEN
260         low = low + 1
270         ptr = high
280       ELSE
290         high = high - 1
300         ptr  = low
310       END IF
320     ELSE
330       IF ptr = low THEN high = high - 1 : ELSE low = low + 1
340     END IF
350   END REPeat sort_loop
360   IF ABS(top - bottom) THEN RETurn : REMark can't sort 1 item!
370   Q_Sort array$,bottom,ptr - 1
380   Q_Sort array$,ptr + 1,top
390 END DEFine Q_Sort

4. Relleno de gráficos

Una rutina de relleno de gráficos consiste en llenar un área de la pantalla (regular o irregular) con un determinado color. Sea cual sea el color de relleno, la rutina debe asegurarse de no pintar zonas fuera del contorno delimitado por el área (polígono regular o irregular). La rutina de relleno comienza a partir de un punto situado dentro del área que se quiere rellenar, a partir de ahí, la rutina va poco a poco rellenando del color elegido el área demarcada. Imagine el boceto de una casa con ventanas, puertas y el techo ya diseñado. A partir de algún punto en la pared, se cubre toda la superficie de pared de toda la casa de un determinado color pasando alrededor de las ventas y puertas sin salirse fuera.

El principio básico es que, cualquiera que sea la línea a partir de la cual vamos a empezar el llenado, buscaremos a la izquierda para ver si podemos llenar, luego buscaremos la derecha para comprobar lo mismo, a continuación miramos encima y a continuación debajo para ver si podemos avanzar en esas direcciones. Si podemos hacerlo llenaremos con nuestro color elegido y a continuación seguiremos haciendo lo mismo hasta que no podamos ir más lejos. Debemos volver sobre nuestros pasos al punto que partimos en caso de que no podamos avanzar por una determinada dirección. Con un polígono irregular, lo que suele ocurrir es que se llena en la medida en que se pueda avanzar y, a continuación, empezar desde el punto de comienzo para encontrar otra dirección a partir de la cual se pueda continuar con el trabajo, y así sucesivamente. A este tipo de relleno a menudo se denomina por inundación (flood) porque emula a cómo el agua va inundando un lugar, llenando poco a poco bit a bit.

Esta rutina difiere con respecto al comando FILL del QL en el sentido que puede hacer frente a las llamadas formas re-entrante (formas irregulares que se pueden doblar de nuevo en si mismas). El comando FILL del QL funciona de una manera diferente a este tipo de relleno, y eso significa que (por lo general) es más rápido que la rutina de llenado por inundación, pero la rutina por inundación puede hacer frente a una variedad más amplia de formas y polígonos que se vaya a rellenar, por lo tanto, es capaz de llenar formas irregulares bastante complejas, mientras que para hacer lo mismo es posible que necesite más de un comando FILL del QL para rellenar una figura compleja correctamente. La otra gran diferencia es que la rutina por inundación trabaja correctamente sólo después de que el perímetro haya sido dibujado completamente, mientras que el comando FILL almacena los puntos y líneas a rellenar como un esquema del perímetro a dibujar, normalmente rellenando la figura cuando el perímetro esté cerrado. De cara al usuario hay poca diferencia, el resultado final es normalmente similar, pero para el programador hay una gran diferencia en cuanto a la codificación de las dos rutinas.

Para hacer que la rutina por inundación funcione, nosotros necesitamos una rutina que examine el color de un determinado pixel en la pantalla. Muchos toolkits de extensión al BASIC suministran utilidades de este tipo (por ejemplo la función PIXEL del DIY Toolkit). En esta rutina yo he usado una extensión llamada PIXEL% que requiere los siguientes parámetros (adapte esta rutina a las extensiones que usted usa). Desafortunadamente, el SuperBASIC estándar del QL carece de una función de este tipo.

x = coordenada x a través de la pantalla
y = coordenada y hacia abajo en la pantalla

Ambos, ‘x’ e ‘y’ asumen que estamos en una ventana que cubre el total de la pantalla, por ejemplo 0,0 es la esquina superior izquierda de la pantalla.

El esquema de la rutina no es demasiado difícil de comprender, pero la forma final de las rutinas es horrible para tratar de entenderlas, especialmente en lo más avanzado de las dos rutinas, que incluye un sistema de buffering para reducir el número masivo de llamadas recursivas realizada por el sistema, asi como una ayuda para acelerar la segunda rutina en comparación con la primera.

procedimiento relleno_desde punto comienzo x,y 
  si punto no rellenable entonces retornar
  rellenar a la izquierda de este punto 
  rellenar a la derecha de este punto 
  desde izquierda a derecha
    relleno_desde punto encima esta linea 
    relleno_desde punto debajo esta linea 
  fin escaneo izquierda a derecha 
fin definición procedimiento

Esto puede ser escrito de la siguiente forma, usando la mencionada extensión PIXEL%(x,y). Las primeras 3 líneas dibujan una caja dentro de otra con una brecha entre ellas, que va a ser rellenada por la rutina. La segunda línea en el procedimiento Fill_Outline (IF y255) protege el programa cuando el color de relleno intenta ir fuera de la parte superior o inferior de la pantalla. La rutina es llamada pasándole 4 parámetros al procedimiento Fill_Outline:

x = coordenada x a partir de la que se comienza el relleno (0 a 511)
y = coordenada y a partir de la que se comienza el relleno (0 a 255)
direction = dirección en que la rutina rellena, -1 = arriba, +1 = abajo
colour = número del color de la tinta usado en el relleno
100 WINDOW 512,256,0,0 : CLS : INK 7
110 BLOCK 100,100,50,50,7 : BLOCK 96,98,52,51,0
120 BLOCK 60,80,70,60,7   : BLOCK 56,78,72,61,0
130 Fill_Outline 100,55,-1,7 : REMark -1 = upward, +1 = downward
140 STOP
150 :
160 DEFine PROCedure Fill_Outline (x,y,direction,colour)
170   LOCal loop,a,lp%,rp%
180   IF y  255 THEN RETurn
190   IF PIXEL%(x,y) = colour THEN RETurn
200   lp% = x
210   REPeat loop
220     IF lp% = 0 THEN EXIT loop
230     IF PIXEL%(lp%-1,y) = colour : EXIT loop
240     lp% = lp% - 1
250   END REPeat loop
260   rp% = x
270   REPeat loop
280     IF rp% = 511 THEN EXIT loop
290     IF PIXEL%(rp%+1,y) = colour : EXIT loop
300     rp% = rp% + 1
310   END REPeat loop
320   BLOCK rp%-lp%+1,1,lp%,y,colour
330   FOR a = lp% TO rp%
340     Fill_Outline a,y+direction,direction,colour
350     Fill_Outline a,y-direction,-direction,colour
360   END FOR a
370 END DEFine Fill_Outline

El problema con esta rutina es que se llega a un callejón sin salida y, a continuación, ha de volver sus pasos hacia atrás para llenar en una dirección opuesta, esto consume mucho tiempo para algunas figuras. Podemos mejorar esto añadiendo un buffer que filtra algunos puntos en la dirección opuesta que no pueden ser rellenados, lo que a su vez significa que no tiene que volver sobre una gran cantidad de píxeles que ya se han llenado. Aún así sigue existiendo un retraso después del llenado en el último punto, pero se puede ahorrar tiempo utilizando una pila o un buffer similar a este. En el relleno de puntos en la dirección opuesta se actualizan a medida que la rutina va en una dirección, por lo que la pila (actualmente un array de enteros) crece para recordar las coordenadas rellenables fuera del punto de relleno original, entonces una vez que la rutina para en esa dirección, empieza a leer coordenadas de píxel de la pila para recordar donde volver. A continuación, trata de avanzar en la dirección opuesta, pero en caso de encontrar otra vez puntos fuera de la dirección de relleno que pueda comprobar más tarde, también los añade a la pila. Y así continúa el proceso hasta que haya terminado todos los puntos.

100 WINDOW 512,256,0,0 : CLS : INK 7
110 BLOCK 100,100,50,50,7 : BLOCK 96,98,52,51,0
120 BLOCK 60,80,70,60,7   : BLOCK 56,78,72,61,0
130 Fill_From 100,55,-1,7 : REMark -1 = upward, +1 = downward
140 STOP
150 :
160 DEFine PROCedure Fill_From (fx,fy,direc,col)
170   LOCal xst%(512),yst%(512),stack%
180   REMark this routine requires a 'stack'
190   DIM xst%(512),yst%(512)
200   stack% = 0 : REMark nothing on stack at first, of course!
210   Fill_Outline fx,fy,direc,col
220 END DEFine Fill_From
230 :
240 DEFine PROCedure Fill_Outline (x,y,direction,colour)
250   LOCal loop,a,lp%,rp%
260   IF y  255 THEN RETurn
270   IF PIXEL%(x,y) = colour THEN RETurn
280   lp% = x
290   REPeat loop
300     IF lp% = 0 THEN EXIT loop
310     IF PIXEL%(lp%,y-direction) > colour THEN xst%(stack%) = lp% :
             yst%(stack%) = y-direction : stack% = stack%+1
320     IF PIXEL%(lp%-1,y) = colour : EXIT loop
330     lp% = lp% - 1
340   END REPeat loop
350   rp% = x
360   REPeat loop
370     IF rp% = 511 THEN EXIT loop
380     IF PIXEL%(rp%,y-direction) > colour THEN xst%(stack%) = rp% :
             yst%(stack%) = y-direction : stack% = stack%+1
390     IF PIXEL%(rp%+1,y) = colour : EXIT loop
400     rp% = rp% + 1
410   END REPeat loop
420   BLOCK rp%-lp%+1,1,lp%,y,colour
430   FOR a = lp% TO rp%
440     Fill_Outline a,y+direction,direction,colour
450   END FOR a
460   REPeat loop
470     IF stack% = 0 : EXIT loop
480     stack% = stack% - 1
490     Fill_Outline xst%(stack%),yst%(stack%),-direction,colour
500   END REPeat loop
510 END DEFine Fill_Outline

La rutina tiene el inconveniente de que en figuras muy complejas puede provocar el agotamiento del espacio de la pila. En la gran mayoría de los casos, una pila de 512 espacios será suficiente. Estas rutinas tienen como ventaja que muestran en la pantalla la mayor parte de lo que está sucediendo, así que usted puede hacerse una idea de cómo “piensa” la rutina. Después de un tiempo, incluso con figuras complejas, ¡puede predecirse cómo va a ser rellenada la figura!

5. El puzzle de las Torres de Hanoi

El puzzle de las Torres de Hanoi consta de tres varillas y varios anillos de diferente diámetro. Lo que usted tiene que hacer es mover todos los anillos de la primera varilla a la segunda siguiendo las normas siguientes. Sólo puede mover un anillo a la vez. Ningún anillo puede colocarse en una varilla donde un anillo más pequeño quede debajo de uno mayor (es decir, los anillos grandes no pueden colocarse encima de uno menor). Por lo tanto, debemos utilizar la tercera varilla como almacén temporal. Sólo se puede desplazar el anillo que se encuentre en la parte superior de la varilla. De esta manera podemos ir desplazando los anillos de la primera varilla a la segunda de tal manera que al final del rompecabezas la segunda varilla contenga todo los anillos en el mismo orden que se encontraban en la primera varilla. Se puede dar una solución a este problema simplemente usando una rutina recursiva para mover progresivamente los anillos de una varilla a otra. Puede, si lo desea, agregar rutinas para animar la solución. Si usted es realmente ambicioso, y ha visto el pequeño robot de Tony Firshman y Reeves Laurence en el stand de TF Serivces en los “QL Shows” controlado por un QL equipado con una interfaz y Minerva, ¡tal vez desee considerar la manera de programar el robot para que pueda solucionar este puzzle! El programa puede hacer frente a cualquier número (dentro de lo razonable) de anillos, siempre empezando con el anillo 1 para el más pequeño y el número más alto para el anillo más grande. Con un número de varillas pequeño, podemos seguir los movimientos, por ejemplo, con una pequeña pila de monedas, siempre y cuando se puedan recordar que moneda estaban en qué anillo. Con más de 3 ó 4 anillos las instrucciones pueden llegar a ser bastante largas, dada la necesidad de estar rotando continuamente los anillos para evitar que el animo más grande esté por encima de otro más pequeño.

He aquí un programa en SuperBASIC que resuelve el rompecabezas.

100 REMark Towers of Hanoi puzzle
110 INPUT'How many rings > ';rings
120 Hanoi rings,1,2,3
130 :
140 DEFine PROCedure Hanoi(r,peg_a,peg_b,peg_c)
150   IF r = 0 THEN RETurn
160   Hanoi r-1,peg_a,peg_c,peg_b
170   PRINT'Move ring ';r;' from peg ';peg_a;' to peg ';peg_b
180   Hanoi r-1,peg_c,peg_b,peg_a
190 END DEFine Hanoi

Por ahora, podría ser suficiente para comprender cómo trabaja esta rutina el emplear una pila de monedas y reproducir la secuencia según la imprime el programa. Escriba un flujo generalizado de lo que hay que hacer y verá que el patrón a seguir emerge en su cabeza sin darse cuenta. Verá entonces que el problema es fácil de resolver. Escribir un programa para resolver esto no es una tarea obvia, especialmente para producir una solución tan corta como esta.


Fuente:
Artículo original: http://www.dilwyn.me.uk/docs/articles/recursion.zip
Dilwyn Jones (Tal-y-bont, Gales, Reino Unido).

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s