Introducción
La recursión es un concepto potente en programación que consiste en que una función se llame a sí misma.
Puede ser un poco difícil de entender al principio, pero una vez que comprendes los fundamentos, se convierte en una herramienta muy valiosa para resolver problemas complejos.
En este tutorial exploraremos la recursión en JavaScript con ejemplos fáciles de entender.
¿Qué es la recursión?
La recursión ocurre cuando una función se llama a sí misma, ya sea de forma directa o indirecta.
Es similar a un bucle, pero implica dividir un problema en subproblemas más pequeños y manejables.
Ejemplo 1: Cuenta regresiva
Empecemos con un ejemplo sencillo: una función de cuenta regresiva.
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: 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, lo que 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 y desventajas de la recursión
Ventajas:
- Solución elegante para ciertos problemas.
- Imita el concepto de inducción matemática.
Desventajas:
- 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 valiosa que puede simplificar problemas complejos al dividirlos 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.
Aprende más:
Instrucciones
Tienes una pizzería y ofreces tres tipos de pizza:
- Margherita: $7
- Caprese: $9
- Formaggio: $10
Si los clientes quieren, pueden agregar una cantidad ilimitada de opciones extra: ya sea «ExtraSauce» por $1 o «ExtraToppings» por $2.
Tu tarea es escribir código que ayude al cliente a calcular cuánto le costará.
Calcula el precio de una pizza
Recibes el nombre de la pizza como primer argumento y una cantidad ilimitada de opciones adicionales; calcula el precio de la pizza en dólares.
pizzaPrice('Margherita');
// => 7
pizzaPrice('Caprese', 'ExtraSauce', 'ExtraToppings');
// => 12
pizzaPrice(
'Caprese',
'ExtraToppings',
'ExtraToppings',
'ExtraToppings',
'ExtraToppings',
);
// => 17
Calcula el precio total de un pedido
Tu función se llama con una lista de PizzaOrders y debe devolver el precio total del pedido en dólares.
Cada PizzaOrder tiene una propiedad pizza, que es el nombre de la pizza, y una propiedad extras, que es la lista 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 lanzará un Maximum call stack size exceeded.
No te preocupes, esto es intencional: ¡intenta implementar esta función usando un bucle imperativo!
Tienes muchas opciones, como, entre otras, usar reduce o un bucle for.
Cuando el intérprete de JavaScript ejecuta el código JavaScript, lleva un registro de las funciones en las que ha entrado (que ha empezado a llamar) en una estructura de datos llamada «pila».
Cuando la función retorna (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 retorne, 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 qué tan alta puede llegar a ser 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:
- asegúrate de que las funciones retornen antes de que se alcance el límite de la pila, normalmente agregando o corrigiendo un caso base.
- reescribe la función recursiva como un bucle imperativo, que ejecutará el cuerpo del bucle sin tener que entrar en una función, y así sin aumentar la pila.
Ejercicio de aprendizaje
