La Esencia de la Recursión

¡Hola! Si estás aquí es porque quieres complementar un poco tus conocimientos respecto de la recursión para entenderla mejor. Estás en el lugar indicado para hacerlo.

Mi objetivo con este post es el de darle un vistazo a la esencia de la recursión, ¿de qué estamos hablando exactamente cuando hablamos de recursión? ¿Qué no era solo sobre funciones que se llaman a sí mismas?

Vamos a explorar a continuación algunos ejemplos de fenómenos recursivos que ilustrarán bastante la idea de la recursión. Voy a tratar de no entrar en definiciones muy formales, porque quiero tratar de comunicarlo de una manera más conceptual y visual.

Pensamiento recursivo

Un fenómeno o sistema recursivo es aquel que está definido en términos de sí mismo (o mejor, que está definido en términos de elementos de una estructura o naturaleza muy similar).

Fuente: https://www.smbc-comics.com/comic/recursion

En ciencias de la computación recordaremos mucho problemas como el cálculo del factorial, la sucesión de Fibonacci, búsqueda y ordenamiento eficientes, etcétera, pero estamos cayendo en mecanizar demasiado el intentar solo ver a la recursión como "una forma rara de iterar en un nuevo nivel", y la recursión va mucho más allá de esto.

La idea de la recursión es aprovechar las características de un fenómeno o sistema en cuanto a sí mismo. Lo que quiero decir con esto es que para poder comprender un fenómeno o sistema complejo, debemos comprender sus partes, y a la vez las partes de sus partes, y así hasta dar con el grado de complejidad más pequeño. Una vez dominemos esto, podremos entender no solo a las partes mínimas del fenómeno o sistema, sino que también lograremos ver cómo cada nivel -diferente al mínimo- es un "todo", compuesto de un "todo" más pequeño... Así, cuando lleguemos al nivel más complejo, entenderemos ese "todo" como mucho más que solo la suma de sus partes.

Una analogía que me viene a la cabeza es la complejidad de un organismo vivo. El cuerpo humano, por ejemplo, es un "todo" complejo. Es un sistema, cuyos componentes en un nivel menor también son sistemas (sistema digestivo, circulatorio, etcétera). Luego cada uno de esos sistemas tiene como componentes otros sistemas (conjuntos de tejidos, que a su vez son sistemas de células, que a su vez son sistemas de organelas, que a su vez son sistemas de aminoácidos, etcétera, etcétera). Aquí el fenómeno recursivo es el de "sistema de componentes que son sistemas", y la naturaleza compartida es de la misma definición de sistema (partes que en conjunto forman un "todo" para cumplir una función de acuerdo a entradas para dar salidas). Este es un ejemplo de recursión de definición o de funcionalidad.

Entonces, lo que quiero resaltar de la recursión es que es algo con lo que podemos diseccionar y comprender fenómenos complejos con facilidad, aprovechando una característica en común en los niveles de complejidad de los mismos; no obstante, también la podemos usar para crear fenómenos complejos.

Fractales

Son quizás el ejemplo más clásico en cuanto a recursión de estructura.

Un fractal es un sistema geométrico compuesto por sistemas geométricos de menor nivel que comparten y replican una estructura similar.

Hay centenares de tipos de fractales definidos en varias dimensiones, reglas, patrones, e incluso bases numéricas. Exploremos unos ejemplos sencillos.

Círculos binarios internos

Es un fractal muy simple: Círculo grande, que tiene círculos más pequeños a la izquierda y la derecha, que tienen círculos más pequeños a la izquierda y la derecha, que tienen [...] Ok, ya paro... El asunto es que debe parar en algún punto, y eso es el caso base, que aquí corresponde a una circunferencia simple.

Podemos generalizarlo como el fractal C(R): círculo grande que tiene dos fractales C(R/2) en su interior, para un radio R (a la izquierda y la derecha del centro).

Notemos cómo se repite la regla de la estructura (el problema recursivo) en cada nivel de complejidad hasta llegar al caso base:

Árbol binario

Es un fractal clásico y simple donde la regla es "estirar y ramificar".

El caso base será una línea, y la definición recursiva es la regla que acabo de mencionar arriba, que funciona así:

    Árbol nivel N:
        "Estirar": Dibujar una línea con un ángulo de referencia
        "Ramificar": 
            1. Girar a la izquierda 40 grados de la dirección del nivel actual
            2. Dibujar Árbol nivel N-1 en esa dirección y con tamaño reducido
            3. Girar a la derecha 40 grados de la dirección del nivel actual
            4. Dibujar Árbol nivel N-1 en esa dirección y con tamaño reducido

Aquí un ejemplo de cómo se vería:

Nota que en cada nivel se refleja "Estirar" con un color distinto, siendo cada recta el tronco de cada sub-árbol.

La curva de Koch

