Recursión en JavaScript

Problema

¿Cuántas formas de ordenarlos hay?

En la estantería hay 5 libros. ¿De cuántas formas puedes ordenarlos? Para el primer lugar hay 5 opciones, para el segundo 4, después 3, 2 y 1: 5 · 4 · 3 · 2 · 1 = 120. Esto es un factorial, y se escribe 5!.

Con un bucle ya sabes hacerlo:

function factorialLoop(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
}

console.log(factorialLoop(5));

Míralo también así: 5! = 5 · 4!. Y 4! = 4 · 3!. La tarea se resuelve mediante la misma tarea, solo que más pequeña. ¿Puede la función decir justo eso?

La idea

Una función que se llama a sí misma

Puede. Una función que se llama a sí misma se llama recursiva, y el enfoque es la recursión.

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

console.log(factorial(5));

Dos cosas hacen que funcione:

Un caso base. Un caso que se resuelve directamente, sin una llamada nueva. Aquí: 1! = 1.
Una tarea más pequeña. Cada llamada se llama a sí misma con un número más cerca del caso base: n - 1.

Míralo

La pila de llamadas

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

console.log(factorial(3));  // 6

Paso a paso, en palabras

El programa llama a factorial(3).
Memoria nueva para factorial con n = 3.
3 no es 1, así que la función llama a factorial(2) y espera la respuesta.
Lo mismo otra vez: factorial(2) llama a factorial(1). Cada llamada tiene su propio n.
n es 1: este es el caso base. Devuelve 1 sin volver a llamar.
La respuesta baja: 2 * 1 = 2.
Y otra vez: 3 * 2 = 6.
factorial(3) devuelve 6 y el programa lo imprime.

Cada llamada recibe su propia memoria con su propio n. Se apilan una encima de otra y esperan. Esta pila se llama pila de llamadas (call stack). Cuando el caso base devuelve 1, las respuestas bajan una a una y la pila se deshace.

Pruébalo

Bajar y volver a subir

¿Qué imprimirá el programa?

function steps(n) {
  if (n === 0) {
    return;
  }
  console.log(`bajo ${n}`);
  steps(n - 1);
  console.log(`subo ${n}`);
}

steps(2);

Respuesta

bajo 2
bajo 1
subo 1
subo 2

bajo 2
bajo 1
subo 2
subo 1

bajo 2
subo 2
bajo 1
subo 1

Pruébalo

Encuentra el error

sumTo(4) debería devolver 1 + 2 + 3 + 4 = 10. En cambio, el programa se detiene con RangeError: Maximum call stack size exceeded. ¿En qué línea está el error?

Elige la línea con el error.

La idea

¿Recursión o bucle?

El factorial se puede escribir con un bucle o con recursión. Aquí el bucle es la mejor opción: no acumula memoria por cada llamada, y para 100 000 llamadas la pila no alcanzará.

La recursión es natural donde algo contiene cosas más pequeñas del mismo tipo: una carpeta con carpetas dentro, una categoría con subcategorías, una rama con ramas. Te encontrarás con tareas así más adelante en el curso. Ahí un bucle se vuelve torpe, mientras que la función recursiva sigue siendo corta.

Más precisamente, para curiosos

El factorial se escribe a menudo con el caso base 0! = 1 (if (n === 0)). Así también funciona para 0.

En JavaScript todo número es decimal (double), y los enteros grandes se guardan de forma aproximada. Hasta 22! el resultado es exacto, pero 23! ya está redondeado. Para enteros exactos sin límite existe BigInt: un número con una n al final (23n):

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

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

console.log(factorial(23));
console.log(factorialBig(23n));

2.585201673888498e+22
25852016738884976640000n

Pruébalo

Ordena las líneas

La función tiene que calcular una potencia: power(2, 10) es 1024. Ordena sus líneas.

}
function power(base, exp) {
}
if (exp === 0) {
return base * power(base, exp - 1);
return 1;

Ejercicio

Tareas recursivas

1. Factorial de dos formas. Escribe factorialLoop(n) con un bucle for y factorial(n) con recursión. Lee un número e imprime el resultado de las dos funciones.

El factorial de 5 es 120
El factorial de 5 es 120

2. Suma de cifras. sumDigits(n): la última cifra (n % 10) más la suma de las cifras del resto (Math.trunc(n / 10)). El caso base es un número de una sola cifra.

3. Fibonacci. Cada número es la suma de los dos anteriores: 0, 1, 1, 2, 3, 5, 8… fib(n) devuelve el número n-ésimo. Pruébalo con 10, y después con 45. ¿Por qué es tan lento? Pista: ¿cuántas veces se calcula cada número?

4. Palíndromo. isPalindrome(s): la primera y la última letra son iguales, y el centro es un palíndromo. El caso base es una palabra de 0 o 1 letras.

sumDigits(2024)
fib(10)
isPalindrome("reconocer")
isPalindrome("ABCDE")

8
55
true
false

Test

Ponte a prueba

1. ¿Qué es la recursión?Dos funciones con el mismo nombreUn bucle dentro de una funciónUna función que se llama a sí misma

2. ¿Por qué una función recursiva necesita un caso base?Para que deje de llamarse a sí mismaPara que vaya más rápidoPara que pueda devolver un resultado

3. factorial(3) llama a factorial(2), y esta llama a factorial(1). ¿Cuántas variables n hay en memoria justo antes de que factorial(1) devuelva su resultado?NingunaTresUna

4. ¿Qué pasa si nunca se llega al caso base?La pila se desborda y el programa se detiene con RangeErrorEl programa se ejecuta sin fin, sin ningún errorLa función devuelve 0

Recursión

Cookies