Recursividad 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ó)

Para practicar para el examen, escribí una función recursiva que contaba las personas de la cola del comedor. La probé con tres nombres y me dijo 4. La probé con uno y me dijo 2. Con la cola vacía, 1: una persona fantasma que aparecía siempre, por muy vacía que estuviera la cola. Revisé el caso general veinte veces, porque estaba seguro de que el fallo era ese 1 +.

El caso general estaba bien. El fallo estaba en el caso base: había escrito return 1 cuando la cola estaba vacía, como si una cola vacía tuviera a alguien. Ese 1 se colaba al final de todas las sumas, en todas las llamadas. Es el tipo de error de este tema: la recursión parece correcta y la salida casi tiene sentido.

Hoy practicamos con tres ejercicios de dificultad creciente, tres fragmentos para depurar (incluido el de la persona fantasma) y un chuletario para llevarte. Estos ejercicios usan la teoría de recursividad y repasan lo de la práctica. Puedes hacerlos sin ellas, pero te costará más.

Cómo usar este artículo

1. Lee el enunciado de un nivel y no mires la solución todavía.
2. Escribe tu versión, ejecútala y compara tu salida con la esperada.
3. Si te atascas, mira solo la 🔵 pista y vuelve a intentarlo.
4. Cuando termines, compara con la solución y fíjate en por qué está hecha así, no solo en que dé la misma salida.

Nivel 1 · Básico: la cuenta atrás y la cuenta de las bandejas

Enunciado. Escribe tres funciones recursivas:

• cuenta_atras(delante), que muestra Quedan N delante desde delante hasta 1 y, al final, ¡Me toca!. No devuelve nada.
• total(precios), que devuelve la suma de una lista de precios.
• contar_caros(precios, limite), que devuelve cuántos precios son mayores que limite.

Pruébalas con cuenta_atras(3) y con la lista [5.50, 2.25, 5.00, 1.50, 5.50], mostrando el total con dos decimales y las bandejas de más de 5 €.

Salida esperada:

Quedan 3 delante
Quedan 2 delante
Quedan 1 delante
¡Me toca!
Total: 19.75 €
Bandejas de más de 5 €: 2

Nivel 2 · Intermedio: la salida del comedor

Enunciado. Al terminar, la cola sale del comedor en orden inverso y algunas personas se van antes. Escribe dos funciones recursivas que devuelvan listas nuevas sin modificar la original:

• invertir(cola), que devuelve la cola al revés.
• quitar(cola, nombre), que devuelve la cola sin ninguna aparición de nombre (puede aparecer varias veces o ninguna).

Pruébalas con cola = ["Ana", "Luis", "Marta", "Luis", "Pablo"]: invierte la cola, quita a Luis, quita a Lucía (que no está) y, al final, muestra la cola original para comprobar que no ha cambiado.

Salida esperada:

['Pablo', 'Luis', 'Marta', 'Luis', 'Ana']
['Ana', 'Marta', 'Pablo']
['Ana', 'Luis', 'Marta', 'Luis', 'Pablo']
['Ana', 'Luis', 'Marta', 'Luis', 'Pablo']

Nivel 3 · Desafío: una cola encadenada en la que alguien se cuela

Enunciado. Representa la cola como una lista encadenada de tuplas (nombre, resto), terminada en (), como en la teoría. Escribe cuatro funciones recursivas:

• desde_lista(lista): convierte una lista de Python en una cola encadenada.
• longitud(cola): el número de personas.
• a_texto(cola): devuelve un string con el formato Ana -> Luis -> Marta, o (vacía) si no hay nadie.
• colarse(cola, nombre, delante_de): devuelve una cola nueva en la que nombre está justo delante de delante_de. Si delante_de no está en la cola, nombre se pone al final.

Crea la cola de Ana, Luis y Marta, muéstrala tal cual y con su longitud y su texto. Después, cuela a Pablo delante de Marta, cuela a Sara delante de Lucía (que no está), muestra la cola original para comprobar que no ha cambiado y, por último, el texto de una cola vacía.

Salida esperada:

('Ana', ('Luis', ('Marta', ())))
3 personas: Ana -> Luis -> Marta
Ana -> Luis -> Pablo -> Marta
Ana -> Luis -> Marta -> Sara
Ana -> Luis -> Marta
(vacía)

