Lección 17 · 17 de 20

Recursividad y memoización · Python

Funciones recursivas en Python para recorrer un árbol de carpetas, y memoización con un diccionario para contar las formas de pagar un importe.

Python · Recursividad y memoización en DMarlon Studio: el código del ejemplo y su salida en la terminal

Una función recursiva se llama a sí misma con un problema más pequeño. Toda recursión necesita un caso base, que se resuelve sin volver a llamarse. En size(item), si el elemento no es un diccionario es un archivo y se devuelve su tamaño; si es una carpeta, se suma size() de cada cosa que contiene, y cada una de esas llamadas baja un nivel más.

show(folder, depth=0) también es recursiva: escribe cada nombre con dos espacios por nivel de profundidad y, si encuentra una carpeta, se llama con depth + 1. La recursión encaja con los datos que tienen forma de árbol (carpetas, menús, organigramas, JSON), donde no se sabe de antemano cuántos niveles hay.

ways_to_pay(amount, coins) cuenta de cuántas maneras se puede pagar un importe con unas monedas. En cada paso hay dos caminos: usar una moneda coins[0] (y queda menos por pagar) o descartarla para siempre (coins[1:]). Los casos base son importe cero (una forma, ya está pagado) e importe negativo o sin monedas (ninguna).

Sin más, esa función repetiría millones de veces los mismos subproblemas. La memoización guarda cada respuesta en memo con la clave (amount, coins) y, si vuelve a aparecer, la reutiliza. Con solo 238 casos guardados obtiene las 4562 formas de pagar 1 euro. Es lo mismo que hace @lru_cache automáticamente.

Python limita la profundidad de la recursión (unas 1000 llamadas anidadas). Para estructuras muy profundas, un bucle con una pila propia es más seguro.

Código · main.py

project = {                               # folders are dicts, files are KB    "README.md": 4,    "src": {"main.py": 12, "utils": {"dates.py": 3, "money.py": 5}},    "docs": {"manual.pdf": 820, "img": {"logo.png": 64}},}def size(item):    if not isinstance(item, dict):        # base case: a plain file        return item    return sum(size(child) for child in item.values())   # calls itselfdef show(folder, depth=0):    for name, item in folder.items():        print("  " * depth + f"{name} ({size(item)} KB)")        if isinstance(item, dict):            show(item, depth + 1)         # one level deepermemo = {}def ways_to_pay(amount, coins):           # amount in cents    if amount == 0:        return 1    if amount < 0 or not coins:        return 0    key = (amount, coins)    if key not in memo:                   # work out each case only once        use_it = ways_to_pay(amount - coins[0], coins)   # pay one coins[0]        skip_it = ways_to_pay(amount, coins[1:])         # never use it        memo[key] = use_it + skip_it    return memo[key]show(project)print("Ways to pay 1 EUR:", ways_to_pay(100, (50, 20, 10, 5, 2, 1)))print("Cases remembered:", len(memo))

Salida · python3 main.py

README.md (4 KB)
src (20 KB)
  main.py (12 KB)
  utils (8 KB)
    dates.py (3 KB)
    money.py (5 KB)
docs (884 KB)
  manual.pdf (820 KB)
  img (64 KB)
    logo.png (64 KB)
Ways to pay 1 EUR: 4562
Cases remembered: 238

Para recordar

Una función recursiva se llama a sí misma con un caso más pequeño.
Sin caso base, la recursión no termina.
Es natural para árboles: carpetas, menús, JSON anidado.
La memoización guarda resultados para no repetir cálculos.
Python corta la recursión hacia las 1000 llamadas anidadas.

Ejercicio

Escriba una función recursiva count_files(folder) que devuelva cuántos archivos hay en project (debe dar 6).