Teoría: Proceso iterativo

La recursión se puede utilizar de diferentes maneras: la que estábamos discutiendo en la lección anterior se llama proceso recursivo. Este tema será más comprensible si ya has entendido el tema anterior y has completado el ejercicio. Otra forma de utilizar la recursión en el código se llama proceso iterativo. El nombre puede ser confuso: tanto el proceso recursivo como el iterativo describen la recursión.

¿Recuerdas las secuencias de llamadas del último curso? Cada nueva instancia, o caja de la función factorial(), espera que la siguiente instancia devuelva algún valor. No se realiza ningún cálculo hasta que lleguemos al final, al caso base. Solo entonces obtendremos 1 y comenzaremos a realizar multiplicaciones en orden inverso: 1 multiplicado por 2 es 2, luego 3 multiplicado por 2 es 6.

Con el factorial de 3 no hay problemas, pero imagina que necesitas el factorial de 100. El programa requeriría almacenar en memoria una gran cantidad de números debido a la postergación de todas las operaciones de multiplicación. Postergar aquí es la palabra clave: la esencia del proceso recursivo es postergar los cálculos hasta el final. Nada se multiplicará hasta que el proceso llegue al caso base, y si se detiene, el programa no sabrá nada y no obtendrás información útil, ya que no le permitirías completar la tarea. Un proceso recursivo es como una persona que realiza todo el trabajo de la semana el viernes después del almuerzo.

Toda esta información sobre los cálculos se llama estado. Todo lo que tu programa recuerda en un momento específico es el estado: cálculos, constantes, funciones. Y muy a menudo, el estado es la causa de diversos problemas en la programación.

Dejar todo para el mediodía del viernes no es la mejor manera de trabajar. Un método mejor es hacer un poco el lunes, un poco más el martes y así sucesivamente. Esto es un proceso iterativo: cuando el trabajo se distribuye uniformemente durante toda la semana.

Vamos a escribir la misma función factorial utilizando un proceso iterativo. La idea es no postergar las multiplicaciones, sino multiplicar dos números de inmediato y pasar el resultado al siguiente paso.

Aquí está el código.

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

  const iter = (counter, acc) => {
    if (counter === 1) {
      return acc;
    }
    return iter(counter - 1, counter * acc);
  };

  return iter(n, 1);
};

Como puedes ver, todo esto ya no parece una fórmula matemática para el factorial. Y no se parece a la función del proceso recursivo del último curso. Esto suele ser así: el código para un proceso recursivo es más fácil de leer y entender porque está más cerca de la idea. Pero no es tan eficiente. El proceso iterativo es mucho más eficiente, pero es más complicado.

La función factorial contiene otra función. Recuerda, las definiciones de funciones no son las cajas en sí, sino solo sus descripciones. La función interna iter() toma dos argumentos: counter y accumulator. counter rastrea el movimiento desde n hasta 1. Y accumulator es el resultado actual de multiplicar los números de n a 1. Si counter llega a 1, se devuelve accumulator — en este momento será igual a la respuesta final.

Después de que la función está definida, nos queda una sola línea en la función factorial: devolver el resultado de llamar a la función iter() con n y 1 como argumentos.

Vamos a ejecutar factorial(3). La única línea que realmente se ejecuta en la función factorial es return iter(n, 1). Quiere devolver y salir, pero necesita obtener un valor de la función iter().

Se crea una caja iter(). Toma 3 y 1. Dentro de la caja iter, 3 es conocido como counter, y 1 como acc. El valor de counter no es igual a 1, por lo que la primera condición no se cumple. Luego quiere hacer un retorno, pero necesita obtener un valor de una nueva instancia de iter().

Esta es la parte más importante: se llama a una nueva caja con counter reducido en 1, porque hemos avanzado un paso, y accumulator fue multiplicado por counter.

Se crea una nueva caja iter(). Toma 2 y 3: counter y accumulator. counter no es igual a 1, por lo que intenta devolver el valor, pero no puede — necesita obtener un valor de una nueva instancia de iter(), llamada con 2 - 1 como primer argumento, y 2 * 3 como segundo. No hemos terminado, pero hemos realizado una multiplicación útil — 2 * 3 es una de las multiplicaciones necesarias para encontrar 3.

Se crea una nueva caja iter(). Toma 1 y 6. Ahora, la primera condición se cumple, así que esta caja simplemente devuelve accumulator, que es el número 6.

Luego, el valor 6 se filtra hacia la primera caja iter(), luego hacia la caja factorial, y finalmente se devuelve como respuesta.

Así es como se ven los cálculos paso a paso.

iter(3, 1); // iter(3 - 1, 3 * 1);
iter(2, 3); // iter(2 - 1, 2 * 3);
iter(1, 6); // counter === 1, return 6
6;

En cualquier momento, el programa necesita recordar el estado, pero su tamaño siempre es constante: solo dos números.

Un proceso iterativo similar puede describirse de la siguiente manera:

1. Establecer el estado inicial. En nuestro caso, realizamos la primera llamada a iter() con n y 1. Este es el estado inicial.
2. Verificar el escenario terminal. Verificamos si counter no es igual a 1 y detenemos la recursión cuando toma el valor 1.
3. Establecer un nuevo estado. Esto es cómo el proceso avanza. En nuestro caso, realizamos otra llamada a iter() con counter disminuido y accumulator multiplicado. Estos dos nuevos números definen un nuevo estado.
4. Repetir el paso 2.

Y este proceso se repite hasta que llega al escenario terminal.

Resumamos brevemente.

1. Recursividad — es cuando algo se contiene a sí mismo en su descripción.
2. Proceso recursivo — es un proceso de cálculo con cálculos diferidos.
3. Proceso iterativo — es un proceso de cálculo en el cual el estado puede describirse con una cantidad fija de valores.

Nota que la condición en la función iter() no incluye una rama else. Por lo tanto, si la condición (counter === 1) no se cumple, se procede a la siguiente línea y se ejecuta return iter(counter - 1, counter * acc).

const iter = (counter, acc) => {
  if (counter === 1) {
    return acc;
  }
  return iter(counter - 1, counter * acc);
};

Esto funciona porque cuando se ejecuta la instrucción return, la instancia de la función devuelve el valor y desaparece. No sucede nada más después de que se ejecuta return.

Por lo tanto, cuando se cumple la condición, se ejecuta return acc, y el segundo retorno ya no ocurre.

Aquí tienes otro ejemplo:

const someFunction = (a) => {
  return 100;
  return a;
  return 4123123;
};

Correcto. Esta función siempre devolverá 100. Las otras dos instrucciones de retorno nunca se ejecutarán porque la instancia de la función se destruye después de ejecutar el primer retorno. Solo puede haber un retorno en cualquier instancia específica de una función.

Conclusiones

Vamos a llamar a la función del último curso:

factorial(3);           // nada sucede, calculamos los factores
3 * factorial(2);       // nada sucede, calculamos los factores
3 * 2 * factorial(1);   // nada sucede, calculamos los factores
3 * 2 * 1;              // finalmente empezamos la multiplicación
3 * 2;
6;

El proceso de cálculo que crea esta función se llama proceso recursivo. La idea principal es posponer el cálculo hasta el final.

Toda la información sobre los cálculos, todo lo que el programa recuerda en cualquier momento (cálculos, constantes, funciones), se llama estado. Muchos problemas en programación surgen de la necesidad de manejar el estado.

La esencia del proceso iterativo es el cálculo con una cantidad fija de estados.

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

  const iter = (counter, acc) => {
    if (counter === 1) {
      return acc;
    }
    return iter(counter - 1, counter * acc);
  };

  return iter(n, 1);
};