¿Qué falla aquí?

Tres fragmentos con un fallo cada uno. Antes de leer la explicación, haz dos cosas: predice si da error y, si no lo da, qué imprime.

Fragmento 1

contar.py

def contar(cola):
    if cola == []:
        return 1
    return 1 + contar(cola[1:])


print(contar(["Ana", "Luis", "Marta"]))

*Piénsalo antes de seguir: hay tres personas en la cola. ¿Qué imprime python3 contar.py?*

Explicación. No hay ningún error, pero el resultado es incorrecto:

4

Es la persona fantasma del principio. El caso base dice que una cola vacía tiene 1 persona, y ese 1 se suma al final de la cadena: 1 + (1 + (1 + 1)). Cualquier cola sale con una persona de más.

Arreglo. Una cola vacía tiene 0 personas:

def contar(cola):
    if cola == []:
        return 0                 # una cola vacía tiene 0 personas
    return 1 + contar(cola[1:])


print(contar(["Ana", "Luis", "Marta"]))
print(contar([]))

3
0

Fragmento 2

total.py

def total(precios):
    if precios == []:
        return 0
    return precios[0] + total(precios[0:])


print(total([5.50, 5.00, 2.25]))

¿Da error? ¿Qué imprime? Queremos sumar tres bandejas.

Explicación. Esta vez sí hay error:

Traceback (most recent call last):
  File "total.py", line 7, in <module>
    print(total([5.50, 5.00, 2.25]))
          ^^^^^^^^^^^^^^^^^^^^^^^^^
  File "total.py", line 4, in total
    return precios[0] + total(precios[0:])
                        ^^^^^^^^^^^^^^^^^^
  File "total.py", line 4, in total
    return precios[0] + total(precios[0:])
                        ^^^^^^^^^^^^^^^^^^
  File "total.py", line 4, in total
    return precios[0] + total(precios[0:])
                        ^^^^^^^^^^^^^^^^^^
  [Previous line repeated 995 more times]
  File "total.py", line 2, in total
    if precios == []:
       ^^^^^^^^^^^^^
RecursionError: maximum recursion depth exceeded in comparison

El slice precios[0:] va desde la posición 0 hasta el final, es decir, la lista entera. La llamada recursiva recibe exactamente la misma lista, que nunca se queda vacía, así que el caso base no llega nunca y la pila se desborda tras unas mil llamadas. Fíjate en el [Previous line repeated 995 more times]: Python resume las llamadas repetidas para no llenar la pantalla.

Arreglo. El resto es la lista sin el primero: precios[1:].

def total(precios):
    if precios == []:
        return 0
    return precios[0] + total(precios[1:])    # el resto: SIN el primero


print(total([5.50, 5.00, 2.25]))

12.75

Fragmento 3

esta.py

def esta(cola, nombre):
    if cola == []:
        return False
    if cola[0] == nombre:
        return True
    esta(cola[1:], nombre)


cola = ["Ana", "Luis", "Marta"]
print(esta(cola, "Ana"))
print(esta(cola, "Marta"))
print(esta(cola, "Lucía"))

¿Da error? ¿Qué imprime? Marta está en la cola y Lucía no.

Explicación. No da error, pero dos de las tres respuestas son None:

True
None
None

Con Ana funciona porque está la primera y se cumple el return True en la primera llamada. Con Marta, la función se llama a sí misma con el resto, y esa llamada sí encuentra a Marta y devuelve True… pero la llamada de arriba no hace nada con esa respuesta: la tira. Como llega al final de la función sin return, devuelve None. Con Lucía pasa lo mismo: el False del caso base se pierde por el camino.

Arreglo. Devuelve lo que conteste el resto:

def esta(cola, nombre):
    if cola == []:
        return False
    if cola[0] == nombre:
        return True
    return esta(cola[1:], nombre)       # devolver lo que contesta el resto


cola = ["Ana", "Luis", "Marta"]
print(esta(cola, "Ana"))
print(esta(cola, "Marta"))
print(esta(cola, "Lucía"))

True
True
False

Soluciones

Mira esta sección solo cuando hayas intentado el ejercicio. Si tu código es distinto pero da la misma salida y cumple los requisitos (funciones recursivas, sin bucles), también es una solución válida.