Para este fractal, el problema mínimo (nivel 0) es un segmento de recta, y el problema general en el nivel N se define así:

    F <-- K+K-K+K

Para

    F: Fractal nivel N
    K: Fractal nivel N-1
    -: Rotar 120 grados a la derecha
    +: Rotar 60 grados a la izquierda

Esta es una pequeña modificación a la definición formal del fractal como sistema de Lyndenmayer... pero no voy a entrar en detalle en formalidades para ser práctico y claro.

Eso de arriba se interpreta como:

    1. Dibujar el subfractal de nivel más pequeño
    2. Rotar 60 grados a la izquierda
    3. Dibujar el subfractal de nivel más pequeño (en la posición final de 1.)
    4. Rotar 120 grados a la derecha
    5. Dibujar el subfractal de nivel más pequeño (en la posición final de 3.)

Ilustrado:

¡Pásate por mi GitHub por aquí para ver mi implementación de estos fractales empleando Python y Turtle Graphics!

Jugando un poco con la definición de la curva de Koch, sobre una base de un triángulo equilátero, lleva a la obtención del copo de nieve de Koch:

Cortesía de António Miguel de Campos - Wikimedia Commons

Programación Dinámica

Bueno, ya vimos unos buenos ejemplos que ilustran el comportamiento recursivo a nivel de estructura, pero vamos a darle una mirada a un especial de la aplicación de la recursión en donde no haremos recursión.

"¿Pero qué cosas dice este sujeto?", estarás pensando y así es, no vamos a hacer que una función se llame así misma, sino que vamos a hacer que esa función se aproveche de la naturaleza recursiva del problema para resolverlo. ¡Ah! ¡Y para hallar soluciones óptimas de forma eficiente, además!

Ok, quizás lo anterior es parcialmente cierto respecto a "no hacer recursión". La programación dinámica tiene dos esquemas: Bottom-up y Top-down. El primero se implementa de forma iterativa (sin hacer recursión) y el segundo de forma recursiva (¡me atrapaste!). A lo que quiero llegar es que el caso del esquema Bottom-up se tiene una recursión por definición, más no por estructura, como sería en el esquema Top-down.

El caso no es tanto cuál esquema escojas, sino cómo estás entendiendo el problema en términos de subproblemas que tienen su misma naturaleza. Vamos a valernos de esa propiedad para resolver problemas en todos los niveles de complejidad, partiendo de la solución sus subproblemas.

Lo anterior también es importante para el tema de hallar una solución óptima (es decir de máximos y mínimos). La naturaleza recursiva del problema hace que lo podamos definir como un problema de optimización basado en soluciones óptimas a los subproblemas, cosa que se repite recursivamente en todos los niveles de complejidad. A esto se le conoce como Subestructura Óptima y es la clave para garantizar que la solución en el nivel superior es la óptima de todo el problema.

Para ver una explicación más detallada, revisa mi post "Fundamentos de Programación Dinámica".

Conclusiones y recursos

Hemos visto que hacer recursión es más que solo llamar una función a sí misma, es pensar en cómo se replica la esencia de cualquier fenómeno o sistema en sus niveles de complejidad inferiores (el caso de las funciones siendo una particularidad de esto).

Aprender a dominar la recursión en formas tanto conceptual como algorítmica es clave para abordar con mucha más facilidad cualquier disección o creación de fenómenos o sistemas complejos, que se puedan definir de manera recursiva en funcionalidad o en estructura.

A pesar de que la recursión simplifica la solución de muchos tipos de problema de una forma elegante, hay que recordar que la pila de llamados de funciones en memoria es limitada, así que hay que evaluar muy bien si la recursión es la mejor forma de establecer dicha solución.

¿Te ha picado la curiosidad? Aquí te tengo algunas referencias adicionales para que explores un poco más:

• Recursion - Wikipedia (EN)
• Fractal - Wikipedia (EN)
• Fractal - Wikipedia (ES)
• The Nature of Code - Daniel Shiffman
• Recursion - LMU Computer Science
• Gödel, Escher, Bach: Una eterna trenza dorada - Douglas R. Hofstadter (es un libro que explora muchos sistemas y fenómenos recursivos, pero es más orientado hacia la contemplación filosófica de las formalidades matemáticas en cada uno)

Por supuesto, también es un tema que está al alcance de una Googleada, ya que es un tema muy popular; aparece y tiene aplicación en muchas áreas: arte, lenguajes, música, naturaleza, ingeniería, matemática, y ciencias de la computación (tanto en la algoritmia como en la creación de sistemas inteligentes). Hay miles de sitios Web que lo cubren de muchas maneras, por lo que estoy seguro que en unos minutos de investigarlo darás con gran número de temas interesantes.

Ha sido todo un gusto cubrir el tema de la forma más sintetizada posible.

¡Nunca pares de aprender!

---

