Recursividad en Python — práctica con la cola del comedor, una búsqueda de turnos con traza y un pedido de grupo (y el turno que estaba en la posición equivocada)

Quería saber en qué posición de la lista estaba mi número de turno del comedor, el 58, y escribí una búsqueda binaria recursiva con slices: miro el del medio y, si no es, sigo buscando en la mitad que toca con turnos[medio + 1:] o turnos[:medio]. Cuando lo encontraba, devolvía medio. La función encontraba el 58 sin problemas… y me decía que estaba en la posición 0. En una lista de 16 turnos ordenados, el 58 estaba en la posición 11.

Tardé un rato en verlo: cada slice es una lista nueva, y sus posiciones empiezan otra vez en 0. Cuando la función encontraba el 58, lo encontraba en un trocito de un solo elemento, y la posición 0 de ese trocito no tenía nada que ver con la lista original. El arreglo es la técnica de inmersión de la teoría: no cortar la lista y llevar los índices como parámetros.

Hoy practicamos recursividad con tres programas completos: las cuentas de la cola del comedor, una búsqueda de turnos que enseña cada llamada por pantalla y un pedido de grupo con subpedidos dentro de subpedidos. Esta práctica se apoya en la teoría de recursividad. Si aún dudas con los slices o con las listas de listas, repasa antes mutabilidad, copias y matrices.

Cómo usar este artículo

Cada programa va completo en un solo archivo. Cópialo, guárdalo con el nombre que se indica y lánzalo desde la terminal con python3 nombre.py. Antes de mirar la salida, intenta predecirla: en recursividad, predecir qué devuelve cada llamada es justo la habilidad que hay que entrenar.

Programa 1 · Las cuentas de la cola del comedor

La cola es una lista de tuplas (nombre, menú, precio). Queremos cuatro cosas, todas con funciones recursivas: cuánto se cobra en total, cuántos menús de un tipo hay, cuál es la bandeja más cara y en qué posición está una persona.

comedor.py

COLA = [
    ("Ana", "normal", 5.50),
    ("Luis", "vegetariano", 5.00),
    ("Marta", "normal", 5.50),
    ("Pablo", "vegetariano", 5.00),
    ("Sara", "postre", 2.25),
]


def total(cola):
    """Suma lo que paga toda la cola."""
    if cola == []:
        return 0
    nombre, menu, precio = cola[0]
    return precio + total(cola[1:])


def contar_menu(cola, tipo):
    """Cuenta las bandejas de un tipo de menú."""
    if cola == []:
        return 0
    nombre, menu, precio = cola[0]
    if menu == tipo:
        return 1 + contar_menu(cola[1:], tipo)
    return contar_menu(cola[1:], tipo)


def mas_cara(cola):
    """Devuelve la bandeja más cara (la cola no puede estar vacía)."""
    if len(cola) == 1:                    # caso base: una sola bandeja
        return cola[0]
    la_del_resto = mas_cara(cola[1:])
    if cola[0][2] >= la_del_resto[2]:
        return cola[0]
    return la_del_resto


def posicion(cola, nombre, pos=0):
    """Posición de nombre en la cola, o -1 si no está."""
    if pos == len(cola):                  # hemos mirado a todos
        return -1
    if cola[pos][0] == nombre:
        return pos
    return posicion(cola, nombre, pos + 1)


print(f"Total a cobrar: {total(COLA):.2f} €")
print("Menús vegetarianos:", contar_menu(COLA, "vegetariano"))
print("Bandeja más cara:", mas_cara(COLA))
print("Pablo está en la posición", posicion(COLA, "Pablo"))
print("Lucía está en la posición", posicion(COLA, "Lucía"))

Lánzalo con python3 comedor.py:

Total a cobrar: 23.25 €
Menús vegetarianos: 2
Bandeja más cara: ('Ana', 'normal', 5.5)
Pablo está en la posición 3
Lucía está en la posición -1

Entre líneas:

