¡Recursividad!

¡Buenas!

Hoy os traigo un script diminuto que incluso podría hacerse en una sola línea, por ejemplo usando find (os animo a comentar cómo se haría), así que este es uno de esos casos que no son tan útiles. Lo interesante es que tiene una función recursiva y me permite hablar de ello.

Las funciones recursivas son funciones que se llaman a sí mismas.

Recursividad, véase Recursividad

La recursividad es interesante porque permite solucionar problemas complicados de forma simple como ocurre en este caso. Además, es una de las bases de la programación  funcional (cosa de la que hablaré en algún momento).

Bien. Este es el script, está hecho en Bash, aunque el lenguaje es lo de menos.

#!/bin/bash

function SCAN_DIR ()
{
 FILES=`ls "${1}"`                # Lista los archivos del directorio
                                   # que se recibe como argumento.

 for FILE in $FILES; do           # Recorre la lista.
     NEW_PATH="${1}/${FILE}"

     if [ -d $NEW_PATH ]; then    # El archivo es un directorio.
         SCAN_DIR "${NEW_PATH}"   # Escanea ese directorio.
     else                         # El archivo NO es un directorio.

         # Si el archivo es un .wav muestra su path y lo convierte a mp3:
         if [ "${NEW_PATH##*.}" == "wav" ] ; then
             echo "$NEW_PATH"
             lame -V 1 "$NEW_PATH" "${NEW_PATH%.wav}.mp3" 1>&2 2> /dev/null
         fi
     fi
 done
}

SCAN_DIR "."   # Escanea el directorio en el que se encuentra el script

El objetivo del script es convertir archivos de .wav a .mp3. Esto lo hará recorriendo todo el árbol de directorios desde la carpeta en la que se encuentre el script aunque es bastante sencillo cambiarlo para que tome la carpeta que nosotros queramos.

Si os fijáis, la función SCAN_DIR() se llama dentro de la función SCAN_DIR(). Esta es la recursividad: tenemos una función que se llama a sí misma.

Paso a paso este programa lista los archivos en el directorio que la función SCAN_DIR reciba como argumento. Por cada uno de ellos crea un nuevo path que sea el path de origen con el nombre del archivo añadido como siguiente salto. De esta forma crea un path relativo al archivo desde el directorio en el que se encuentra el script.

Aquí se llega al primer if. Si el archivo es un directorio (el -d comprueba si el archivo es un directorio) se escanea el directorio. Si no lo es y la extensión del archivo es wav se convierte a mp3 usando lame. Para comprobar la extensión utiliza unos operadores que no conocía cuando hice el script (buscad por ahí, es chulo el tema). El “1>&2 2> /dev/null” desvía la salida estándar a la de errores y la de errores a /dev/null, esto significa (resumiendo mucho) que desecha el output de pantalla del lame (si queréis saber algo más de esto preguntad).

Organizado todo esto, se dispara el tema lanzando un SCAN_DIR del directorio actual (“.”).

Esto hace que el programa recorra los archivos del directorio, en el momento que uno de ellos sea un directorio entrará en él y lo recorrerá, si uno de ellos es un directorio lo recorrerá y así sucesivamente. Cuando termine con los archivos del directorio, volverá al directorio anterior y seguirá con sus archivos, etcétera.

En el siguiente gráfico se aprecia mejor lo que este programa hace. Lo interesante es ver lo sencillo que es optar por la recursividad en casos como este viendo gráficamente lo que está pasando.

Arbol de directoriosEn el gráfico se muestra un árbol de directorios relativamente simple con unos nombres poco originales. Las flechas representan los saltos que daría el script siguiendo lo que he explicado más arriba.

Cada uno de los triángulos de colores representa una ejecución de la función SCAN_DIR. Encima de cada uno de ellos se representa qué parámetro de entrada recibiría en ese caso.

El objetivo de los triángulos es representar gráficamente que un problema tipo árbol, como este, puede diseccionarse, en general, en diferentes pequeños problemas idénticos del tamaño de esos pequeños triángulos  y puede atacarse recursivamente con una función muy sencilla sin complicarnos. Intentad hacerlo de otra forma y me contáis si podéis hacerlo más simple.

