Saltar al contenido
Portada » Recursividad y pila

Recursividad y pila

Vamos a repasar como podemos implementar recursividad en Javascript. La recursividad se define en programación cuando una función se llama a sí misma. Uno de los puntos clave de las funciones recursivas es establecer un punto de parada o corte de forma adecuada, de manera que las llamadas recursivas no se vuelvan infinitas.

Enfoque iterativo vs recursivo

Estos dos enfoques representan una manera de pensar a la hora de construir un algoritmo. Para entenderlo de la mejor forma vamos a hacerlo a través de un ejemplo, la función potencia.

pow(2, 2) = 4

Para implementar el algoritmo de la función potencia podemos enfocarlo a través de los dos enfoques de la siguiente forma.

Solución iterativa

function pow(x, n) {
  let resultado = 1;

  // multiplica el resultado por x n veces en el bucle
  for (let j = 0; j < n; j++) 
  {
    resultado *= x;
  }

  return resultado;
}

alert( pow(2, 4) ); // 16

Solución recursiva

function pow(k, i) 
{
  if (i == 1)
  {
    return k;
  } 
  else 
  {
    return k * pow(k, i - 1);
  }
}

alert( pow(2, 4) ); // 16

Cuando se ejecuta la llamada recursiva la ejecución se divide en dos ramas. La recursión reduce la llamada a la función de una forma más simple y así sucesivamente, hasta que el resultado final sea el caso de parada.

Una de las características fundamentales de las soluciones recursivas es que suelen ser más pequeñas en código respecto a las iterativas.

La profundidad máxima de recursión en Javascript está limitada por el propio motor de ejecución.

Contexto de ejecución y pila en recursividad

Vamos a revisar como funcionan internamente las llamadas recursivas.

La información sobre el proceso de ejecución de una función se almacena en el contexto de ejecución. El contexto de ejecución es una estructura de datos interna que contiene los detalles de la ejecución de una función: donde está el control de flujo actual, variables actuales, etc.

Cada llamada a una función tiene un único contexto de ejecución asociado.

Cuando se hace una llamada anidada dentro de una función ocurre lo siguiente:

  • La función actual queda pausada.
  • El contexto asociado a la función pausada queda almacenado en una estructura de datos especial llamada la pila de contextos en ejecución.
  • Se ejecuta la llamada anidada.
  • Cuando termina la ejecución, el antiguo contexto se devuelve de la pila, la función “padre” continúa su ejecución desde donde paró.

Más recursos JS

PrototypeAñadir propiedades de forma dinámica a un objeto
toLocaleStringHerramienta esencial para el formateo de fechas y números en aplicaciones internacionales
Recursividad y pilaUso de recursividad y funcionamiento de la pila JS
DesestructuraciónMecanismo para desempaquetar arrays y objetos
Manejo de StringsManejo básico de Strings, cadenas de caracteres
OperadoresUso de operadores de comparación y lógicos
PromesasGestión de peticiones asíncronas con promesas
SleepImplementación de la función sleep() en JS
ThisUso de la palabra reservada this en diferentes contextos
MapsTe enseñamos cuando usar Map y cuando Object con ejemplos
Switchery JSLibrería para modificar el estilo de los checkbox
Mejores libros Javascript EspañolEncuentra los mejores libros para aprender JS y convertirte en el desarrollador más demandado.
Exception JSManejo de excepciones en Javascript, control de errores y flujo de programa.
Obfuscator JavascriptProtege tu código Javascript Ofuscándolo
Javascript desde ceroAprende los conceptos básicos de Javascript, ponte en marcha.
LodashLodash hace que la manipulación de datos en JavaScript sea más fácil y menos propensa a errores
Formatdate JSFormateo y trabajo con fechas en javascript de forma sencilla.
DayjsBiblioteca para la gestión de fechas
padStartManeja cadenas de texto con la función padStart()