Solución del Nivel 1

cuenta_atras.py

def cuenta_atras(delante):
    """Anuncia cuántos quedan delante hasta que te toca."""
    if delante == 0:
        print("¡Me toca!")
    else:
        print(f"Quedan {delante} delante")
        cuenta_atras(delante - 1)


def total(precios):
    """Suma los precios de una lista de bandejas."""
    if precios == []:
        return 0
    return precios[0] + total(precios[1:])


def contar_caros(precios, limite):
    """Cuenta los precios mayores que limite."""
    if precios == []:
        return 0
    if precios[0] > limite:
        return 1 + contar_caros(precios[1:], limite)
    return contar_caros(precios[1:], limite)


cuenta_atras(3)
precios = [5.50, 2.25, 5.00, 1.50, 5.50]
print(f"Total: {total(precios):.2f} €")
print("Bandejas de más de 5 €:", contar_caros(precios, 5))

Por qué está hecho así:

• cuenta_atras no devuelve nada: imprime. Su caso base imprime ¡Me toca! y termina; el caso general imprime la línea y se llama con delante - 1, que se acerca al 0. Como el print va antes de la llamada, las líneas salen a la ida, de 3 a 1.
• total es el esquema de primero y resto en estado puro: 0 para la lista vacía y precios[0] + total(precios[1:]) en el caso general. Las cuentas cuadran: 5.50 + 2.25 + 5.00 + 1.50 + 5.50 = 19.75.
• contar_caros tiene dos casos generales: si el primero supera el límite suma 1, y si no, no suma nada. En los dos, la llamada recibe precios[1:]. Los dos 5.50 cuentan; el 5.00 no, porque no es mayor que 5.
• limite se pasa igual en todas las llamadas: es un dato que no cambia. Solo cambia la lista, que es lo que hace el problema más pequeño.

Solución del Nivel 2

salida.py

def invertir(cola):
    """Devuelve la cola en orden inverso, sin modificar la original."""
    if cola == []:
        return []
    return invertir(cola[1:]) + [cola[0]]


def quitar(cola, nombre):
    """Devuelve una cola nueva sin ninguna aparición de nombre."""
    if cola == []:
        return []
    if cola[0] == nombre:
        return quitar(cola[1:], nombre)
    return [cola[0]] + quitar(cola[1:], nombre)


cola = ["Ana", "Luis", "Marta", "Luis", "Pablo"]
print(invertir(cola))
print(quitar(cola, "Luis"))
print(quitar(cola, "Lucía"))
print(cola)

Por qué está hecho así:

• invertir sigue la pista: invierte el resto y pone el primero al final. Para ["Ana", "Luis"]: invertir(["Luis"]) + ["Ana"], que es ["Luis"] + ["Ana"]. La concatenación con + crea una lista nueva, así que la original no se toca.
• [cola[0]] mete el primer nombre en una lista de un elemento. Sin los corchetes, lista + "Ana" daría un TypeError, porque no se puede concatenar una lista con un string.
• quitar construye la respuesta solo con lo que quiere conservar: si el primero es el nombre, lo salta (devuelve directamente lo del resto); si no, lo pone delante. Por eso quita todas las apariciones de Luis, no solo la primera, a diferencia de list.remove.
• Quitar a Lucía no da error: si no aparece, todos los nombres se conservan y la cola sale igual. Recuerda que remove sí lanzaría ValueError.
• La última línea demuestra que ninguna de las dos funciones ha modificado cola: todas devuelven listas nuevas.

Solución del Nivel 3

encadenada.py

def desde_lista(lista):
    """Convierte una lista de Python en una cola encadenada (nombre, resto)."""
    if lista == []:
        return ()
    return (lista[0], desde_lista(lista[1:]))


def longitud(cola):
    if cola == ():
        return 0
    nombre, resto = cola
    return 1 + longitud(resto)


def a_texto(cola):
    """Devuelve la cola como 'Ana -> Luis -> Marta'."""
    if cola == ():
        return "(vacía)"
    nombre, resto = cola
    if resto == ():
        return nombre
    return nombre + " -> " + a_texto(resto)


