Lecciones y el juego de aprendizaje

Recursión y retroceso

Funciones que se llaman a sí mismas, desde una cuenta regresiva hasta un solucionador de Sudoku, en una Raspberry Pi 4, con el límite real de profundidad del motor enseñado con honestidad.

El curso

Recursión y retroceso es un curso intermedio de Programación en siete lecciones, después de Python desde cero y Arregla el bug. La mayor parte corre en el montaje de la Pi con dos LEDs de la galería (rojo en GPIO17, amarillo en GPIO27), y el jefe usa el módulo de semáforo. Cada paso se verifica contra lo que la Pi imprime o lo que hacen sus pines, y cada número en las lecciones es uno que el programa realmente imprime.

  1. Llamadas que se llaman a sí mismas: una cuenta regresiva sin ciclo, la pila de llamadas dibujada como sangría mientras sube y baja, el factorial con enteros grandes exactos (25! completo), un triángulo de Sierpinski impreso como texto, y un LED parpadeando cinco veces por recursión.
  2. Casos base: una inmersión en cueva sin piso que desborda la pila, un caso base que la detiene, el límite de profundidad medido (un poco menos de 1,000 llamadas para una función pequeña), exponenciación por elevar al cuadrado (2^100 en 8 llamadas) y por qué una línea recta de trabajo pertenece a un ciclo.
  3. Tree walks: a cave of tunnels stored as nested tuples, printed as an outline, its 9 rooms counted, its deepest point found, a route to the glow worm grotto by depth-first search, then the Pi's own folders walked with the same pattern.
  4. Permutaciones: cada orden de una tripulación, n! contado hasta 720, una señal alienígena mezclada decodificada contra un conjunto de palabras, cargas del rover empacadas con el patrón incluir-o-saltar, y el resultado verificado contra itertools.permutations.
  5. Retroceso: N reinas con elegir, explorar, deshacer; cada solución contada del 4 al 8 (92 para el tablero de ajedrez); 15,720 casillas revisadas en lugar de 16 millones de tableros; el LED amarillo parpadeando en cada retroceso; y un laberinto de cueva marina del que se escapa.
  6. Memoización: las 21,891 llamadas del Fibonacci ingenuo para fib(20), un diccionario que las reduce a 39, functools.lru_cache con sus conteos de aciertos y fallos, 601,080,390 rutas del rover a través de una cuadrícula, y las 242 formas de hacer un dólar.
  7. Jefe: un solucionador de Sudoku: el final.

El gran final

El jefe construye un solucionador de Sudoku completo en unas veinte líneas. Carga un rompecabezas real, escribe las reglas como una función y la prueba en una casilla, luego resuelve la cuadrícula por retroceso: encuentra la primera casilla vacía, prueba cada dígito que quepa, resuelve el resto, y retira el dígito si eso falla. Una verificación independiente demuestra que cada fila, columna y caja contiene del 1 al 9 (4,208 colocaciones para este rompecabezas), los semáforos muestran ámbar mientras piensa y verde cuando está resuelto, y un guardián pone la luz en rojo para un rompecabezas que rompe las reglas antes de que el solucionador pierda un momento en él.

Qué hace distinto el motor de la Pi

La Pi corre MicroPython 1.29, no CPython, y la recursión es donde eso más se nota:

  • Una recursión demasiado profunda lanza RuntimeError: maximum recursion depth exceeded, o RuntimeError: pystack exhausted para una función con muchas variables locales. RecursionError, el nombre de CPython, no está definido aquí. Las lecciones atrapan RuntimeError, que funciona en ambos, porque el RecursionError de CPython es un tipo de RuntimeError.
  • El límite es la memoria de la pila, no una cuenta fija: unas 980 llamadas para una función diminuta, menos para una más grande. No existe sys.setrecursionlimit.
  • Los dicts no conservan el orden en que entraron las llaves, así que los árboles se guardan como listas y tuplas, y os.listdir y los conjuntos se ordenan antes de imprimir.
  • str.ljust y str.rjust faltan, así que el relleno se construye con " " * count. Los enteros no tienen límite de tamaño, igual que en CPython.

Todo lo demás del curso, functools.lru_cache, itertools y os, corre igual que en una Pi real.