Desmitificando la recursión: Algoritmos en JavaScript

La recursión, un concepto que para muchos programadores representa un verdadero desafío cognitivo, es en realidad una herramienta esencial en la caja de herramientas de un desarrollador JavaScript. La recursión se refiere a la técnica en la cual una función se llama a sí misma directa o indirectamente y es especialmente útil para resolver problemas que pueden dividirse en subproblemas de naturaleza similar. En este extenso viaje, vamos a desglosar la recursión, presentar variados ejemplos y brindar la visión necesaria para entender y aplicar esta técnica con destreza y precisión en varios algoritmos.

Representación Abstracta de Llamadas de Funciones Recursivas

Comprendiendo la base de la recursión

La recursión se basa en dos conceptos principales: el caso base y el caso recursivo. El caso base actúa como un ancla, deteniendo la recursión, mientras que el caso recursivo es donde la función realiza su llamada a sí misma. Para visualizar esto, imagine que está parado frente a una pila de cajas. Su objetivo es llegar al fondo de esta pila. La acción de quitar la caja superior es análoga a hacer una llamada recursiva, y el momento en que alcanza la caja inferior, donde no hay más cajas que quitar, se asemeja al caso base.

Ejemplo introductorio: El factorial

Una de las maneras más sencillas de entender la recursión es a través del ejemplo del cálculo del factorial de un número. El factorial de un número n (denotado como n!) es el producto de todos los enteros positivos desde 1 hasta n. Matemáticamente, se define de manera recursiva como n! = n * (n-1)!, con el caso base siendo 0! = 1.

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

En el ejemplo anterior, `factorial(n)` se llama a sí misma con `n – 1`, lo que eventualmente lleva al caso base `n === 0`. Este es un ejemplo clásico donde la recursión brilla por su elegancia y simplicidad.

Recursión y sus casos de uso en algoritmos

Más allá de los ejemplos didácticos como el factorial, la recursión es útil en una amplia gama de algoritmos, incluyendo aquellos que manejan estructuras de datos jerárquicas como los árboles y los grafos. Algoritmos de búsqueda y recorrido, como la búsqueda en profundidad (DFS) y la búsqueda en anchura (BFS), se implementan de manera más natural y legible mediante el uso de la recursión.

Trabajando con árboles: Recorrido en preorden

Considere un árbol binario, una estructura de datos en la cual cada nodo tiene a lo sumo dos hijos. El recorrido en preorden es una estrategia donde visitamos primero la raíz del árbol, luego el subárbol izquierdo de manera recursiva, y finalmente el subárbol derecho también de manera recursiva.

function preorden(nodo) {
  if (nodo !== null) {
    console.log(nodo.valor);
    preorden(nodo.izquierdo);
    preorden(nodo.derecho);
  }
}

En el fragmento de código anterior, `preorden(nodo)` gestiona la recursión ejecutándose así misma primero con el hijo izquierdo del nodo actual y luego con el derecho, estableciendo las bases para navegar por toda la estructura del árbol.

Manejando listas enlazadas

Las listas enlazadas son otra estructura de datos esencial que se beneficia de la recursión. Consideremos una lista enlazada simple, donde cada elemento apunta al siguiente. Podemos utilizar la recursión para invertir la lista, cambiando las referencias de manera que el último elemento se convierta en el primero.

function invertirLista(nodo) {
  if (nodo === null || nodo.siguiente === null) {
    return nodo;
  }
  let resto = invertirLista(nodo.siguiente);
  nodo.siguiente.siguiente = nodo;
  nodo.siguiente = null;
  return resto;
}

Aquí `invertirLista(nodo)` utiliza el caso base cuando se llega al final de la lista y luego trabaja hacia atrás, reorientando cada nodo hacia el anterior hasta que la lista completa se ha invertido.

Recursión y división y conquista

La estrategia de división y conquista consiste en dividir un problema en subproblemas más pequeños, resolver estos subproblemas de manera independiente y luego combinar las soluciones para resolver el problema general. La recursión es un ingrediente natural en este enfoque, como se evidencia en algoritmos de ordenamiento como QuickSort y MergeSort.

MergeSort: Un ejemplo práctico

MergeSort divide el arreglo a ordenar en dos mitades, ordena cada mitad de manera recursiva y luego une las mitades ordenadas en un nuevo arreglo ordenado. La recursión se utiliza tanto para dividir el arreglo como para realizar la operación de mezcla de manera eficiente.

function mergeSort(arreglo) {
  if (arreglo.length <= 1) {
    return arreglo;
  }
  const mitad = Math.floor(arreglo.length / 2);
  const izquierda = arreglo.slice(0, mitad);
  const derecha = arreglo.slice(mitad);
  return merge(
    mergeSort(izquierda),
    mergeSort(derecha)
  );
}

function merge(izquierda, derecha) {
  // Implementación de la función de mezcla
}

Cada llamada a `mergeSort()` sigue subdividiendo el arreglo hasta llegar a arreglos de un solo elemento (el caso base). Luego, en cada retorno de la pila de llamadas, los arreglos se combinan mediante `merge()`, resultando en un nuevo arreglo ordenado que es una combinación de los dos subarreglos ordenados previamente.

Te puede interesar

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *