Recursividad y recursividad de cola en javascript

La recursividad es uno de los temas que todo el mundo cubre, sin importar qué lenguaje de programación esté aprendiendo. Probablemente en las primeras clases de cualquier curso para principiantes. Aún así, muchas personas luchan por entenderlo. Esta publicación cubre qué es la recursividad, qué observar al escribir una función recursiva. Además, hay una sección sobre una recursividad de cola, una versión un poco más optimizada de la recursividad.

¿Qué es la recursividad?

Una definición de recursividad comúnmente utilizada es que es una función que se invoca a sí misma. Pero ¿qué significa eso? Por lo general, escribe la función y luego la llama. Con recursividad, dentro del cuerpo de la función, también lo llama.

function funcionRecursiva() {
    // codigo
    funcionRecursiva();
}

Al mirar el fragmento sobre, podría pensar que se trata de un bucle infinito. ¿Qué pasa con el desbordamiento de pila? Y usted tiene razón. Al escribir recursividad, debe prestar especial atención al caso final. Pero hay un poco más sobre ese a continuación. Primero, responda a la otra pregunta que podría hacer.

¿Cuando y por qué usar recursividad?

Hay diferentes casos de uso y cada uno tiene su propia opinión. Creo que son excelentes cuando necesitas hacer un bucle en algo, pero no sabes cuántas veces. Extracción larga del servidor, donde está obteniendo datos siempre que haya algunos. Además, atravesar el árbol, como los nodos HTML y los nodos de árboles binarios.

Rompiendo la recursividad

Como se mencionó anteriormente, el caso final siempre debe cubrirse. Ese es el momento en el que detienes la recursividad. De lo contrario, obtienes un bucle infinito. Solo por ejemplo, digamos que necesitamos calcular el factorial de un número. Si no sabe qué es factorial, hay una explicación sencilla en la página de Wikipedia. Además, para simplificar, supongamos que el argumento siempre es un valor válido.

function factorial(numero) {
    if(numero === 1) {
        return numero;
    } else {
        return numero * factorial(numero - 1);
    }
}

factorial(5); // 120

Para calcular el factorial, suma todos los números hasta llegar a uno. Ese es también el caso final de nuestra recursividad, y es por eso que una vez que alcanzamos el valor uno, ya no llamamos a la función factorial.

Recursión de cola

La recursividad de cola es un tipo de función recursiva cuando lo último que se ejecuta es una llamada recursiva. No significa mucho, lo sé. Pero simplificado, es una recursividad más optimizada. Entonces, para explicarlo mejor, vuelvo al ejemplo anterior. Esa no es una recursividad de cola, y se ejecuta de la siguiente manera.

factorial(5); // paso 1
5 * factorial(4); // paso 2
5 * 4 * factorial(3); // paso 3
5 * 4 * 3 * factorial(2); // paso 4
5 * 4 * 3 * 2 * factorial(1); // paso 5
5 * 4 * 3 * 2 * 1; // paso 6

Como puede ver arriba, primero se ejecuta cada llamada factorial. Solo entonces multiplica todo el número. Para convertirlo en recursividad de cola, estoy cambiando la función para aceptar el resultado como un segundo parámetro.

function recursividadDeCola(numero, resultado = 1) {
    if(numero === 1) {
        return resultado;
    } else {
        return recursividadDeCola(numero - 1, resultado * numero);
    }
}

recursividadDeCola(5); // 120

En este caso, la función se ejecuta en los siguientes pasos.

Paso 1: tailRecursiveFactorial(5, 1)
Paso 2: tailRecursiveFactorial(4, 5)
Paso 3: tailRecursiveFactorial(3, 20)
Paso 4: tailRecursiveFactorial(2, 60)
Paso 5: tailRecursiveFactorial(1, 120)

Este tipo requiere menos operaciones y necesita menos elementos en una pila, lo que significa una ejecución más eficaz.