Recursividad y memorización en JavaScript

En este artículo, discutiremos cómo usar la programación recursiva, qué es y cómo optimizarla para usarla en algoritmos. Utilizaremos JavaScript como nuestro lenguaje de programación para comprender el concepto de recursividad.

¿Qué es la recursividad?

La recursividad es una técnica de programación que se utiliza para realizar una llamada a una función desde ella misma, de allí su nombre. El ejemplo más utilizado por su fácil comprensión es el cálculo de números factoriales. El factorial de 0 es, por definición, 1.

En el ejemplo a continuación, pasamos un número, lo duplicamos y luego pasamos ese valor nuevamente. En teoría, esto continuaría para siempre, pero debido a que las computadoras son limitadas, generalmente no podemos tener una recursión infinita. En general cuando la ejecución del programa se acaba el espacio del stack de llamadas obtenemos un error del tipo StackOverflow, a menos que pongamos una secuencia de control que salga de la recursividad. En el siguiente caso tan pronto como supere los 100:

const duplicar = num => {
  num = num + num;
  console.log(num);

  if (num > 100) return 'Salir'; // Si removemos esto, se acaba la memoria eventualmente.
  return double(num);
};

console.log(duplicar(4));

Bueno, “eso es genial y todo eso, pero ¿no puedo usar un bucle para hacer algo que pueda hacer la recursión?”. Pues sí, pero en realidad no. La recursión es útil cuando se trata de varios algoritmos de búsqueda y clasificación o al recorrer estructuras de datos que son más complicadas que las listas simples. Cuando se hace correctamente, también puede obtener un rendimiento mucho mejor, como O (log n) mientras que todos los bucles son O (n).

Memorización

No hay que usar la recursividad durante mucho tiempo para darse cuenta de que es bastante fácil alcanzar nuestros limites de procesamiento. Esto se debe a que la mayoría de las funciones recursivas son O(n^2) o incluso O(n!). Dado que JavaScript se ejecuta en pilas de llamadas cada vez que se agrega una nueva capa recursiva, se debe usar mucha memoria y potencia de procesamiento para administrarlo todo, a pesar de que la mayoría es redundante.

Probemos algo simple como generar una secuencia de fibonacci. Una secuencia de Fibonacci es donde cada dígito es la suma de los dos elementos anteriores, 0, 1, 1, 2, 3, 5, 8, 12 …

const fibonacci = num => {
  if (num < 2) return num;

  return fibonacci(num - 1) + fibonacci(num - 2);
};

for (let i = 0; i < 1000; i++) console.log(fibonacci(i));

Lo anterior, se acaba el stack de llamadas en aproximadamente 3 minutos.

Eso es simplemente horrible. Usar recursos para 1,000 capas de la misma información es demasiado, incluso para una computadora (o servidor) relativamente decente.

En cambio, podemos solucionar esto agregando una variable de almacenamiento, o un “memo”, que contendrá nuestros valores a medida que avanza la pila. Cada vez que se ejecuta nuestra función, su valor se agregará a su índice correspondiente en la nota y la siguiente capa se referirá a eso para calcular nuestro resultado.

const fibonacci = (num, memo) => {
  memo = memo || {};

  if (memo[num]) return memo[num];
  if (num < 2) return num;

  return memo[num] = fibonacci(num - 1, memo) + fibonacci(num - 2, memo);
};

for (let i = 0; i < 1000; i++) console.log(fibonacci(i));

Y así creamos una especie de caché en el código con una estructura de datos, que nos permite que la ejecución recursiva sea mucho mas veloz al no tener que recalcular toda la secuencia cada vez.

Conclusión

La recursión es una de esas cosas con las que debes sentirte muy cómodo porque volverá repetidamente o te perseguirá a lo largo de tu carrera de programación. Será esencial para aprender a recorrer árboles y listas y clasificar varios conjuntos de datos en el futuro.