Si tienes algún feedback, duda o comentario, puedes encontrarme en LinkedIn como Juan Camilo Álvarez Jurado (jcalvarezj) y en Twitter como @jcalvarezj8. Sígueme también en GitHub como jcalvarezj.

Fundamentos de Programación Dinámica

La Programación Dinámica siempre fue un tema que me aterraba años atrás en mis cursos de algoritmia, pero me di cuenta recientemente, luego de tomar la iniciativa y revisarla despacio, de que es algo que puede ser manejable (además de ser una herramienta muy útil en mi cinturón de conocimientos de programación).

Este es un tema que va de intermedio a avanzado en Ciencias de la Computación, por lo que te recomiendo que estés al día con la parte de fundamentos de Análisis y Diseño de Algoritmos y lo leas despacio.

Los algoritmos se presentan en notación de pseudocódigo (intermedio flexible entre lenguaje natural y de programación), con el fin de presentarlos de forma general (y para acostumbrar al lector a esta notación, que es muy usada en el mundo de la algoritmia).

Definición

Se trata de una técnica de diseño de algoritmos en la que se busca mejorar el tiempo(*) que toma resolver un problema que puede describirse desde una filosofía recursiva. Un problema se describe en una filosofía recursiva cuando lo podemos plantear en término de problemas de menor grado (complejidad o tamaño), que tienen la misma naturaleza que el problema mayor (y por tanto, son a su vez de filosofía recursiva).

(*) "Tiempo" como cantidad de "pasos simples"; medida relativa en el análisis de algoritmos

Para resolver este tipo de problemas, la programación dinámica plantea que se debe buscar la manera de aprovechar las estructuras de datos para almacenar la solución a los problemas de menor grado y reutilizar estas soluciones para no repetir los cálculos. Entonces estamos ganando eficiencia en complejidad computacional de tiempo, al sacrificar algo de complejidad computacional en espacio (lo cual no hay que dejar de tener presente).

La estructura de datos depende del tipo de problema y del sentido que le otorguemos a su contenido. Normalmente se emplean los índices de las estructuras para referir a qué problema están almacenando su solución.

Por último, la programación dinámica es una técnica muy especial para resolver problemas de optimización al evitar la necesidad de llegar a una explosión combinatoria por fuerza bruta (lo que lleva a complejidades exponenciales e incluso factoriales). Para lograr esto, aprovecharemos la filosofía recursiva del problema de la siguiente manera:

• La estructura de datos de apoyo va a almacenar soluciones óptimas a problemas de decisión respecto de las soluciones a subproblemas (que también serán óptimas). A esto es conocido como Subestructura Óptima
• La solución se calcula a partir de las decisiones de optimización que se vean reflejadas en esta estructura.

Esquemas

Existen dos esquemas de implementación de esta técnica que son Bottom-Up (o Tabulación) y Top-Down (o Memoización)

Bottom-Up

Va iterando desde lo más pequeño hasta lo más grande (problemas triviales a problema general). Funciona de la siguiente manera:

1. Identificar y definir los problemas triviales; es decir, cuáles son los problemas más pequeños posibles de los que ya tenemos la respuesta.
2. Verificar cuáles problemas están apenas un nivel más alto que los problemas triviales. Para todos los problemas más grandes, tratar de definirlos a partir de los problemas apenas más pequeños.
3. De manera iterativa, desde el primer problema más grande que el trivial hasta el problema mayor que se quiere resolver, calcular la solución a cada problema a partir de su definición recursiva (serán resueltos a partir de las soluciones que ya se han encontrado para los problemas menores)
4. Obtener la solución en la estructura auxiliar

El pseudocódigo se vería así:

Top-Down

Este esquema trabaja en orden inverso al BottomUp, ya que comienza en el problema general y baja hasta los problemas triviales; esta vez, de manera recursiva. Sigue estos pasos:

1. Pasar por parámetro la estructura de datos auxiliar
2. Establecer como casos base a los problemas triviales (porque ya tenemos su solución).
3. Validar si en la estructura auxiliar está registrada la solución al problema que resuelve el ambiente recursivo actual
4. Si la solución no existe en la estructura auxiliar, hacer recursión para resolver los problemas de menor tamaño y anotarla ahí.
5. Obtener la solución en la estructura auxiliar

El pseudocódigo se vería así:

Ejemplos

Vamos a ver a continuación un par de ejemplos para aterrizar mejor estas ideas.

1. Sucesión de Fibonacci

El ejemplo clásico y más sencillo que mejor muestra el poder de esta técnica y ayuda a entender cómo aplicarla es el de la sucesión de Fibonacci.

Recordemos la definición de la función de Fibonacci:

Y bien, su implementación más sencilla es algo como:

