Recursión

La recursión se puede definir en pocas palabras como, una función que se llama a si misma. De esta manera, se va llamando la función a si misma, cambiando los parámetros, hasta llegar a un punto de corte, donde la función empieza a retornar un valor. Uno de los ejemplos más triviales y también la causa de que que la recursión se atribuya solo a ámbitos matemáticos, es el factorial.

const factorial = n => {
  if (n < 2) return 1
  return n * factorial(n - 1)
}
// inline
const factorial n => n < 2 ? 1 : n * factorial(n - 1)

Pero, la verdad, es que la recursión es una elegante, y muchas veces la única, manera de resolver problemas iterativos. Esta es el eje central de la FP. Inclusive podemos verla en la definición de lamba. Además, en lenguajes más puros y estrictos como Haskell o Erlang no cuentan con las palabras reservadas while ni for. Por lo que el concepto de loop es ajeno a ellos, pero no la iteración.

Uno de los usos donde la recursión es la única solución al problema, es donde no tenemos manera de conocer el final de la estructura que recorremos. Como por ejemplo, árboles, grafos y streams. Y problemas que involucran estas estructuras, como recorrido de caminos, backtracking, toma de decisiones, ordenamiento. U otras estructuras no tan primitivas, como es el caso de los arrays en JS, que para optimizar los tiempos de búsqueda y los llamados a métodos, utilizan árboles para ordenar los elementos.

Ejemplos

Como buenos ejemplos, tenemos los algoritmos de ordenamiento pertenecientes a «divide y vencerás». Los muy conocidos Quick Sort y Merge Sort son algoritmos con enfoque recursivos. Uno un poco más rápido que el otro en casos triviales, pero el otro está pensado para estructuras donde el acceso aleatorio sea costoso

function quicksort (lista) {
  if (lista.length === 0) return []
  return [
    ...quicksort(lista.slice(1).filter(x => x < lista[0])),
    lista[0],
    ...quicksort(lista.slice(1).filter(x => x >= lista[0]))
  ]
}

function mergesort (lista) {
  if (lista.length < 2) return lista
  const mitad = parseInt(lista.length / 2)
  let izq = lista.slice(0, mitad)
  let der = lista.slice(mitad)
  return merge( mergesort(izq), mergesort(der) )
}

function merge (izq, der) {
  if (!izq.length) return der
  if (!der.length) return izq
  return (izq[0] < der[0])
    ? [ izq[0], ...merge(izq.slice(1), der) ]
    : [ der[0], ...merge(izq, der.slice(1)) ]
}

Un ejemplo más complejo, es la permutación con repetición de una secuencia de caracteres, utilizando Vue para facilitarnos la reactividad. Y una implementación de map

const map = (func, iterable) => (!iterable.length)
  ? iterable
  : [ func(iterable[0]), ...map(func, iterable.slice(1)) ]

 

Call Stack y Tail Call Optimization

Al principio, expusimos una definición de factorial. Con ella explicaremos algo importante para las ejecuciones recursivas. El Call Stack o pila de llamados. Cada vez que se llama a una función, la ejecución de la función anterior se detiene en orden de obtener el resultado de la nueva función invocada. Esto puede ocasionar que operaciones simples deban esperar el retorno de la función antes de ser evaluadas. Pero no es el único problema que nos puede generar, ya que la mayoría de los lenguajes no funcionales, prevén un límite a su pila de llamadas. En el caso de JS, depende de cada motor, pero node, que utiliza V8 de Google, tiene un limite cercano a las 10000 funciones en la pila.

factorial(4)
4 * factorial(3)
4 * ( 3 * factorial(2) )
4 * ( 3 * ( 2 * factorial(1) ) )
4 * ( 3 * ( 2 * 1 ) )
4 * ( 3 * 2 )
4 * 6
24

Podemos ver como a medida avanza la recursión, se van apilando los llamados, ya que operaciones simples como la multiplicación deben esperar al retorno completo para poder ser evaluadas. Pero haciendo un pequeño cambio en nuestra definición de factorial y moviendo las operaciones simples para que no dependan del retorno, vemos un cambio en el orden de las llamadas.

const factorial = (n, acc = 1) => {
  if (n < 2) return acc
  return factorial(n - 1, n * acc)
}

Como va llevando el resultado acumulado hasta el final de la pila, la operación se realiza antes de entrar en otro nivel de recursión. Y, si nuestro lenguaje es un lenguaje compilado, puede detectar que al llegar al final de la recursión, el resultado ya fue calculado y solo esta devolviéndose, por lo que omite el camino completo de vuelta a la pila, y retorna el valor

factorial(4, 1)
factorial(3, 4)
factorial(2, 12)
factorial(1, 24)
24

Esto se conoce como Tail Call Optimization, tail-recursion o tail-end recursion. Implica agregarle una complejidad extra a nuestro código pero el resultado es mucho más veloz y eficiente.

Conclusión

A medida que avanzan las revisiones de ECMAScript, cada vez se exponen métodos y estructuras que se acercan a los lenguajes funcionales. En las últimas versiones se busca implementar estructuras de tipo iterable, con el fin de unificar un método para recorrerlas de manera recursiva y métodos que se basen en iteradores e iterables. Por lo que la recursión va estar intrínsecamente ligada al futuro de JS.

Y, como pudimos apreciar en los ejemplos, la recursión no es realmente compleja, y su desempeño puede ser apenas menor que los bucles en muchos casos. A veces solo requiere un poco de nuestra atención para mejorar los tiempos computacionales y reducir la pila de llamado.

Comparte este artículo

Entra en la discusión y deja tu comentario

Veces