Programación Funcional en JavaScript: La recursividad

10728808896_120654cb09_b.jpg

Una rama arrancada de un árbol no deja de ser un nuevo árbol, un nuevo ser idéntico pero de menor tamaño con sus hojas como última alternativa posible.

Seguimos hablando sobre el control de flujo en programación funcional con JavaScript. Si en el anterior post hablamos de cómo intentar hacer un menor uso de estructuras iterativas manuales para realizar ciertas acciones, en esta ocasión vamos a hablar de una técnica muy recurrente en programación funcional y que para muchos lenguajes de programación funcionales puros es la única forma de iterar: hablamos de la recursividad.

Una técnica que nos permitirá pensar en la solución de problemas complejos de una forma diferente. Veremos también en que nos puede ayudar a día de hoy la recursividad y cómo puede ser aplicada. Empecemos:

¿Qué es la recursividad?

La recursividad es la técnica que utilizamos en programación para solucionar problema complejos que pueden dividirse en partes más pequeñas e idénticas al problema total pero de menor magnitud. La composición de todas las soluciones hijas dan el resultado de la solución padre.

La recursividad es bastante peculiar porque suele funcionar autoejecutando funciones con un ámbito menos al problema padre. Es por eso que en toda solución recursiva contamos con 2 elementos:

  • Un caso base: es el caso al que toda función recursiva tiene que acabar llegando para dar por resuelto el caso más simple del problema que queremos resolver. Si no definimos un caso base dentro de nuestra solución recursiva llamaremos a nuestra función infinitas veces hasta que acabemos con todos los recursos del sistema.
  • Un caso recursivo: Que suele ser una función que es capaz de autoinvocarse. La clave de esta autoinvocación es que los elementos que le pasemos tendrán que ser menores que los del problema padre ya que si no nunca podríamos llegar al caso base.

Iteración y recursión en JavaScript

La recursividad es una técnica muy usada en programación funcional porque nos evita el uso de iteraciones. Muchos lenguajes de programación funcional no cuentan ni con sintaxis para realizar bucles. Simplemente pueden recorrer arrays por medio de recursividad.

Para ver la diferencia entre ambos modelos, vamos a presentar un problema muy simple que pueda resolverse con ambas técnicas: la idea es realizar un algoritmo que sea capaz de sumar todos los número enteros de un array.

La solución iterativa es muy sencilla y muy tonta:

const nums = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
let acc = 0;
for (let i = 0; i < nums.length; i++) {
    acc += nums[i];
}
acc; // 45

Este ejemplo ya lo podíamos simplificar usando a nuestro nuevo amigo ‘reduce’:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9].reduce((acc, index) => acc + index, 0); // 45

Y la solución recursiva sería de la siguiente manera:

1. function sum(nums) {
2.    if (nums.length === 0) {
3.        return 0;
4.    } else {
5.        const [first, ...rest] = nums;
6.        return first + sum(rest);
7.    }
8. }

sum([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]); // 45

Estudiemos un poco el código:

  • En la línea número 2 estamos definiendo el caso base de nuestro problema. Queremos que cuando el array sea vacío, la función devuelve un cero.
  • La línea 6 se encarga de mostrar el caso recursivo. Lo que hacemos es volver a invocar la propia función ‘sum’ con una peculiaridad, hemos sacado el primer elemento del array.
  • Esto lo hemos hecho con una nueva funcionalidad que tenemos en JavaScript (gracias a ES6) llamada ‘asignación por desestructuración‘. La línea 5 nos permite ver de qué forma tan fácil podemos extraer el primer elemento y el resto. Pura magia.
  • En la línea 6 estamos haciendo el return de la función sumando el valor.

Para que veamos mejor como se ejecuta, si hiciesemos una ejecución línea podríamos observar algo parecido a esto:

1 + sum([2, 3, 4, 5, 6, 7, 8, 9])
1 + 2 + sum([3, 4, 5, 6, 7, 8, 9])
1 + 2 + 3 + sum([4, 5, 6, 7, 8, 9])
1 + 2 + 3 + 4 + sum([5, 6, 7, 8, 9])
1 + 2 + 3 + 4 + 5 + sum([6, 7, 8, 9])
1 + 2 + 3 + 4 + 5 + 6 + sum([7, 8, 9])
1 + 2 + 3 + 4 + 5 + 6 + 7 + sum([8, 9])
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + sum([9])
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + sum([])
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 0
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9
1 + 2 + 3 + 4 + 5 + 6 + 7 + 17
1 + 2 + 3 + 4 + 5 + 6 + 24
1 + 2 + 3 + 4 + 5 + 30
1 + 2 + 3 + 4 + 35
1 + 2 + 3 + 39
1 + 2 + 42
1 + 44
45

Como podéis imaginar, la recursividad es una técnica que consume un mayor número de recursos del computador. Es por eso que mucha gente llega a criticarlo. Sin embargo, estudiaremos en el futuro técnicas que nos ayuden a optimizar este tipo de algoritmos.

¿Para qué nos es útil la recursividad?

La recursividad es una técnica que se lleva muy bien con estructuras de datos que partan de un nodo raíz y del que vayan colgando diferentes nodos hijos. Las estructuras de datos en forma de árbol son idóneos para recorrer y hacer tomas de decisión por medio de recursividad.

Existen algoritmos específicos como son el backtracking o la búsqueda con poda que se basan en la recursividad.

En nuestro mundo, siendo por lo general frontenders los que usamos JavaScript, encontramos una estructura en forma de árbol muy conocida: El DOM. No es de extrañar por tanto que la programación funcional, JavaScript y el DOM se puedan llevar tan bien con la recursividad.

La recursividad es un buen método para criptografía. Trabajar con árboles que van generando claves dinámicas es una buena forma de practicar la recursividad.

Conclusión

Quizá no empecemos a usar la recursividad para solucionar todos los problemas del mundo. Pero si es una técnica a tener en cuenta ya que nos ayuda a dividir problemas complejos en casos más simples.

Como veremos en el futuro, librerías como ReactJS se basan en aplicar el paradigma funcional a la capa de interfaz y cómo vimos, no están muy desencaminados en su acercamiento viendo lo bien que se lleva la recursividad con el recorrido de árboles como lo son los nodos del DOM de nuestra aplicación.

La recursividad siempre atrae críticas y escepticismo por la cantidad de recursos que necesitas para llegar a una solución que podría obtenerse por medios menos costosos, pero no os preocupeis porque intentaremos remediarlo por medio de técnicas de optimización en el futuro.

Por ahora, será mejor que nos quedemos con el concepto. Os animo a que practiquéis la recursividad por vosotros solos ya que es un concepto que se aprende fácil de forma teórica, pero que cuesta asimilar cuando queremos ponerlo en práctica en un problema real.

Esto es todo amigos. Nos leemos 🙂

Anteriores posts de Programación Funcional en JavaScript:

Introducción

  1. La Programación Funcional en JavaScript
  2. Programación Funcional en JavaScript: Los Objetos
  3. Programación Funcional en JavaScript: Las funciones

El control de flujo funcional

  1. La programación Funcional en JavaScript: Los métodos funcionales
  2. La programación Funcional en JavaScript: La recursividad

Imagen portada | flickr

Anuncios

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