• total y contar_menu siguen el esquema de primero y resto: desempaquetan la primera tupla con nombre, menu, precio = cola[0] y llaman con cola[1:]. El caso base, la cola vacía, devuelve 0 en las dos. Las cuentas cuadran: 5.50 + 5.00 + 5.50 + 5.00 + 2.25 = 23.25.
• mas_cara tiene un caso base distinto: una sola bandeja. ¿Por qué no la cola vacía? Porque una cola vacía no tiene bandeja más cara: no hay nada razonable que devolver. Por eso el docstring avisa de que la cola no puede estar vacía.
• En el caso general de mas_cara, primero se calcula la más cara del resto y después se compara con la primera. Ana y Marta pagan lo mismo (5.50) y gana Ana porque la comparación es >=: en caso de empate, se queda la primera. Con > habría salido Marta.
• posicion usa inmersión: en lugar de cortar la cola, lleva un parámetro pos que empieza en 0 (valor por defecto) y avanza de uno en uno. Así no copia la lista y, cuando encuentra a Pablo, pos es su posición real (3). Si llega al final sin encontrarlo, devuelve -1, como con Lucía.

Pruébalo tú

• Cambia >= por > en mas_cara y comprueba que ahora sale Marta. Después, explica con tus palabras por qué.
• Escribe mas_barata(cola) siguiendo el mismo esquema que mas_cara. ¿Qué bandeja debería salir?
• Reescribe total con inmersión, con un parámetro pos=0 en lugar de cola[1:]. ¿Cuál es ahora el caso base?

Programa 2 · Buscar un turno, llamada a llamada

En el comedor repartimos números de turno, y la lista de turnos que siguen esperando está ordenada. Buscamos un turno con búsqueda binaria e imprimimos cada llamada para ver cómo se va estrechando la zona.

turnos.py

TURNOS = [3, 8, 12, 15, 21, 27, 30, 34, 41, 47, 52, 58, 63, 70, 76, 81]


def buscar(turnos, turno, inf, sup, llamada=1):
    """Busca turno entre las posiciones inf y sup - 1."""
    if inf >= sup:
        print(f"  Llamada {llamada}: zona vacía, no está")
        return -1
    medio = (inf + sup) // 2
    print(f"  Llamada {llamada}: miro de {inf} a {sup - 1}, en el medio hay {turnos[medio]}")
    if turnos[medio] == turno:
        return medio
    if turnos[medio] > turno:
        return buscar(turnos, turno, inf, medio, llamada + 1)
    return buscar(turnos, turno, medio + 1, sup, llamada + 1)


def buscar_turno(turnos, turno):
    return buscar(turnos, turno, 0, len(turnos))


for turno in [58, 3, 50]:
    print(f"Busco el turno {turno}")
    print("  Posición:", buscar_turno(TURNOS, turno))

Lánzalo con python3 turnos.py:

Busco el turno 58
  Llamada 1: miro de 0 a 15, en el medio hay 41
  Llamada 2: miro de 9 a 15, en el medio hay 63
  Llamada 3: miro de 9 a 11, en el medio hay 52
  Llamada 4: miro de 11 a 11, en el medio hay 58
  Posición: 11
Busco el turno 3
  Llamada 1: miro de 0 a 15, en el medio hay 41
  Llamada 2: miro de 0 a 7, en el medio hay 21
  Llamada 3: miro de 0 a 3, en el medio hay 12
  Llamada 4: miro de 0 a 1, en el medio hay 8
  Llamada 5: miro de 0 a 0, en el medio hay 3
  Posición: 0
Busco el turno 50
  Llamada 1: miro de 0 a 15, en el medio hay 41
  Llamada 2: miro de 9 a 15, en el medio hay 63
  Llamada 3: miro de 9 a 11, en el medio hay 52
  Llamada 4: miro de 9 a 9, en el medio hay 47
  Llamada 5: zona vacía, no está
  Posición: -1

Entre líneas:

