Introducción
La recursión es un concepto muy potente de la programación que consiste en que una función se llame a sí misma.
Al principio puede resultar un poco complicado de entender, pero, una vez que comprendes los fundamentos, se convierte en una herramienta muy valiosa para resolver problemas complejos.
En este tutorial vamos a explorar la recursión en JavaScript con ejemplos fáciles de entender.
¿Qué es la recursión?
La recursión se produce cuando una función se llama a sí misma, ya sea de forma directa o indirecta.
Es parecida a un bucle, pero consiste en dividir un problema en subproblemas más pequeños y manejables.
Ejemplo 1: cuenta atrás
Empecemos con un ejemplo sencillo: una función de cuenta atrás.
function countdown(num) {
// Base case
if (num <= 0) {
console.log('Blastoff!');
return;
}
// Recursive case
console.log(num);
countdown(num - 1);
}
// Call the function
countdown(5);
En este ejemplo:
-
Caso base: cuando
num es menor o igual que 0, la función imprime «Blastoff!» y deja de llamarse a sí misma.
-
Caso recursivo: la función imprime el
num actual y se llama a sí misma con num - 1.
Ejemplo 2: el factorial
Ahora veamos un ejemplo clásico de recursión: calcular el factorial de un número.
function factorial(n) {
// Base case
if (n === 0 || n === 1) {
return 1;
}
// Recursive case
return n * factorial(n - 1);
}
// Test the function
console.log(factorial(5)); // Output: 120
En este ejemplo:
-
Caso base: cuando
n es 0 o 1, la función devuelve 1.
-
Caso recursivo: la función multiplica
n por el factorial de n - 1.
Conceptos clave
Caso base
Toda función recursiva debe tener al menos un caso base, una condición en la que la función deja de llamarse a sí misma.
Sin un caso base, la recursión continuaría indefinidamente y provocaría un desbordamiento de pila.
Caso recursivo
El caso recursivo define cómo la función se llama a sí misma con una versión más pequeña o más sencilla del problema.
Ventajas e inconvenientes de la recursión
Ventajas:
- Es una solución elegante para ciertos problemas.
- Imita el concepto de inducción matemática.
Inconvenientes:
- Puede ser menos eficiente que las soluciones iterativas.
- Puede provocar un desbordamiento de pila en recursiones profundas.
Conclusión
La recursión es una técnica muy valiosa que puede simplificar problemas complejos dividiéndolos en subproblemas más pequeños y manejables.
Entender los casos base y los casos recursivos es fundamental para implementar soluciones recursivas eficaces en JavaScript.
Para saber más:
Instrucciones
Llevas una pizzería y ofreces tres tipos de pizzas:
- Margherita: 7 $
- Caprese: 9 $
- Formaggio: 10 $
Si los clientes quieren, pueden añadir un número ilimitado de opciones extra: «ExtraSauce» por 1 $ o «ExtraToppings» por 2 $.
Tu tarea es escribir código que ayude al cliente a averiguar cuánto le cuesta.
Calcular el precio de una pizza
Dado el nombre de la pizza como primer argumento y un número ilimitado de opciones añadidas, calcula el precio de la pizza en dólares.
pizzaPrice('Margherita');
// => 7
pizzaPrice('Caprese', 'ExtraSauce', 'ExtraToppings');
// => 12
pizzaPrice(
'Caprese',
'ExtraToppings',
'ExtraToppings',
'ExtraToppings',
'ExtraToppings',
);
// => 17
Calcular el precio total de un pedido
Se llama a tu función con un array de PizzaOrders y debe devolver el precio total del pedido en dólares.
Cada PizzaOrder tiene una propiedad pizza, el nombre de la pizza, y una propiedad extras, el array de opciones extra.
const margherita = new PizzaOrder('Margherita');
const caprese = new PizzaOrder('Caprese', 'ExtraToppings');
orderPrice([margherita, caprese]);
// => 18
Te darás cuenta de que no puedes escribir esto usando recursión, ya que una prueba con una cantidad enorme de pedidos provocará un Maximum call stack size exceeded.
No te preocupes, es algo intencionado: ¡intenta implementar esta función usando un bucle imperativo!
Tienes muchas opciones, como usar reduce o un bucle for, entre otras.
Cuando el intérprete de JavaScript ejecuta el código de JavaScript, lleva un registro de las funciones a las que ha entrado (que ha empezado a llamar) en una estructura de datos llamada «una pila».
Cuando la función devuelve (termina), se elimina de la pila.
Sin embargo, esta pila tiene un tamaño limitado.
El error más común es una función recursiva que nunca termina.
Cada llamada se coloca en la pila, pero antes de que devuelva, se coloca otra llamada en la pila.
function kaboom() {
kaboom()
}
kaboom()
// => RangeError: Maximum call stack size exceeded
La traza de la pila de este error muestra la misma línea una y otra vez, lo cual tiene sentido, porque la función se llama a sí misma.
Aunque en la mayoría de los casos no tiene una aplicación práctica real, puedes averiguar hasta qué altura puede llegar esa pila.
let calls = 0;
function kaboom() {
calls +=1 ;
kaboom()
}
kaboom()
// => RangeError: Maximum call stack size exceeded
console.log(calls)
// => a number, generally higher than 10.000
Solo hay dos soluciones viables para un error de pila de llamadas causado por una función recursiva síncrona:
- asegurarte de que las funciones devuelvan antes de alcanzar el límite de la pila, normalmente añadiendo o corrigiendo un caso base.
- reescribir la función recursiva como un bucle imperativo, que ejecutará el cuerpo del bucle sin tener que entrar en una función y, por tanto, sin aumentar la pila.
Ejercicio de aprendizaje
