Por lo general no suelo escribir sobre programación en general, pero este tema siempre me ha parecido bastante interesante.

Actualmente estoy programando un algoritmo de compresión de video/imagen sin perdida que se basa en árboles y predictores. La primera iteración del algoritmo fue hacerlo funcionar sin preocuparse demasiado en la optimización. Al ser un algoritmo basado en árboles la primera iteración del algoritmo usaba recursividad para recorrer los árboles.

Una vez que funciona el algoritmo me propuse eliminar la recursividad. El algoritmo debe funcionar de forma fluida en microcontroladores (poca memoria y poca potencia).

La recursividad en computación y para que se entienda facilmente es llamar a una función X dentro de la misma función X. Por lo general los métodos recursivos constan de un caso base y un caso general. El caso base es el que termina la recursividad y el caso general el que hace llamadas recursivas. Aquí tenemos una función que recorre un arbol en profundidad e imprime el contenido de las hojas.

Aquí el caso base es el tercer if, en dicho if no hay llamadas a la función, cuando sale de dicho if se termina la función y el programa continua ejecutandose en esta misma función, ya que posteriormente se habia hecho una llamada a esta misma función.

La recursividad funciona gracias a la pila o stack, esta estructura de datos es del tipo LIFO (Last In First Out) que significa que el último que entra en la pila es el primero que se coge cuando se vaya a sacar un elemento, podemos hacer un simil con un conjunto de plato apilados, cuando vayamos a dejar un plato lo dejaremos arriba del todo y cuando vayamos a necesitar un plato lo cogeremos de arriba. He hablado anteriormente sobre la pila en este blog, como por ejemplo en la categoría security: http://bitybyte.angelluispg.es/category/security/ donde hablo sobre vulnerabilidades de la pila y en esta entrada http://bitybyte.angelluispg.es/2016/07/10/emulacion-de-una-cpu/ donde emulo creo una CPU e implemento una pila.

Cuando hacemos llamadas a procedimientos desde lenguajes de alto nivel lo que se está haciendo a nivel de máquina es empujar los parametros de dicha función a la pila, incrementar el registro SP (Stack Pointer) y hacer un call a la función. Podemos eliminar la recursividad si implementamos una pila software y usamos dicha pila. Usar esta segunda aproximación es mas eficiente, ya que no tenemos que realizar el call a la función.

Los lenguajes de alto nivel suelen implementar una pila en su librería, no es el caso de C, en donde si queremos una pila tendremos que programarla nosotros mismos. Aquí dejo mi implementación de pila.

Básicamente lo que hacemos es usar nuestra pila en vez la del sistema. Es mejor ver el ejemplo en vez de explicarlo. Aquí se puede ver el mismo algoritmo de recorrido de árboles en profundidad pero esta vez de forma iterativa

Vemos como se han eliminado las llamadas a la función y ahora se hace uso de la pila software que se ha implementado.