• buscar trabaja con la lista entera y dos índices: inf (incluido) y sup (excluido). Es la búsqueda por inmersión de la teoría, con un parámetro extra, llamada, que solo sirve para numerar las líneas de la traza.
• Sigue el turno 58: la primera llamada mira de 0 a 15 y en el medio encuentra 41. Como 58 es mayor, el turno solo puede estar a la derecha: la segunda llamada mira de 9 a 15. Allí el medio es 63, mayor que 58, así que toca la izquierda (de 9 a 11). En la cuarta llamada, la zona tiene un solo turno y es el 58: posición 11, la posición de verdad en TURNOS.
• El turno 3 está al principio y hace falta una llamada más (5), porque la zona se va quedando siempre con la mitad izquierda hasta tener un solo elemento.
• El turno 50 no existe. Tras cuatro llamadas, la zona de 9 a 9 tiene el 47; como 50 es mayor, la siguiente zona es de 10 a 9, es decir, inf >= sup: zona vacía, y la función devuelve -1.
• Con 16 turnos, ninguna búsqueda necesita más de 5 llamadas. Con una búsqueda lineal, encontrar el 81 habría necesitado 16. Con un millón de turnos, la binaria haría unas 21 llamadas; la lineal, hasta un millón (y no cabría en la pila de Python).
• buscar_turno es la envoltura: quien la usa solo pasa la lista y el turno, sin preocuparse de inf, sup ni llamada.

Pruébalo tú

• Busca el turno 81 (el último) y el 20 (no existe). Antes de ejecutar, predice cuántas llamadas hará cada búsqueda.
• Cambia el medio + 1 por medio y busca el 50. Observa en la traza cómo la zona deja de encoger.
• Escribe la versión con slices (sin inf ni sup) que devuelve medio, busca el 58 y comprueba que te da una posición incorrecta. Así verás el error del principio con tus propios ojos.

Programa 3 · Un pedido de grupo con subpedidos

Para terminar, una estructura que pide recursividad a gritos. El grupo de prácticas hace un pedido conjunto: algunos piden suelto (un precio) y otros piden varias cosas (una lista de precios). Y dentro de la mesa del grupo, alguien vuelve a pedir varias cosas. Es una lista que puede contener listas, a cualquier profundidad.

pedidos.py

PEDIDO = [
    5.50,                       # Ana: menú
    [5.00, 2.25],               # Luis: menú y postre
    [                           # mesa del grupo de prácticas
        5.50,
        [5.00, 1.50],           # Pablo: menú y café
        5.50,
    ],
    2.25,                       # Sara: postre
]


def total(pedido):
    """Suma todos los precios, estén al nivel que estén."""
    if pedido == []:
        return 0
    primero = pedido[0]
    if isinstance(primero, list):           # el primero es un subpedido
        return total(primero) + total(pedido[1:])
    return primero + total(pedido[1:])


def contar_platos(pedido):
    """Cuenta los precios sueltos (los platos)."""
    if pedido == []:
        return 0
    primero = pedido[0]
    if isinstance(primero, list):
        return contar_platos(primero) + contar_platos(pedido[1:])
    return 1 + contar_platos(pedido[1:])


def aplanar(pedido):
    """Devuelve una lista con todos los precios, sin anidar."""
    if pedido == []:
        return []
    primero = pedido[0]
    if isinstance(primero, list):
        return aplanar(primero) + aplanar(pedido[1:])
    return [primero] + aplanar(pedido[1:])


def niveles(pedido):
    """Cuántos niveles de listas hay, contando el de fuera."""
    maximo = 1
    for elemento in pedido:
        if isinstance(elemento, list):
            maximo = max(maximo, 1 + niveles(elemento))
    return maximo


print(f"Total: {total(PEDIDO):.2f} €")
print("Platos:", contar_platos(PEDIDO))
print("Lista plana:", aplanar(PEDIDO))
print("Niveles:", niveles(PEDIDO))

Lánzalo con python3 pedidos.py:

Total: 32.50 €
Platos: 8
Lista plana: [5.5, 5.0, 2.25, 5.5, 5.0, 1.5, 5.5, 2.25]
Niveles: 3

Entre líneas:

