DEV Community

Baltasar García Perez-Schofield
Baltasar García Perez-Schofield

Posted on

Iterando lo recursivo

#spanish #recursive #iterative #java

En otro de mis múltiples proyectos laterales o mascota, o como se desee llamarlos, escribí un pequeño parser para un HTML reducido, para una app de notas. Mi objetivo es que el usuario pueda escribir como en un pequeño procesador de textos, y que el resultado se guarde en MarkDown. El soporte de todo esto es JEditorPane, ya que es una app escrita en Java sobre Swing (me gusta mucho C#, pero poder distribuir toda la aplicación en un solo archivo jar es un puntazo).

El caso es que JEditorPane puede guardar el código en varios formatos, pero el que me pareció más adecuado fue HTML. Así que el objetivo es que el usuario, sin preocuparse de formatos, acabe escribiendo algo parecido a lo siguiente en el editor, para una nota de tareas cotidianas:

<html>
<body>
A realizar:
<ol>
    <li>Recoger la bici del taller.</li>
    <li>Dar de comer a las tortugas.</li>
    <li>Pedir cita para colonoscopia.</li>
</ol>
</body>
</html>
Enter fullscreen mode Exit fullscreen mode

...y que la propia aplicación lo traduzca a lo siguiente:

# Tareas cotidianas

A realizar:

1. Recoger la bici del taller.
2. Dar de comer a las tortugas.
3. Pedir cita para colonoscopia.
Enter fullscreen mode Exit fullscreen mode

Aunque pueda parecer de traducción inmediata (quizás mediante algún tipo de preprocesador), los problemas aparecerían enseguida si no escribiéramos un parser. Su objetivo será convertir la entrada en HTML en un árbol sintáctico. El ejemplo anterior quedaría como árbol sintáctico así:

Root
|________________________|
p                        ol
|                        |______________________________|________|
"A realizar"             li                             li       li
                         |                              |        |
                         "Recoger la bici   "Dar de comer       "Pedir cita para
                          del taller"        a las tortugas."    la colonoscopia"
Enter fullscreen mode Exit fullscreen mode

Y aquí es donde tenemos la curiosidad de hoy. Tenemos que recorrer el árbol para generar texto MarkDown. ¿Cómo recorrer el árbol sintáctico? Una forma sería la siguiente, apoyándonos en la recursividad y en el patrón de diseño "Visitor".

class Tree {
    // ...
    public void run(Visitor v)
    {
        this.runOver( v, this.root );
    }

    private void runOver(Visitor v, Element element)
    {
        v.visit( element );

        for(Element subelement: this.subElements) {
            this.runOver( v, subElement );
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

Conseguimos separar así el código que se encarga del árbol del código que se encarga de realizar las diferentes tareas sobre él. El método runOver(v: Visitor, element: Element) recorre todos los elementos usando una estrategia en profundidad. Este método es muy sencillo, gracias al uso de la recursividad: todos los elementos son visitados empleando, de hecho, muy poco código.

Si tuviéramos una clase Visitor como la siguiente:

class Visitor {
    // ...
    public void visit(Element element)
    {
        String elementText = element.toString();

        if ( !elementText.isEmpty() ) {
            text.append( elementText );
            text.append( '\n' );
        }
    }

    private StringBuilder text;
}
Enter fullscreen mode Exit fullscreen mode

Se ejecutaría así (lo siguiente es una representación del stack o pila de llamadas):

runOver( root, v )
    |-runOver( p, v )
    |    |-runOver( p.get( 0 ), v );
    |-runOver( ol, v )
    |    |-runOver( ol.get( 0 ), v )
    |    |    |-runOver( li.get( 0 ), v )
    |    |-runOver( ol.get( 1 ), v )
    |    |    |-runOver( li.get( 0 ), v )
    |    |-runOver( ol.get( 2 ), v )
    |    |    |-runOver( li.get( 0 ), v )
Enter fullscreen mode Exit fullscreen mode

Y obtendríamos la siguiente salida:

A realizar:
Recoger la bici del taller.
Dar de comer a las tortugas.
Pedir cita para colonoscopia.
Enter fullscreen mode Exit fullscreen mode

La recursividad tiene dos desventajas: la primera se evapora con el tiempo, y es que al principio cuesta pensar y entender código que se llama a sí mismo. Es más fácil si se tiene en cuenta el caso más importante: el caso base, en el que se produce el retorno de las llamadas recursivas. En este caso, se trata de aquel elemento que no tiene subelementos.

La seguna desventaja tiene que ver con el rendimiento: lo cierto es que el simple hecho de utilizar recursividad supone el riesgo de desbordar el stack, es decir, la pila de llamadas. Cada llamada recursiva supone una entrada más en la pila de llamadas, por lo que, si uno de nuestros árboles tiene 100 elementos de profundidad (es decir, antes de que se produzca el retorno), se reservarán 100 entradas en el stack (aunque algunos compiladores pueden hacer ciertas optimizaciones en algunas situaciones).

En cualquier caso, no tendremos este problema si utilizamos un enfoque iterativo. Es decir, si en lugar de un algoritmo que se invoque a sí mismo para cada elemento, utilizamos un bucle que enumere los elementos. Si pensamos en el papel del stack, entonces llegaremos a la conclusión de que la pila de llamadas hace las veces de colección de elementos visitados: cada nueva llamada se realiza por cada uno de los subelementos de un elemento dado, y cada retorno se realiza porque ya se han visitado todos los subelementos.

La estrategia es sustituir esta pila de llamadas implícita, el stack, por una colección explícita, una colección real en nuestro método run() (el método privado runOver() ya no será necesario). La cuestión es que, si utilizamos una pila, tendremos que introducir los subelementos de un elemento dado en el orden inverso a como aparecen de manera natural. Así que, en su lugar, emplearemos una cola.

Partamos entonces de una cola: es decir, se introducen elementos por el final y se retiran por el principio. En esta cola introducimos la raíz (el elemento root), y el bucle se ejecuta mientras la cola esté vacía. Cuando visitamos un elemento, añadimos sus subelementos al final de la cola, y continuamos con el siguiente en el principio de la cola.

class Tree {
    // ...
    public void run(Visitor v)
    {
        var elements = new ArrayDeque<Element>();
        elements.add( this.getRoot() )

        while( !elements.isEmpty() ) {
            var element = elements.peek();

            elements.remove();
            elements.addAll( element.getSubElements() );

            v.visit( element );
        }
}
Enter fullscreen mode Exit fullscreen mode

Supongamos el ejemplo anterior, la nota de tareas a realizar. Supongamos que queremos En la primera vuelta introducimos la raíz, por lo que se elimina y se introducen sus subelementos. El contenido de elementos pasa a ser:

elementos -> [ p, ol ]
text      -> ""
Enter fullscreen mode Exit fullscreen mode

Se toma el primer elemento p, siendo su único subnodo el texto "A realizar.". Entonces, p se elimina.

elementos -> [ ol, "A realizar." ]
text      -> ""
Enter fullscreen mode Exit fullscreen mode

En el siguiente paso, se toman los hijos de ol, y se incluyen al final de elements.

elementos -> [ "A realizar.", li, li, li ]
text      -> ""
Enter fullscreen mode Exit fullscreen mode

Ahora se toma el primer elemento. Este es el único hasta ahora que contiene texto, por lo que se introduce en el StringBuilder. El texto no tiene subelementos, por lo que la cola no se ve afectada.

elementos -> [ li, li, li ]
text      -> "A realizar.\n"
Enter fullscreen mode Exit fullscreen mode

Volvemos a tomar el primer elemento, para añadir sus subelementos.

elementos -> [ li, li, "Recoger la bici del taller." ]
text      -> "A realizar.\n"
Enter fullscreen mode Exit fullscreen mode

Y lo hacemos de nuevo.

elementos -> [ li, "Recoger la bici del taller.", "Dar de comer a las tortugas." ]
text      -> "A realizar.\n"
Enter fullscreen mode Exit fullscreen mode

Y de nuevo.

elementos -> [ "Recoger la bici del taller.", "Dar de comer a las tortugas.", "Pedir cita para colonoscopia." ]
text      -> "A realizar.\n"
Enter fullscreen mode Exit fullscreen mode

A partir de ahora, como el texto no contiene subelementos, simplemente, en las siguientes tres vueltas de bucle, se añaden los textos al StringBuilder.

elementos -> [ "Dar de comer a las tortugas.", "Pedir cita para colonoscopia." ]
text      -> "A realizar.\nRecoger la bici del taller.\n"
Enter fullscreen mode Exit fullscreen mode

Seguimos...

elementos -> [ "Pedir cita para colonoscopia." ]
text      -> "A realizar.\nRecoger la bici del taller.\nDar de comer a las tortugas.\n"
Enter fullscreen mode Exit fullscreen mode

Y finalizamos. Al no contener ningún elemento, el algoritmo termina.

elementos -> []
text      -> "A realizar.\nRecoger la bici del taller.\nDar de comer a las tortugas.\nPedir cita para colonoscopia.\n"
Enter fullscreen mode Exit fullscreen mode

¡Hurra! Nuestro código se ejecuta sin necesidad de preocuparse de si la complejidad de nuestro árbol puede o no desbordar el stack. Además, nuestro código, al efectuar menos llamadas a funciones, será más rápido. A cambio, eso sí, empleamos más memoria, la de la cola elementos. ¡Siempre tendremos que cambiar rendimiento por memoria y viceversa!

Top comments (0)