Recursión

Mover una Torre de Hanói de 64 discos lleva 18 446 744 073 709 551 615 movimientos; una función recursiva describe la solución en cuatro líneas.

Una función que se llama a sí misma

Algunos problemas contienen una copia más pequeña de sí mismos. El factorial de 5, que se escribe 5!, es 5 × 4 × 3 × 2 × 1 = 120. Míralo otra vez: es 5 × (4 × 3 × 2 × 1), es decir, 5 × 4!. En general n! = n × (n − 1)!, así que para calcular un factorial puedes calcular un factorial más pequeño y multiplicar. Una función que resuelve un problema llamándose a sí misma con una versión más pequeña es recursiva.

function factorial(n) {
  if (n <= 1) return 1;          // caso base: aquí se para
  return n * factorial(n - 1);   // caso recursivo: un problema más pequeño
}
console.log(factorial(5)); // 120

Toda función recursiva necesita dos partes. El caso base es una entrada lo bastante pequeña para responderla directamente, sin otra llamada: aquí, el factorial de 1 es 1. El caso recursivo reduce el problema y vuelve a llamar a la función. Cada llamada debe acercarse al caso base. Si no lo hace, por ejemplo si escribieras factorial(n + 1) por error, las llamadas no terminan nunca.

La pila de llamadas

¿Cómo lleva la cuenta la computadora de todas esas llamadas sin terminar? Cuando se ejecuta factorial(5), llega a 5 * factorial(4) y tiene que esperar la respuesta. La computadora pone la llamada que espera en una pila, un montón donde lo último que se pone es lo primero que se saca. factorial(4) espera a factorial(3), y así hasta factorial(1), que devuelve 1 de inmediato. Entonces la pila se deshace: factorial(2) devuelve 2, factorial(3) devuelve 6, factorial(4) devuelve 24 y factorial(5) devuelve 120.

La pila tiene un tamaño limitado. Una recursión que nunca llega a su caso base sigue agregando llamadas hasta que se acaba el espacio, y JavaScript se detiene con un error; en Chrome y Node.js el mensaje es "RangeError: Maximum call stack size exceeded". Ese mismo límite hace que una recursión muy profunda, de cientos de miles de niveles, sea mejor escribirla como un bucle.

La Torre de Hanói

La Torre de Hanói es un rompecabezas que publicó el matemático francés Édouard Lucas en 1883. Hay tres varillas y una pila de discos de distintos tamaños en la primera varilla, con el más grande abajo. El objetivo es mover toda la pila a la tercera varilla. Solo se puede mover un disco cada vez, solo el disco de arriba de una varilla, y nunca se puede poner un disco más grande sobre uno más pequeño.

Pensar paso a paso adónde va cada disco se vuelve confuso enseguida. Pensar de forma recursiva lo hace corto. Para mover n discos de A a C: primero quita del camino los n − 1 discos de arriba, de A a B. Luego mueve el disco más grande de A a C. Luego mueve los n − 1 discos de B encima de él, en C. Mover n − 1 discos es el mismo rompecabezas, un tamaño más pequeño, y mover un disco es el caso base. Para 3 discos esto da 7 movimientos; el laboratorio muestra la pila de llamadas que esperan en cada movimiento.

function hanoi(n, from, to, via) {
  if (n === 0) return;
  hanoi(n - 1, from, via, to);
  console.log("disk " + n + ": " + from + " -> " + to);
  hanoi(n - 1, via, to, from);
}
hanoi(3, "A", "C", "B");  // 7 movimientos

¿Cuántos movimientos llevan n discos? Mover n discos cuesta dos movimientos de n − 1 discos más uno: M(n) = 2M(n − 1) + 1, con M(1) = 1. Eso da 1, 3, 7, 15, 31, así que M(n) = 2ⁿ − 1, y ninguna solución puede usar menos. Diez discos llevan 1023 movimientos. Sesenta y cuatro discos llevan 2⁶⁴ − 1 = 18 446 744 073 709 551 615 movimientos; a un movimiento por segundo son unos 585 mil millones de años. Este es el crecimiento O(2ⁿ) de la unidad anterior.

Recursión, bucles y trabajo repetido

Todo lo que se escribe con recursión se puede escribir con un bucle y una pila propia, y los casos sencillos como el factorial a menudo quedan más claros como bucles. La recursión brilla cuando el propio problema tiene forma de árbol: dividir una lista en el ordenamiento por mezcla, explorar carpetas dentro de carpetas o buscar en un laberinto, que es el tema de la última unidad. Una trampa es el trabajo repetido. Los números de Fibonacci 0, 1, 1, 2, 3, 5, 8, … siguen fib(n) = fib(n − 1) + fib(n − 2). Escrito directamente como recursión, fib(10) = 55 hace 177 llamadas, fib(20) hace 21 891 y fib(30) hace 2 692 537, porque los mismos valores más pequeños se calculan una y otra vez. Recordar las respuestas ya encontradas, o construir desde abajo con un bucle, elimina ese desperdicio.