"Para entender recursión, uno primero debes entender recursión" - Desconocido

Si eres como yo entonces probablemente no entendiste recursión la primera vez que leíste acerca de ella.

Para mí, fue porque:

  1. Recursión en sí misma, es un concepto difícil.
  2. Algunos de los tutoriales y artículos que leí no eran muy claros.

Por alguna razón, la mayoría de los artículos que explicaban recursión usaban el ejemplo de números factoriales y la secuencia de Fibonacci. Lo que significaba que tenía que entender como los números de Fibonacci funcionaban para después hacer la conexión a recursión.

Pero, vamos a tomar otro camino en este artículo.

¿Qué es recursión?

En términos simples: recursión es cuando una función sigue llamándose a sí misma, hasta que ya no tiene que hacerlo.

¿Qué? Si, la función se sigue llamándose a sí misma, pero con una entrada más pequeña cada vez.

Piensa en recursión como una carrera en un circuito. Es como correr la misma pista una y otra vez, pero las vueltas se hacen más pequeñas cada vez. Eventualmente, correrás la vuelta más pequeña y se terminará la carrera.

Lo mismo con la recursión: La función sigue llamándose a sí misma, cada vez con una entrada menor hasta que eventualmente se detiene.

Pero, la función no decide por sí misma cuando parar. Nosotros le decimos cuando. Nosotros le damos a la función una condición conocida como caso base.

El caso base es la condición que le dice a la función cuando dejar de llamarse a sí misma. Es como decirle a la función cuál será la última vuelta de la carrera para que se detenga después de la última vuelta.

Ejemplos de recursión

Muy bien eso es recursión. Vamos a mirar algunos ejemplos para entender como funciona la recursión.

¿Recuerdas la primera vez que aprendiste acerca de los bucles (loops)? El primer ejemplo que hiciste probablemente fue un programa que hacia una regresiva. Vamos a hacer eso.

Primero, necesitamos entender que queremos que haga nuestro programa. Cuenta regresiva desde un número dado hasta el número más pequeño, restando 1 cada vez que pasa por el bucle.

Dado el número 5, esperamos que la salida sea algo así:

// 5
// 4
// 3
// 2
// 1

Muy bien, ¿Cómo podemos programar este programa con recursión?

let cuentaAtras = numero => {
    //base case
    if (numero === 0) {
        return;
    }
    console.log(numero);
    return cuentaAtras(numero - 1);
};
console.log(cuentaAtras(5)) // 5, 4, 3, 2, 1

¿Qué exactamente es lo que pasa aquí?

Si te diste cuenta, lo primero que hicimos fue definir el caso base. ¿Por qué? Porque la función primero que nada necesita saber cuándo dejará de llamarse a sí misma.

¿Nunca correrías una carrera sin saber primero que tan larga es, o si?

Si no le dices a la función cuándo detenerse, entonces sucederá algo llamado stackoverflow. La pila(stack) se va a llenar con funciones que se están llamando, pero que no regresan ni se quitan de la pila.

La parte de recursión sucede en la línea 7. Donde le decimos a la función que siga regresando, pero reduciendo sus entradas una cada vez que regresa.

Así que, efectivamente, esto es  lo que sucede:

1// La entrada actual es 5
2// Es 5 igual a 0 ?
3// No, Ok entonces imprime 5 en la consola.
4// Se llama asi misma de nuevo con el numero - 1 O 5 - 1;
5// La entrada principal es 4
6// Es 4 igual a 0 ?
7// No, Ok entonces imprime 4 en la consola.
8// Repite hasta que la entrada sea 0, y asi la función deja de llamarse a si misma.

Vale, eso tiene sentido. Vamos con otro ejemplo.

¿Sabes cómo podemos saber que un número es par usando el operador de residuo(%)? Entonces, si cualquier número % 2 == 0 entonces ese número es par o si cualquier número % 3 == 0 entonces ese número es impar.

Bueno, resulta que existe otro método.

Si continuamente restamos dos a un número hasta que el número más pequeño sea 0(cero) o 1(uno) entonces podemos saber si el número es par o impar.

Intentemos eso con recursión. Entonces, dado el número 6, nuestro programa debería devolver 'Par' porque 6-2-2-2 = 0. Dado 7, nuestro programa debería devolver 'impar' porque 7-2-2-2 = 1.

Veamos el código.

let parImpar = (numero) => {
    if (numero === 0) {
        return 'Par';
    } else if (numero === 1) {
        return 'Impar';
    } else {
        return parImpar(numero - 2);
    }
};
console.log(parImpar(20)) // Par
console.log(parImpar(75)) // Impar
console.log(parImpar(98)) // Par
console.log(parImpar(113)) // Impar

De nuevo, el primer paso fue decirle a la función cuándo dejar de llamarse a sí misma. Luego le dijimos qué hacer cuando se llama a sí misma.

Recursión es básicamente divide y conquista. Seguimos dividiendo el problema haciéndolo cada vez más pequeño.

Recursión vs Bucles

Cuando se trata de velocidad, un bucle se ejecuta mucho más rápido que una función recursiva. También es más fácil escribir un bucle que una función recursiva. Y cuando se trata de legibilidad, es más fácil saber qué sucede con un bucle que con una función recursiva.

Pero, las funciones recursivas son muy elegantes.

Entonces, ¿Cuál es la mejor opción? ¿Eficiencia o velocidad?

Esta es una frase del libro Eloquent Javascript.

Preocuparse por la eficiencia puede ser una distracción. Es otro factor más que complica el diseño del programa, y ​​cuando estás haciendo algo que ya es difícil, esa cosa extra de la que preocuparte puede ser paralizante. Por lo tanto, empieza siempre por escribir algo que sea correcto y fácil de entender. Si te preocupa que sea demasiado lento, que normalmente no lo es, ya que la mayoría del código simplemente no se ejecuta con la frecuencia suficiente para llevar una cantidad significativa de tiempo, puedes medirlo después y mejorarlo si es necesario.

En este punto te preguntarás, porque alguien elegiría escribir una función recursiva en vez de un bucle. Si los bucles son mucho más sencillos, ¿verdad?

Bueno, eso es cierto - pero hay algunos problemas que son más fáciles de resolver con recursión. Si deseas explorar uno de esos problemas, considera leer el capítulo 3 de Eloquent JavaScript.

Ahora que has descubierto un nuevo superpoder, pongámoslo en práctica.

Realiza los siguientes ejercicios utilizando recursión. Si crees que puedes asumir más, puedes resolver los famosos problemas factorial y secuencia de Fibonacci.

Ejercicios

Si te gustaría ponerte un reto, considera resolver los siguientes ejercicios.

  1. Escribe un programa que invierta una cadena usando recursión. Dada la cadena "freeCodeCamp", el programa debería devolver "pmaCedoCeerf".
  2. Escribe un programa que devuelva el número de veces que aparece una letra en una cadena. Tu programa debería recibir una cadena y la letra.
    let programa = (cadena, letra) => {...}
    Después, debe devolver el número de veces que la letra aparece en la cadena. Dado el texto "JavaScript" y la letra  "a", su programa debe devolver 2.‌‌‌‌
    Pista: Intenta averiguar cuándo quieres que la función deje de llamarse a sí misma y cómo devolver una versión más pequeña del problema cada vez que la función se llama a sí misma.

Eso es todo por ahora. Espero te haya servido para entender recursión un poco más.‌‌

Traducido del artículo de Joel P Mugalu - How to Understand Recursion in JavaScript