def colarse(cola, nombre, delante_de):
    """Devuelve una cola nueva con nombre justo delante de delante_de.
    Si delante_de no está, nombre se pone al final."""
    if cola == ():
        return (nombre, ())
    primero, resto = cola
    if primero == delante_de:
        return (nombre, cola)
    return (primero, colarse(resto, nombre, delante_de))


cola = desde_lista(["Ana", "Luis", "Marta"])
print(cola)
print(longitud(cola), "personas:", a_texto(cola))
nueva = colarse(cola, "Pablo", "Marta")
print(a_texto(nueva))
print(a_texto(colarse(cola, "Sara", "Lucía")))
print(a_texto(cola))
print(a_texto(()))

Por qué está hecho así:

• desde_lista construye la cola de delante hacia atrás con recursión: el primer nodo guarda el primer nombre y, como resto, la cola encadenada del resto de la lista. El caso base convierte la lista vacía en la cola vacía ().
• longitud desempaqueta cada nodo con nombre, resto = cola y suma 1 por nodo. nombre no se usa, pero desempaquetar así deja claro qué es cada parte.
• a_texto tiene dos casos base: la cola vacía (que solo se da si la cola entera está vacía) y el último nodo, cuyo resto es (). Gracias a ese segundo caso, la flecha no aparece después de Marta.
• colarse es el más interesante. Si el primer nodo es delante_de, devuelve (nombre, cola): un nodo nuevo que apunta a la cola de siempre. Si no, devuelve (primero, colarse(resto, …)): reconstruye el primer nodo con el resto ya modificado. Como las tuplas son inmutables, no se puede «enganchar» a Pablo en la cola original; hay que crear nodos nuevos hasta el punto de inserción.
• Si llega a la cola vacía sin encontrar a delante_de, el caso base devuelve (nombre, ()): un último nodo con nombre. Por eso Sara acaba al final.
• La cola original no cambia: a_texto(cola) sigue mostrando a Ana, Luis y Marta. Además, la cola nueva comparte con la original el nodo de Marta: solo se crean nodos nuevos para Ana, Luis y Pablo.

Míralo paso a paso en Python Tutor

El fallo del fragmento 3 se entiende mucho mejor en vivo. Python Tutor ejecuta el código línea a línea y muestra el valor que devuelve cada llamada. Elige Python 3 y pega este programa, que busca a Marta con la versión rota y con la buena:

def esta(cola, nombre):
    if cola == []:
        return False
    if cola[0] == nombre:
        return True
    esta(cola[1:], nombre)


def esta_bien(cola, nombre):
    if cola == []:
        return False
    if cola[0] == nombre:
        return True
    return esta_bien(cola[1:], nombre)


cola = ["Ana", "Luis", "Marta"]
print(esta(cola, "Marta"))
print(esta_bien(cola, "Marta"))

Salida esperada:

None
True

Qué observar, paso a paso:

1. En esta(cola, "Marta") se apilan tres marcos: la cola con tres nombres, con dos y con uno. En el tercero, cola[0] es "Marta" y Python Tutor muestra Return value: True.
2. Ahora mira el segundo marco al volver: la línea esta(cola[1:], nombre) ha terminado, pero su True no se guarda en ningún sitio. La función llega al final y su valor devuelto es None.
3. El primer marco hace lo mismo: recibe None y devuelve None. Eso es lo que imprime el primer print.
4. Repite con esta_bien: en el segundo y en el primer marco, el valor devuelto es True, porque el return sube la respuesta de un marco al siguiente.
5. Compara los dos recorridos: los marcos y los argumentos son idénticos. La única diferencia es si la respuesta sube o se pierde, y eso lo decide un return.

Chuletario: Recursividad

Lo esencial en 30 segundos