• total, contar_platos y aplanar tienen la misma estructura: caso base con la lista vacía y, en el caso general, dos situaciones según lo que sea el primer elemento. Si es un número, se combina directamente con el resto. Si es una lista, isinstance(primero, list) lo detecta y se hace una llamada recursiva para el subpedido y otra para el resto.
• Esto es nuevo respecto a la cola: aquí cada llamada puede hacer dos llamadas recursivas, una que «baja» a la sublista y otra que «avanza» por la lista. Por eso funciona con cualquier nivel de anidamiento sin escribir un bucle por nivel.
• Las cuentas cuadran: 5.50 + (5.00 + 2.25) + (5.50 + (5.00 + 1.50) + 5.50) + 2.25 = 32.50, y hay 8 precios sueltos, que son exactamente los de la lista plana.
• aplanar construye una lista nueva concatenando con +: aplanar(primero) + aplanar(pedido[1:]) junta los precios del subpedido con los del resto, y [primero] + … mete un número suelto dentro de una lista para poder concatenarlo.
• niveles mezcla un bucle y recursión: recorre los elementos con un for y, para cada sublista, pregunta cuántos niveles tiene. El pedido tiene 3: la lista exterior, la mesa del grupo y el pedido de Pablo dentro de la mesa.

Pruébalo tú

• Añade al final del pedido una lista vacía, []. ¿Cambia el total? ¿Y los niveles? Ejecuta y comprueba si acertaste.
• Escribe mas_caro(pedido) que devuelva el precio más alto de todo el pedido, esté al nivel que esté. Pista: puedes reutilizar aplanar, o escribirlo con el mismo esquema que total.
• Mete el pedido de Pablo un nivel más adentro ([[5.00, 1.50]]) y predice qué cambia en cada línea de la salida.

Míralo paso a paso en Python Tutor

Python Tutor ejecuta el código línea a línea y dibuja cada llamada como un marco con sus propias variables. Elige Python 3 y pega esta búsqueda binaria por inmersión, que busca un turno que está y otro que no:

def buscar(turnos, turno, inf, sup):
    if inf >= sup:
        return -1
    medio = (inf + sup) // 2
    if turnos[medio] == turno:
        return medio
    if turnos[medio] > turno:
        return buscar(turnos, turno, inf, medio)
    return buscar(turnos, turno, medio + 1, sup)


turnos = [3, 8, 12, 15, 21, 27, 30]
print(buscar(turnos, 21, 0, len(turnos)))
print(buscar(turnos, 10, 0, len(turnos)))

Salida esperada:

4
-1

Qué observar, paso a paso:

1. En la primera llamada, el marco de buscar tiene inf = 0 y sup = 7, y medio vale 3 (el 15). Como 21 es mayor, se crea un segundo marco con inf = 4.
2. Mira la flecha de turnos en todos los marcos: apunta siempre a la misma lista. La inmersión no copia nada; solo cambian inf y sup.
3. En el segundo marco, medio vale 5 (el 27). Como 27 es mayor que 21, el tercer marco tiene sup = 5. Ahí medio es 4, el 21: la función devuelve 4, y ese valor sube intacto por todos los marcos hasta el print.
4. En la segunda búsqueda (el 10), observa cómo la zona encoge hasta que inf y sup se igualan. En ese marco se cumple inf >= sup y el valor devuelto es -1.
5. Fíjate en que ningún marco hace nada a la vuelta: cada uno devuelve directamente lo que le contesta el siguiente. Por eso el resultado del último llega tal cual al primero.

Para terminar

Hoy has visto la recursividad en tres situaciones distintas: recorrer una lista con primero y resto (y con inmersión, para no copiarla), dividir el problema por la mitad con una búsqueda binaria que enseña su propia pila, y recorrer una estructura anidada en la que cada elemento puede ser otra lista. Si algo no te ha cuadrado, vuelve a la teoría; y cuando te sientas cómodo, pasa a los ejercicios, donde los fallos vienen incluidos.

Siguiente paso: ejerciciosRecursividad en Python — ejercicios con la cola del comedor, una salida al revés y una cola encadenada (y la persona de más que nunca existió)

¿Te ha servido este artículo? Así puedes apoyar SergioLearns →