Y bueno, funciona. Puedes calcular con esa lógica el N-ésimo número en la sucesión... Peeeero, si tratas de calcular para un N mayor de 40 o 50, no importa que tengas una máquina súperpoderosa, empieza a tardarse una eternidad en realizar el cálculo y puede que obtengas un resultado, como puede que obtengas un error de desbordamiento de pila (es decir, no hay memoria para la cantidad de llamados de funciones que hay).

Veamos qué pasa.

El árbol de llamados recursivos para N = 7 es este:

 

(Imagen tomada de http://jeffe.cs.illinois.edu/teaching/algorithms/ y modificada con fines ilustrativos)

Como se puede notar, hay una cantidad exagerada de llamados repetidos. Si hacemos un trabajo formal de analizar matemáticamente ya sea bien ese árbol de llamados, o la ecuación de recurrencia que describe la función de complejidad de tiempo   T(n) = T(n-1) + T(n-2) + O(C)  , ¡obtendremos un pesado orden exponencial de  O(2ⁿ) !

Así que, ¿qué podemos hacer?

Bueno, como lo sugiere la programación dinámica, vamos a intentar reutilizar esos cálculos. Veamos cómo se aborda esto en ambos esquemas.

Solución Bottom-Up

Es muy simple. Recordemos:

1. Inicializamos la estructura auxiliar (en este caso un array cuyas posiciones refieren al N que estamos calculando)
2. Definimos los problemas triviales (es decir, lo que ya conocemos: F(0) = 0, F(1) = 1)
3. Iteramos desde el primer problema no trivial hasta el problema que queremos resolver, calculando para cada problema su solución a partir de los problemas más pequeños
4. Usamos la estructura auxiliar para sacar de ahí la solución y eso es todo.

Este sería el pseudocódigo de la receta que he mencionado:

Que visualmente se vería así (no confundirse con los índices, se pueden adecuar según la solución):

(Cortesía de Algorithm Visualizer)

Implementado en JavaScript se vería así:

function fibonacciTabulation(n) {
    const results = new Array(n).fill(0);  
    results[0] = 0;  
    if (n >= 1) {
        results[1] = 1;
        for (let i = 2; i <= n; i++)
            results[i] = results[i-1] + results[i-2];
    }
    return results[n];
}

Solución Top-Down

Ahora intentemos emplear el otro esquema. ¿Cómo era?

1. En la firma de la función pasar la estructura auxiliar como parámetro (un array cuyos índices refieren al término a calcular)
2. Casos base = Problemas triviales (que deben estar ya anotados en la estructura auxiliar)
3. Si no hay anotada en la estructura auxiliar una solución para el N del ambiente recursivo actual, calcular mediante recursión y anotar en la estructura
4. Retornar la solución que esté anotada en la estructura auxiliar

En pseudocódigo queda:

Y como es una función recursiva, podemos definir una función envolvente para simplificar su llamado (y poderle pasar una estructura inicializada):

Y si vemos en este caso el árbol de llamados recursivos que teníamos antes, notaremos que sólo estaremos haciendo uso de una pequeña porción de esos llamados al estarlos reutilizando.

(Imagen tomada de http://jeffe.cs.illinois.edu/teaching/algorithms/ y modificada con fines ilustrativos)

Una implementación en JavaScript:

function fiboMemoization(n, solution) {
    if (n === 0 || n === 1)
        return solution[n];
    else {
        if (!solution[n]) 
            solution[n] = fiboMemoization(n-1, solution) + fiboMemoization(n-2, solution);
        return solution[n];
    }
}
function fibonacci(n) {
    return fiboMemoization(n, [0, 1]);
}

Así que para ambos esquemas podemos notar un comportamiento lineal, es decir, una complejidad de tiempo de  O(N) , pero como estamos reservando memoria según el tamaño de entrada, también tenemos una complejidad espacial de  O(N) 

2. Problema de las líneas de ensamblaje

Ahora veamos cómo podemos utilizar el poder de la programación dinámica en un problema de optimización del mundo real. El problema en este caso es la optimización de tiempo en líneas de ensamblaje industriales. Dice así:

"Se tienen dos líneas de ensamblaje de vehículos, cada una con estaciones en que se añaden o ajustan partes del producto final.

En cada estación el proceso se demora un determinado tiempo, y hay una demora extra si se quiere cambiar de línea de ensamblaje (no se asume el tiempo entre estaciones de la misma línea). Además, el ingreso a las líneas tiene un tiempo distinto, al igual que la salida a la entrega del producto.

Se requiere de un algoritmo que ensamble un vehículo empleando el menor tiempo posible, y con una complejidad de tiempo de ejecución óptima."

Para resolver este problema nos vamos a valer de la propiedad de Subestructura Óptima que ya hemos mencionado anteriormente. Te la recuerdo: la solución óptima de un problema va a estar dada a partir de la decisión de optimización entre las soluciones a subproblemas, que también serán óptimas.

¿Suena un poco enredado? Vamos al ejemplo y veamos despacio qué significa.

Para ser práctico lo resolveré mediante el esquema Bottom-Up, así que te dejo como reto implementarlo mediante Top-Down

Antes que nada, entendamos el problema. Para ello he elaborado un diagrama que lo ilustra:

La notación es simplemente para denotar las características del problema en función de las posiciones de líneas y estaciones. Esto da pista de que vamos a tener una estructura auxiliar de dos dimensiones: filas para líneas y columnas para estaciones.

Entonces como datos de entrada del problema tenemos los siguientes arrays:

        e[i] :  Tiempo extra que toma entrar inicialmente a la línea  i
        s[i] :  Tiempo extra que toma salir al final de la línea  i
        S[i][j] :  Tiempo que tarda la estación  j  de la línea  i  en obrar
        P[i] :  Tiempo que se tarda en pasar a la línea  i

Ahora nos toca establecer la estructura auxiliar:

        T[i][j] = El tiempo óptimo para la estación  j  de la línea  i

Notemos que simplemente estamos usando las dimensiones del problema (línea, estación) para identificar cada problema de forma única.

Ahora, identifiquemos los problemas triviales:

En la primera estación de cada línea no tenemos que optimizar cosa alguna; ya tenemos la solución para ambas. Entonces guardamos esta información en nuestra estructura auxiliar:

T[1][1] = e[1] + S[1][1]
T[2][1] = e[2] + S[2][1]

La primera definición se lee: "el tiempo óptimo para la estación 1 de la línea 1 es la suma del tiempo de entrada de la línea 1 y el tiempo de operación de esa estación (o sea, e[1] y S[1][1], respectivamente)"... Y pues, ya te imaginas cómo se lee la segunda.

¿Qué sigue? -- Bueno, recordando un poco el esquema, luego de pensar en los problemas triviales ya podemos pensar en los problemas de filosofía recursiva.

Desde la segunda estación en adelante (en cualquier línea) hay un problema de decisión: ¿desde cuál ruta, sumado al tiempo de la estación, es menor el tiempo que toma el proceso? (La imagen ilustra el problema de decisión para el problema referido a la estación S(1, 2) )

T[1][2] = min{ T[1][1] + S[1][2] , T[2][1] + P[2][1] + S[1][2] }
T[2][2] = min{ T[2][1] + S[2][2] , T[1][1] + P[1][2] + S[2][2] }

Nuevamente, tratemos de leer esto para el primer problema: "el tiempo óptimo para la estación 1 de la línea 2 es el menor entre el tiempo que toma la ruta horizontal y el tiempo que toma la ruta diagonal".

• La ruta horizontal será la suma del tiempo óptimo en la estación anterior y el tiempo que tarde esta estación
• La ruta diagonal será la suma del tiempo óptimo en la estación anterior de la otra línea, el tiempo que tarda el paso de línea y el tiempo que tarda esta estación

Entonces lo que hay que hacer es ver cómo se comporta en general... hagamos inducción. Los siguientes problemas serían:

T[1][3] = min{ T[1][2] + S[1][3] , T[2][2] + P[1][2] + S[1][3] }
T[2][3] = min{ T[2][2] + S[2][3] , T[1][2] + P[1][2] + S[2][3] }

Entonces notando el patrón lo podemos generalizar, para N estaciones, a

T[1][N] = min{ T[1][N-1] + S[1][N] , T[2][N-1] + P[2][1] + S[1][N] }
T[2][N] = min{ T[2][N-1] + S[2][N] , T[1][N-1] + P[1][2] + S[2][N] }

Luego del problema de la estación final (N), calculamos en una posición N+1 el resultado de sumar la solución óptima para N y el tiempo extra de salida. Notar que entonces la estructura en realidad debería tener N+1 columnas

T[1][N+1] = T[1][N] + s[1]     
T[2][N+1] = T[2][N] + s[2]     

Finalmente, se obtiene la solución a partir de la información que tenemos en la estructura de datos auxiliar. Es simple, dado que esa estructura refleja las decisiones en cálculos óptimos, podemos recorrerla obteniendo las posiciones (línea, estación) el menor valor de tiempo entre una estación de las dos líneas.

Vamos a ver cómo podemos formalizar esta solución en algoritmos:

¡Y ese es todo el algoritmo! No hay cosas muy raras más que rellenar la estructura de datos auxiliar con soluciones óptimas.

Es hora de sacar del horno la solución al problema:

Un pequeño seguimiento rápido a un problema de ejemplo (animación):

¡Y ya está resuelto!

Por último, si quieres, puedes echarle un vistazo a cómo se vería una implementación en Java de este problema, aquí en mi repositorio personal de GitHub.

Conclusiones

En este post hemos aprendido las bases que se necesitan para entender cómo resolver problemas de manera eficiente mediante programación dinámica. El todo de ello está en la filosofía recursiva, la estructura de datos auxiliar, la reutilización de soluciones y las decisiones de optimización (para ese tipo de problemas).

Todos los problemas tienen una forma distinta de ser abordados y requieren de buen ingenio para saber cómo sacarle el mayor provecho a las estructuras de datos. Es por ello que te invito a explorarlos y ver la variedad de formas que hay de representarlos y resolverlos (aunque el reto está en tratar de pensar en cómo hacerlo uno mismo).

Si quieres saber más

Aquí te comparto algunos recursos para explorar y profundizar más.

• Demystifying Dynamic Programming - Alaina Kafkes
• Algorithms - Jeff Erickson
• Dynamic Programming for Interviews - Sam Gavis-Hughson, Interview Coach of Byte By Byte LLC
• Dynamic Programming - Joe Del Rocco (Cacti Council)
• Introduction to Algorithms - Thomas H. Cormen
• Fundamentals of Algorithmics - Gilles Brassard, Paul Bratley
• Algorithm Design - Jon Kleinberg y Éva Tardos

Otros problemas clásicos incluyen:

• El problema del cambio (making change)
• La subsecuencia común más larga
• La mochila (o knapsack en inglés) - Explicación por Joe Del Rocco (Cacti Council)
• El problema del consumo de calorías (una versión modificada del problema de la mochila) - Aquí una pista de cómo abordarlo por Michelle Xie
• Recorte de varillas para obtener el precio óptimo (rod cutting)
• El vendedor viajero (travelling salesman)
• Y muchos más

Por supuesto hay muchos más recursos al alcance de una Googleada, unos más entendibles que otros. Te animo a ir despacio, con calma y a no rendirte. En ocasiones algunos problemas, su definición, y su solución pueden parecer complicados de abstraer, y por eso te pido perseverar un poco.

(¡Hey, a propósito! ¡Dale un vistazo al Curso de Programación Dinámica y Estocástica con Python de David Aroesti en Platzi! Aquí David nos presenta una pequeña introducción al tema con el ejemplo de la sucesión de Fibonacci resuelta mediante memoización)

Recuerda también ayudarte mucho de forma visual con dibujos y diagramas, para que veas el problema en otros ángulos y puedas dar con alguna propiedad de éste que puedas aprovechar para resolverlo con mayor facilidad.

Eso es todo por ahora, muchas gracias por tu atención e interés.

¡Nunca pares de aprender!

---

Si tienes algún feedback, duda o comentario, puedes encontrarme en LinkedIn como Juan Camilo Álvarez Jurado (jcalvarezj) y en Twitter como @jcalvarezj8. Sígueme también en GitHub como jcalvarezj.

Docker in a Nutshell

Docker is a tool that allows to build, distribute, and execute software with great ease almost anywhere. It is based on the creation of elements called "containers", which resemble virtual machines but are much more lightweight. Containers work directly with the host system's kernel and optimally manages resources and dependencies to execute software inside it. In this post we will explore a little bit the concepts and use of Docker to easily build, distribute, and execute a piece of software.

Refer to the official documentation on https://docs.docker.com/ 

Containers

Docker's containers comprise the software application to be executed, its dependencies, and its necessary physical resources. We can understand them as "lightweight virtual machines", but in the mode of isolated processes that run natively on the host system.

Containers help standarize the way to deliver software products. They are flexible for any type of application, portable for running the software the same way in every machine, scalable for managing resources or multiple instances, and secure for allowing access to only the necessary parts of the system.

Images

Images correspond to the executable artifacts of software that can be materialized as a running container. We can understand images as blueprints for containers, meaning that we can create as many containers as we want based on an image.

An image will determine a set of operations to create a container based on source code, CLI commands, and other images.

DockerHub

Just like GitHub allows to store and share code repositories, DockerHub allows to store and share images, facilitating the distribution of the building elements of containers.

To get an image it is enough to run the following command:

    docker pull name-of-image

In order to be able to upload an image to DockerHub it is necessary to have an account and then run the following commands:

    docker login

    docker push name-of-image

Creating an Image

To create an image based on a project we need a file called "Dockerfile". This file contains several instructions, one per line, that will give form to the image. Each one of these instructions are called layers and are efficiently interpreted by Docker to identify other required images, avoid repetition through a cache, and allow a sequential flow of execution.

This is an example of a Dockerfile:

FROM node:12 ## Dependency on the Node version 12 image

COPY ["package.json", "package-lock.json", "/usr/src/"] ## Copy files to folder

WORKDIR /usr/src ## Set a folder as wokring directory for the container

RUN npm install ## Simple execution of CLI commands

COPY [".", "/usr/src"]

EXPOSE 3000 ## Expose ports

CMD ["npx", "nodemon", "index.js"] ## Execute command as main process

Then, to build the image, standing on the location of the Dockerfile:

    docker build -t image-name .

The last argument of the above command is the Docker build context, in other words the folder where the Docker file is located. If a file must be specified, use the -f option to set it.

The image name can follow this convention:   dockerhub-user-name/image-name:tag-name

Although the user name and tag are optional, they should be used for DockerHub.

Running an Image

This command runs an Image, creating an instance of a running Container:

    docker run [options] image-name

Where options can be:

    -d              to run in detached mode (run in the background)

    --name      to specify a unique name for the container

    -p              to specify port mapping  (local-port:container-port)

    --env         to set an environment variable

    -it              used for some interactive images like Ubuntu, shells, etc.

    --rm           to automatically remove the container after it stopped

For instance:

    docker run -d --name myapp -p 3000:3000 --env MONGO_URL=mongodb://mydb:27017/test myimage

Will run a container named myapp from the image myimage, mapping the host machine's port 3000 to the container's port 3000, and setting the MONGO_URL environment variable. Notice that this variable uses mydb as host for the connection string; Docker will try to search for a mydb container to link it there.

Managing Containers

Running containers can be listed using  docker ps  (use the -a option to show all containers)

To gracefully stop a container use the  docker stop container-name-or-id  command. This will send the container's main process a SIGTERM signal first, but if it doesn't respond to that it will send a SIGKILL signal after some time.

To delete a container use   docker rm container-name-or-id (use the -f option to force)

Some running containers can execute commands/programs. To do this:

    docker exec [options] container-name-or-id command

Connecting Containers

Containers can be connected through vitrual networks in order to communicate and interact with each other. We can create a virtual network open to connecting containers using the command

    docker network create --attachable network-name

To connect running containers to this network:

    docker network connect network-name container-name-or-id

Virtual networks can be inspected using

    docker network inspect network-name

Data Access

There are several ways in which Docker allows to have access to files in a system: Bind Mounts, Volumes, direct file copy, and TMPFS Mount (for temporary data).

Bind Mounts

A Bind Mount, or "directory mirroring", is an operation that links a host system's directory with a container's directory, so that whatever happens in one is reflected on the other.

To achieve this, just include the -v option followed by  host-directory-path:container-directory-path, right before the name of the image in a docker run command. For example:

    docker run -d --name my-mongo-db -v /home/username/somefolder:/data/db mongo

Warning: As this method will allow for full read/write access to a directory, it could mean a security risk if misused.

Volumes

These are an evolved alternative to Bind Mounts and are more secure. Volumes are spaces of data within containers that are persisted in Docker and can be managed only by users with privilages.

To create a volume use

    docker volume create volume-name

Then, to use it for the execution of an image, use the --mount option:

    docker run -d --name my-mongo-db -mount src=volume-name:dst=path-to-directory

This way, when another container accesses the created volume, it will find all the changes persisted from the first container inside the directory it points to.

Docker Compose

There is an incredible complement for Docker called Docker Compose that simplifies greatly the creation, communication, and administration of multiple containers. To install refer to https://docs.docker.com/compose/install/ 

Docker Compose requires a docker-compse.yml file structured as follows:

- The version of the Compose file (for support of different features according to the version)

- A list of Services (which will be translated into container instances)

- Volume management, among other features

As an example:

version: "3.8"

services:

myapp:

build: . # Especify the folder of the Docker build context

environment: # Define environment variables

MONGO_URL: "mongodb://mydb:27017/test"

depends_on: # What other services are needed to run this one

- mydb

ports: # Port mapping (host machine:container)

- "3000:3000"

volumes: # Define data access through volumes (automatically created)

- .:/usr/src # Mount all from here to /usr/src

- /usr/src/node_modules # Ignore this folder

mydb:

image: mongo

The above Compose file, working on version 3.8, will create two containers: myapp and mydb.

myapp will require a build previous to running. This can be done using

    docker-compose build 

The above command will build an image using the Dockerfile in the specified directory, named with the convention:  project-folder_service-name

To run, after building the necessary images, execute  docker-compose up  which will start all the services as containers and automatically communicate them through a virtual network. It also supports a detached mode witha -d option.

To shut down gracefully and remove all containers, execute  docker compose down.

It is also possible to specify the number of instances of containers from a specific service using

    docker-compose up -d --scale service-name=number-of-instances 

(If multiple instances require different ports, it is possible to specify port ranges in the Compose file. For example: 3000-3001)

Food log 000

Guess I feel like spamming food pictures here as well. I love food, both its flavor and aesthetics.

Look at this beautiful dish I had in "La Patatería", located in my lovely hometown, Manizales.

This is a delicious mix of beef, squid, crab, and shimp, with some cheese sauce and french fries -but I can't remember the name of the dish-. I want some more right now! Please! Can I have more? I need it!

According to picture's metadata, this was in January.

This is the second dish I eat in that place. Both amazing so far... Gotta try 'em all!

Dynamic Programming basics

Dynamic Programming always was a topic that really scared me back at school, but it is something that can become really manageable once you get the trick of it. Let's define it first.

Dynamic programming is an algorithm design technique that attempts to improve the time that takes solving a problem that can be stated in a recursive philosophy. The deal is making the most out of auxiliary data structures in order to save time complexity (by sacrificing a bit of space complexity). These data structures will hold particular solutions that can be reused for obtaining bigger solutions.

Let's start with a basic example to see what I mean. You normally would implement Fibonacci's function as follows (considering n≥0 as precondition):

function Fibonacci (n: int): int
    if n equals 0
        return 0
    else if n equals 1
        return 1
    else
        return Fibonacci(n-1) + Fibonacci(n-2)

(Well, if you didn't know about it, reading the pseudocode above is pretty straightforward: "Fibonacci's function of 0 is 0, of 1 is 1, and of anything else above 1 is the sum of the calculations for the last two numbers)

And, well, it does the job... but when you start inputting n=40, n=80, and on... you start to notice the problem. It freaking gets stuck.

So, how to efficiently solve this problem? Let's see how it behaves. The following is a diagram on function calls for Fibonacci of 4:

All these calls stack on memory in depth. Notice that there tends to be a lot of unnecessary calls of stuff we've already calculated. The same will happen for bigger inputs, of course... So, yeah, that won't look pretty for our processor.

Now, analyzing the above behavior, we get the following recurrence equation that describes it:

T_n = T_n-1 + T_n-2 + O(C)

This is equivalent to a O(2ⁿ) time complexity, which totally sucks.

So, what to do with that? Well, the best thing we could possibly do is storing the result of a call somewhere and just accessing that result just when needed. That is basically what Dynamic Programming is about.

There are two methods to do this: Top-down Dynamic Programming (also known as Memoization) or Bottom-up Dynamic Programming (also known as Tabulation). I will explain Bottom-up below, as it is the easiest one for me to work with.

Bottom-up is my favorite. You start from the base case (the most trivial problem you can solve), and then you gradually go solving bigger cases, step by step, until you reach the problem you want to solve. For this case, the algotithm will be as follows:

function BottomUpDPFunction(<input>: <input type>): <output type>

    <create helper data structure>

    <store trivial problem's solution on the structure>

    for <i-th problem> from <first non-trivial problem's index> to <general problem's index>
        <solve i-th problem using the (i-1)-th problem in the data structure> 

    return <general problem's solution stored in the data structure>

Therefore, implementing Fibonacci's goes like this:

function FibonacciBottomUp(n: int): int {
    solutions = new array of size n+1, initialized with zeros
    solutions[0] = 0    // First trivial problem
    solutions[1] = 1    // Second trivial problem

    for i from 2 to n
        solutions[i] = solutions[i-1] + solutions[i-2]    // Solve current problem with previous solutions

    return solutions[n]
}

(Notice that because of array's index numbers, our i-th problem corresponds to the (i-1)-th position)

If we analyze it, we get a time complexity of O(n) !!! Isn't that cool!?  (Of course, we are sacrificing some additional memory; in this case we have a space complexity of O(n), which is not much of a problem anyway, but we have to be aware of that)

Please let me know what you think. If you have any suggestions or corrections, please tell me in the comments section below.

Thanks for reading!


[--EDIT--]


Adding here the Top-Down approach because this post feels incomplete without it:

function TopDownDPFunction(<input>: <input type>, <helper data structure>: <array or dictionary of types according to problem>): <output type>

    if <base case conditions>
        return <base case solution in helper data structure>

              else

                  if <helper data structure doesn't contain solution>
                      <store in helper data structure a solution that uses>: TopDownDPFunction(<reduced input>, <helper data structure>)

                  return <solution of the current problem found in the data structure>

So here is what the implementation would look like:

function FibonacciTopDown(n: int, solutions: array of int): int {
    if n equals 0 or n equals 1
        return solutions[n]

              else
                  if solutions[n] equals 0
                      solutions[n] = fibonacciTopDown(n-1, solutions) + fibonacciTopDown(n-2, solutions)
                  return solutions[n]

}

 And don't forget we need a wrapper function to run that
 

function Fibonacci(n: int): int {
    solutions = new array of size n+1, initialized with zeros
    solutions[0] = 0    // First trivial problem
    solutions[1] = 1    // Second trivial problem
    return FibonacciTopDown(n, solutions)

}

Hello World

Hello, my name is Juan C. Alvarez and this is my weblog. I am intending to use it sort of like a journal, and for sharing some interesting programming and software engineering contents or any cool findings on these topics. I will probably upload some random content such as food and places, or anything that comes into my mind that I feel that fits here and is worth sharing.

I suppose that's all. Have a great time all of you and take care. Remember to follow health and safety recommendations as for this date the infamous COVID19 is spreading fast. It is a serious matter.