Teoría: Recursividad

La recursión en la programación es cuando una función se llama a sí misma. En matemáticas, muchas funciones se definen de esta manera, por lo que la mayoría de los lenguajes de programación adoptan este enfoque. JavaScript no es una excepción: al definir una función, puedes usar no solo los datos definidos anteriormente, sino también llamar a la función definida dentro del cuerpo de la función. Se ve así:

const f = () => {
  f();
};

Esta llamada se ejecutará infinitamente y puede parecer que no tiene sentido. Intentemos comprender la recursión con un ejemplo más cotidiano. Supongamos que tienes tres libros en un estante y quieres saber cuántas combinaciones posibles hay para su permutación.

Obtendrías seis combinaciones únicas de tres libros. Con cuatro libros, tendrías 24 combinaciones. Con trece libros, tendrías casi tantas combinaciones como personas en el planeta. ¿25 libros? Habría más combinaciones de permutación que átomos en el cuerpo humano.

En general, hay n! combinaciones de permutación de n libros. El factorial significa multiplicar todos los números enteros desde 1 hasta n. Entonces, 3! es 1 * 2 * 3. Escribamos una función factorial.

const factorial = (n) => {
  return 1 * 2 * 3 * 4; //
}

Algo no está bien aquí. No conocemos el valor de n inicialmente, ahí radica el problema. En matemáticas, conocemos dos condiciones para definir recursivamente el factorial: si n es igual a 0, entonces el factorial es 1, eso es simple. Pero si n no es igual a 0, entonces el factorial es n*(n-1)!

Intentemos esto:

const factorial = (n) => {
  if (n === 0) {
    return 1;
  }
  else {
    return n * factorial(n - 1);
  }
}

const answer = factorial(3);

Esto puede parecer extraño. Estamos llamando a una función desde dentro de la función, pero... ¡es la misma función! Todo se debe a que una función en sí misma no es una caja, es su descripción. La caja se crea solo cuando se llama a la función, y una vez que se completa, la caja se autodestruye. Entonces, cuando llamas a la misma función desde dentro de sí misma, simplemente se crea otra caja.

Sigamos esto: llamamos a factorial(3). 3 no es igual a 0, por lo que se ignora la primera condición. La función intenta realizar la multiplicación y devolver la respuesta, pero no puede hacerlo, necesita conocer el segundo número, por lo que llama a factorial(3 - 1) o factorial(2).

Se crea otra caja factorial idéntica, toma el número 2, que tampoco es 0, por lo que intenta realizar la multiplicación y devolver la respuesta, pero no puede hacerlo, necesita conocer el segundo número, por lo que llama a factorial(1).

Se crea otra caja factorial idéntica, toma el número 1 y nuevamente no es 0. Otro intento de multiplicación y devolución del resultado, se llama a factorial(0) y esta caja puede devolver instantáneamente la respuesta, que es 1.

El 1 se devuelve a la caja anterior, se multiplica por 1 y se devuelve "1" a la caja anterior, se multiplica por 2 y se devuelve "2" a la caja anterior, se multiplica por 3 y se devuelve "6" al mundo exterior y se guarda en la constante answer. ¡Voilà!

Todo esto es recursión: algo se describe a través de sí mismo, se contiene a sí mismo en su descripción. Cuando se trata de matemáticas o programación, se requieren dos condiciones:

1. Un caso base o escenario terminal simple. Es el punto en el que debemos detenernos. En nuestro ejemplo, es 0: detuvimos el cálculo del factorial cuando se pasó un 0 a la función.
2. Una regla para avanzar en la recursión, una profundización. En nuestro caso, fue n * factorial(n - 1).

Otro detalle. Si verificas nuestro código con un linter, mostrará un error no-else-return. Sigamos las recomendaciones del linter y refactoricemos el código:

const factorial = (n) => {
  if (n === 0) {
    return 1;
  }
  return n * factorial(n - 1);
};

const answer = factorial(3);

Repasemos los pasos nuevamente, pero desde una perspectiva diferente, sin mirar dentro de las cajas. Así es como se ve paso a paso:

factorial(3);
3 * factorial(2);
3 * 2 * factorial(1);
3 * 2 * 1 * factorial(0);
3 * 2 * 1 * 1;
3 * 2 * 1
3 * 2;
6;

La multiplicación no ocurre mientras descendemos hasta el caso base de la función factorial(0). Y luego volvemos hacia arriba, realizando una multiplicación en cada paso.

La recursión se utiliza ampliamente, especialmente en la programación funcional, como se mencionó anteriormente. Y no solo para cálculos matemáticos, ¡sino para muchos otros procesos!

A veces, la información en una computadora requiere funciones recursivas por su naturaleza. Por ejemplo, las páginas web están compuestas por elementos HTML, y algunos elementos pueden estar dentro de otros. Etiquetas dentro de etiquetas dentro de etiquetas. Y para procesar eficientemente una página, el navegador necesita moverse recursivamente de nivel en nivel para comprender cómo mostrar estos elementos en la pantalla para el usuario.

Te encontrarás constantemente con la recursión en este y los siguientes cursos, porque es increíblemente poderosa.