• Una función recursiva se llama a sí misma con una versión más pequeña del problema.
• Caso base: la entrada más pequeña, que se responde sin llamadas. Caso general: combina el primer paso con la llamada sobre el resto.
• La llamada tiene que reducir el problema (l[1:], n - 1, n // 2, inf/sup que se acercan).
• Todos los caminos devuelven algo: return delante de la llamada recursiva.
• Las llamadas se apilan: lo que va antes de la llamada se ejecuta a la ida; lo que va después, a la vuelta. Límite: unas 1000.
• No repitas llamadas iguales: guarda el resultado en una variable.
• Inmersión: añade parámetros (posición, zona, acumulador) en una función auxiliar y llámala desde la original.

Sintaxis

Quiero…	Código	Resultado
Esquema básico	if caso_base: return valor / return combinar(x, f(resto))	Función recursiva
Primero y resto	l[0] y l[1:]	El resto es una lista más corta
Resto y último	l[:-1] y l[-1]	Igual, pero desde el final
Sumar una lista	return l[0] + suma(l[1:])	Caso base: 0
Contar con condición	return (1 if cond else 0) + contar(l[1:])	Caso base: 0
Buscar	if l[0] == x: return True / return esta(l[1:], x)	Caso base: False
Construir una lista	return [l[0]] + f(l[1:])	Lista nueva
Invertir	return invertir(l[1:]) + [l[0]]	Lista al revés
Búsqueda binaria	medio = (inf + sup) // 2 y llamar con (inf, medio) o (medio + 1, sup)	Posición o -1
Inmersión	def f(l): return f_desde(l, 0)	Interfaz sencilla, sin copias
Nodo encadenado	nombre, resto = cola	Caso base: cola == ()
Detectar sublista	isinstance(x, list)	True si x es una lista
Ver el límite	sys.getrecursionlimit()	1000

Plantillas de los ejercicios

Recorrer una lista con primero y resto (Nivel 1):

def total(precios):
    if precios == []:
        return 0
    return precios[0] + total(precios[1:])

Construir una lista nueva filtrando (Nivel 2):

def quitar(cola, nombre):
    if cola == []:
        return []
    if cola[0] == nombre:
        return quitar(cola[1:], nombre)
    return [cola[0]] + quitar(cola[1:], nombre)

Invertir (Nivel 2):

def invertir(cola):
    if cola == []:
        return []
    return invertir(cola[1:]) + [cola[0]]

Lista encadenada: recorrer y reconstruir (Nivel 3):

def longitud(cola):
    if cola == ():
        return 0
    nombre, resto = cola
    return 1 + longitud(resto)


def colarse(cola, nombre, delante_de):
    if cola == ():
        return (nombre, ())
    primero, resto = cola
    if primero == delante_de:
        return (nombre, cola)
    return (primero, colarse(resto, nombre, delante_de))

Búsqueda binaria por inmersión (teoría y práctica):

def buscar_en_rango(lista, x, inf, sup):
    if inf >= sup:
        return -1
    medio = (inf + sup) // 2
    if lista[medio] == x:
        return medio
    if lista[medio] > x:
        return buscar_en_rango(lista, x, inf, medio)
    return buscar_en_rango(lista, x, medio + 1, sup)

Errores que más se repiten

Síntoma	Causa probable
RecursionError: maximum recursion depth exceeded	No hay caso base, no se alcanza o la llamada no reduce el problema (l[0:], n en vez de n - 1)
RecursionError con una función correcta	La entrada es demasiado grande para unas 1000 llamadas: busca una solución menos profunda o usa un bucle
La función devuelve None	Falta return delante de la llamada recursiva
El resultado sale siempre 1 de más (o de menos)	El caso base devuelve un valor incorrecto (return 1 en vez de return 0)
TypeError: can only concatenate list (not "str") to list	Concatenas un elemento suelto: mételo entre corchetes, [x]
La búsqueda binaria nunca termina	Llamas con medio en vez de medio + 1 en la mitad derecha
La posición encontrada no es la de la lista original	Buscas con slices: usa inmersión con inf y sup
ValueError: not enough values to unpack en una lista encadenada	Desempaquetas (): comprueba antes el caso base cola == ()
La función es lentísima con números grandes	Repites la misma llamada recursiva: guarda el resultado en una variable

Antes de entregar, pregúntate

1. ¿Cuál es mi caso base, y devuelve la respuesta correcta para la entrada más pequeña?
2. ¿Cada llamada recursiva recibe algo más pequeño que la anterior?
3. ¿Todos los caminos de la función terminan en un return (si la función debe devolver algo)?
4. ¿Hago la misma llamada recursiva más de una vez, o copio la lista en cada llamada cuando podría usar índices?

Si quieres repasar el tema desde la base, vuelve a la teoría de recursividad.

Sigue aprendiendoTodos los artículos de Python

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