Considero que antes de empezar a entender la recursividad es importante comprender otros conceptos:
- Pila o Stack. Un rápido repaso, una pila o stack es una estructura de datos que sigue el principio de First In - Last out (FILO). Como analogía: se comporta como si apilaras un montón de hojas (de ahí su nombre de pila). Ejemplo: Tienes 10 hojas desordenadas, decides meterlas dentro de una caja de una en una, la primer hoja que metes a la caja quedará hasta el fondo y no podrá ser recuperada a menos que hayas sacado todas las hojas que estén arriba de ella, de ahí el acrónimo FILO: Lo primero en entrar será lo último en salir.
- Condicionales. Otro rápido repaso, se reduce a decidir entre varías acciones según se cumpla o no una condición, conocidas también como if statements y pertenecientes al tipo de estructuras de control, ya que manejan como se comporta el flujo del código.
- Bucles. Estructura de control encargada de iterar sobre el código según una condicional, una vez cumplida se rompe el bucle y continúa con el código.
Ahora bien, ¿Qué es la recursividad?
Consiste en llamar a una función dentro de sí misma una y otra vez (caso recursivo) hasta que cumpla con una condición (caso base), resulta muy parecida a los bucles, con una diferencia crucial: Se comporta como una pila. Analicemos el siguiente código:
function contar(n) {
if (n === 0) return; // Caso Base
contar(n - 1); // Caso Recursivo
console.log(n);
}
Tenemos la función contar(n), recibe como parametro "n", que asumiermos por conveniencia siempre sera uno del tipo 'number'. Como se puede observar en los comentarios tenemos el "Caso Base", if(n === 0) return;, aquel que interrumpe la acción se necesita que "n" sea igual a 0 tanto en tipo de dato como en su contenido (comparación estricta), después nos encontramos con el 'Caso Recursivo', contar(n - 1), la función se llama a si misma pero decrementando "n" en 1, en otras palabras es la parte de código que permite la recursividad, finalmente se puede observar un console.log(n), una mera impresión de consola para observar el decremento, en este caso, conteo.
Supongamos que llamamos la función contar con valor de n = 3.
Flujo de código:
Primera Iteración.
if ( 3 === 0 ) return; // No se cumple el caso base por lo que continúa al caso recursivo.
contar(3- 1); // Se lleva a cabo el caso recursivo pero ahora la función lleva valor de 2.
console.log(3); // No se imprime todavía, ya que entro en recursión (First In).
Segunda Iteración.
if ( 2 === 0 ) return; // No se cumple el caso base
contar(2- 1); // Se lleva a cabo el caso recursivo pero ahora la función lleva valor de 1.
console.log(2); // Imprime 2 una vez acabe la recursividad.
Tercera Iteración.
if ( 1 === 0 ) return; // No se cumple el caso base
contar(1- 1); // Se lleva a cabo el caso recursivo pero ahora la función lleva valor de 0.
console.log(1); // Imprime 1 una vez acabe la recursividad (Last in)
Cuarta Iteración.
if ( 0 === 0 ) return; // Se cumple el caso base
contar(0); // YA NO CONTINUA
console.log(0); // YA NO CONTINUA
Empieza la recursión, va resolviendo sus iteraciones de atras hacía delante, como una pila.
En la tercera iteración se imprime 1 (primera en ser resuelta), en la segunda se imprime 2 (segunda en ser resuelta), en la primera se imprime 3 (última en ser resuelta).