Este tipo de funciones no sólo son interesantes en problemas de este estilo, pero siempre debe estar en vuestra cabeza la asociación árbol-recursividad. Puede que os saque de algún apuro.

Hace tiempo que quería hablar un poco de este tipo de funciones en parte porque en las asignaturas de programación que tenemos en la carrera ni nos las mencionaron. Sólo te enseñan algo de C y C++, no a programar bien, lo que es un error grave en mi opinión (hablaré de esto en otro momento). Pero en parte (supongo) tampoco lo hacen porque estas funciones son un poco peligrosas: un gran poder conlleva una gran responsabilidad y esas cosas.

Cuando se ejecuta una función dentro de un programa, el ordenador guarda el estado en el que estaba antes de entrar en la función en una memoria para luego saber volver a la situación anterior. Esta memoria no deja de ser la memoria normal, pero se comporta de forma especial, como una pila (de apilar, no de batería) o Stack en inglés. Esta pila se comporta como un taco de papeles en el que se pueden añadir o quitar de la parte superior (también se llama cola LIFO Last In First Out). Cuando se entra a la función, el programa guarda su estado en esta memoria (coloca un papel) y al salir lo recoge, pero si dentro de la función volviese a llamarse a otra tendría que guardar el estado que tenía dentro de esa función (colocar un papel encima del anterior) y así sucesivamente haciendo la pila cada vez más grande. Toda esta información iría apilándose en el stack a la espera de que programa fuese saliendo de las funciones para ir recogiéndola poco a poco a medida que fuera saliendo.

Cuando usamos funciones recursivas explotamos este comportamiento al máximo y si no las hacemos bien podemos tener problemas.

Imaginad que el árbol de directorios que tenemos es infinito, habría tantos papeles en la pila que se caería todo, porque todo tiene un límite en este mundo. A este fenómeno se le llama stack overflow y no deja de ser un desborde de la pila.

Este caso no debería ocurrir con funciones recursivas normales, puesto que la cantidad de cosas que podemos añadir a la pila es enorme hoy en día (aunque ojo cuando estéis haciendo cosas en sistemas embebidos o limitados porque puede pasar), sin embargo en una función mal hecha esto puede acabar mal.

Una función recursiva mal hecha significa que puede haber un caso en el que la función no tenga fin, que siempre vaya a llamarse a sí misma de nuevo. Esto es intolerable y siempre nos llevará a un indeseado desborde (explota todo). Lo que nos lleva a la gran advertencia: Las funciones recursivas siempre tienen que tener un final.

Eso es todo. Se puede profundizar mucho más en estos temas porque me he metido en un berenjenal fino, pero con esto creo que ya tenéis para un rato.

Resumen de ideas importantes:

  • Asociar árbol con función recursiva.
  • Las funciones recursivas siempre tienen que tener un final.

Y unos enlaces interesantes:

Creo que me he pasado tres pueblos con la longitud de esto, pero bueno. Se nota que me gusta el tema ¿no?

Un abrazo. Espero que aprendáis algo con esto o que al menos os divirtáis leyéndolo.

Anuncios

6 pensamientos en “¡Recursividad!

  1. Aha! Buena explicación!

    Allá va un reto. Como harías para también incluir directorios ocultos en la busqueda? 😀

    Un saludeteee!

    • Thanks Kaian!
      Para incluir los directorios ocultos me sale, así pensando poco, añadir la opción -A al ls.
      Quedaría todo igual, con el siguiente cambio:
      FILES=`ls -A “${1}”`

      El -A es “almost-all”, es como el -a pero sin mostrar el directorio actual (“.”) ni el superior (“..”). Mucho ojo, con el -a hacemos stack overflow porque se escanea el mismo directorio infinitas veces.

      Lo he probado y parece que chuta bien.

      Un abrazo!

  2. Fork bombs: Concurrencia y recursividad – Free Hacks!

  3. Perl Datadumper recursivo – Free Hacks!

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