Recursión o Recursividad
Esta semana toca recursividad (🤘) que es uno de mis temas favoritos (😎).
Qué es recursividad?
La recursividad es una característica de algunos procesos u objetos que hacen referencia a sí mismos en su definición.
¿Qué queremos decir con esto? Primero, que la recursividad o recursión (las dos son correctas) no son una “cosa”, sino una “característica” de una cosa. Existen series recursivas, algoritmos recursivos, funciones recursivas… Así mismo, no hay una sintaxis especial o palabra clave para indicar que una función es recursiva, si no que simplemente es una forma de describir funciones que tienen la característica de que como parte del cuerpo de la función, encontramos una o más invocaciones a sí misma.
Un ejemplo de recursividad fácil de visualizar son los fractales, como el triángulo de Sierpinski (ver gif de arriba), que son objetos geométricos cuya estructura básica se repite a diferentes escalas. En el caso del triángulo de Sierpinski, partimos de una regla sencilla: dado un triángulo, dibujamos 3 triángulos nuevos, con lados de longitudes la mitad que el primero y organizados de una manera particular, como podemos ver en el gif. La recursividad se da en que volvemos a aplicar la misma regla a cada uno de los triángulos producidos, y así sucesivamente.
En código, omitiendo mucho detalle, podríamos expresar esta lógica con una función más o menos así:
const dibujaTriangulo = () => {
// dibuja triángulo principal
// ... dibujaTriangulo(); // dibuja triángulo de la derecha
dibujaTriangulo(); // dibuja triángulo de arriba
dibujaTriangulo(); // dibuja triángulo de la izquierda
}dibujaTriangulo(); // invocación para iniciar la acción
Como podemos ver, cada invocación a dibujarTriangulo() va a resultar en tres invocaciones más a la misma función, y cada una de ellas hará también tres invocaciones, y así sucesivamente… ad infinitum. En el mundo real, las funciones recursivas usan algún tipo de condición para saber cuando terminar. Continuando con el ejemplo (que pueden ver terminado acá), nuestra implementación va a usar un par de variables (max y depth) para limitar la “profundidad”, o el número de veces que vamos a dejar que se repita el proceso.
const dibujaTriangulo = (max, depth) => {
// dibuja triángulo principal
// ... if (!depth) {
depth = 0;
} if (depth >= max) {
return; // terminamos!
} dibujaTriangulo(max, depth + 1); // dibuja triángulo de la dcha
dibujaTriangulo(max, depth + 1); // dibuja triángulo de arriba
dibujaTriangulo(max, depth + 1); // dibuja triángulo de la izqda
}dibujaTriangulo(5);
Nuestra nueva versión de dibujaTriangulo() ya no continúa hasta el infinito, sino que ahora espera un argumento (max) con el que indicamos cuantas veces queremos repetir el proceso.
Recursión como abstracción
Como programadores, siempre estamos tratando de encontrar abstracciones que nos permitan evitar la repetición explicita. Por eso, cuando vemos en nuestro código que algo se repite varias veces, siempre nos planteamos refactorizar para “abstraer” ese pedacito que se repite en una variable, una función, clase, bucle, … para poder reusarlo (♻︎).
La recursión nos ofrece una forma de pensar y organizar procesos repetitivos, al igual que los bucles. De hecho todo algoritmo recursivo puede implementarse usando iteración. La recursión, a través del uso de funciones, nos permite abstraer y representar ciclos repetitivos de una forma alternativa a la iteración. Por ejemplo:
const imprimeElementos = (arr) => {
for (var i = 0; i < arr.length; i++) {
console.log(arr[i]);
}
}imprimeElementos([1, 2, 3, 4]);
El código de arriba recibe un array e imprime todos sus valores en la consola, uno a uno, usando un bucle for. La misma lógica se puede expresar de forma recursiva:
const imprimeElementos = (arr) => {
if (arr.length > 0) {
console.log(arr.shift());
return imprimeElementos(arr);
}
};imprimeElementos([1, 2, 3, 4]);
La nueva versión de imprimeElementos() produce el mismo resultado, pero en vez de usar un bucle, usa recursión para recorrer el arreglo.
Ejemplos
Ahora que ya hemos visto, en líneas generales, qué significa la recursión, veamos algunos ejemplos un poco más reales. De hecho, como desarrolladores web, hay una estructura en particular con la que nos encontramos a diario, donde la recursión va a ser una herramienta esencial: el DOM.
Recorrer el árbol del DOM
El DOM (Document Object Model) es la representación en memoria de un documento HTML, con una interfaz programática (API) que nos permite interactuar con él. El DOM es una estructura conocida como “árbol”, donde partiendo de un “tronco”, cada elemento o nodo puede contener a otros nodos y así sucesivamente.
Para “recorrer” este tipo de estructura, donde no sabemos la “profundidad” (los niveles de anidación), y donde cada elemento es “similar” (con las mismas características), una función recursiva es la ruta más obvia. Imaginemos que tenemos que implementar una función que dada una condición, a comprobar para cada nodo, retorna un arreglo con todos los nodos que cumplan la condición:
const select = (element, condition) => {
let found = []; if (condition(element)) {
found.push(element);
} for (let i = 0; i < element.children.length; i++) {
found = found.concat(select(element.children[i], condition));
} return found;
};
Una vez implementada nuestra función select() , podríamos invocarla así:
const selection = select(
document.body,
element => element.tagName === 'H2'
);Como vemos, al invocar select(), nuestra condición se va a comprobar para el elemento “raíz”, y de ahí vamos a continuar invocando select() para cada uno de los “hijos” del elemento, y así sucesivamente. Cada invocación retorna un arreglo con los nodos que cumplen la condición. En el ejemplo de arriba, la variable selection va a ser un arreglo con todos los elementos <h2> encontrados.
Recorrer el sistema de archivos (file system)
Otro ejemplo común de estructura recursiva es el sistema de archivos de una computadora, donde un directorio (folder) puede contener archivos y/o directorios, y así sucesivamente.
Para este ejemplo vamos a usar Node.js, que nos permite interactuar con el sistema de archivos a través de los módulos fs y path. Sé que todavía no hemos visto este tipo de cosas en Node.js, pero les dejo el ejemplo para que puedan estudiarlo y de paso investigar un poquito sobre Node.js y como interactuar con el sistema de archivos:
const Fs = require('fs');
const Path = require('path');const traverseSync = dir => ({
path: dir,
children: Fs.readdirSync(dir).map(file => {
const path = Path.join(dir, file);
return Fs.lstatSync(path).isDirectory()
? traverseSync(path)
: { path };
})
});
El ejemplo de traverseSync() crea un objeto, con una propiedad “path” y otra “children”, donde children va contener un arreglo con todos los “hijos” (archivos y subcarpetas) que van a ser a su vez objetos con la misma estructura (con path y children). De esta forma, nuestro código va a recorrer los “hijos” (children) e invocar traverseSync() para cada uno de ellos, y así ir recorriendo la estructura completa.
Limitaciones
Imaginemos la siguiente función:
const foo = () => foo();Si invocamos la función foo() de arriba, veremos que resulta en un error: “Maximum call stack size exceeded”. Esto se debe a que cada invocación de foo() resulta en otra invocación a sí misma, la cual va a invocarse a sí misma otra vez, y no hay ninguna condición que termine la recursión. Cada vez que invocamos una función, JavaScript va a añadir un elemento al “call stack” y el tamaño de éste tiene limitaciones según la memoria que nuestro intérprete pueda asignar. Por ello, llega un momento en que JavaScript agota el tamaño máximo permitido del call stack. El “call stack” es una pila que JavaScript usa para saber dónde está en la ejecución de un script que invoca multiples funciones — qué función está ejecutándose actualmente, qué funciones se invocan desde la función actual, qué función debe ejecutarse después, etc.
Tail Call Optimisation
Existen técnicas de “optimización de llamada de cola” (Tail Call Optimisation) diseñadas para mitigar esta limitación. En este artículo no vamos a entrar en detalles, pero para las curiosas cabe mencionar una técnica conocida como “trampolining”, y además el hecho de que ES6 implementa Tail Call Optimisation, lo que significa que el intérprete es capaz de identificar llamadas recursivas y optimizar su ejecución evitando consumir el call stack.
Ejercicios
- Implementa una función que retorne un string con todas las letras del alfabeto. Implementar dos versiones, una iterativa y otra recursiva.
- Implementa una función que dados dos argumentos (
baseyexponente) calcula la potencia de la base elevada al exponente. Básicamente, nuestra función tiene que hacer lo mismo queMath.pow(), y tener un “firma” así:int potencia( int base, int exponente ). Implementar dos versiones, una iterativa y otra recursiva. - Escribe una función recursiva que dado un número entero
nretorne un arreglo con todos los números enteros en orden decreciente desdena1. La firma de la función debe ser:array countdown( int n ). Ejemplos:
a)countdown(1)retorna[1]
b)countdown(5)retorna[5, 4, 3, 2, 1]
Resumen
- La recursividad es una característica de algunos procesos u objetos que hacen referencia a sí mismos en su definición.
- Las funciones recursivas se invocan a sí mismas en el cuerpo de la función.
- La recursión se puede usar para abstraer repetición y expresar iteración a través de funciones.
- Las funciones recursivas son útiles para “recorrer” estructuras anidadas, como árboles.
- La recursión está limitada por el tamaño máximo que soporte nuestro call stack.
