Recursividad en Python — teoría con la cola del comedor, la pila de llamadas y una potencia que se hace rápida (y la función que nunca dejaba de preguntar)

La primera función recursiva que escribí tenía que contar cuántas personas había delante de mí en la cola del comedor. La idea me parecía preciosa: «las personas que tengo delante son una (la de justo delante) más las que tiene ella delante». Lo escribí tal cual, en una línea, y lo ejecuté con una cola de tres personas:

def cuantos_delante(delante):
    return 1 + cuantos_delante(delante[:-1])


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

Traceback (most recent call last):
  File "gancho.py", line 6, in <module>
    print(cuantos_delante(cola))
          ^^^^^^^^^^^^^^^^^^^^^
  File "gancho.py", line 2, in cuantos_delante
    return 1 + cuantos_delante(delante[:-1])
               ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "gancho.py", line 2, in cuantos_delante
    return 1 + cuantos_delante(delante[:-1])
               ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "gancho.py", line 2, in cuantos_delante
    return 1 + cuantos_delante(delante[:-1])
               ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

«¿Mil llamadas? Si solo hay tres personas.» Lo que había escrito no era falso, pero estaba incompleto: le había dicho a cada persona que preguntara a la de delante, y a nadie le había dicho cuándo parar. Cuando la cola se quedaba vacía, delante[:-1] seguía devolviendo una lista vacía, la función volvía a preguntar, y así hasta que Python se cansó y cortó por lo sano con un RecursionError.

Hoy entendemos qué es la recursividad, por qué toda función recursiva necesita un caso base y un caso general, cómo se apilan las llamadas en memoria, por qué dos soluciones recursivas del mismo problema pueden ser muy distintas en profundidad y eficiencia, y cómo se aplica todo esto a las secuencias, a las listas encadenadas y a la técnica de inmersión. El ejemplo que nos acompaña es la cola del comedor. Si vienes de mutabilidad, copias y matrices, te vendrá bien tener frescos los slices: aquí los vas a usar en casi cada línea. Y cuando acabes, la práctica de recursividad te espera con tres programas completos.

¿Qué es la recursividad?

La recursividad es una forma de resolver problemas que consiste en dividir el problema en versiones más pequeñas de sí mismo, hasta llegar a una tan pequeña que se resuelve directamente. En programación, se traduce en una función que se llama a sí misma.

Imagina la cola del comedor. Llegas al final y quieres saber cuántas personas tienes delante, pero no ves bien el principio. Así que le preguntas a la persona de justo delante: «¿cuántos tienes delante tú?». Ella no lo sabe, así que pregunta a la suya, y esa a la suya… hasta que la pregunta llega a la primera de la cola, que no tiene a nadie delante y contesta «cero». Esa respuesta vuelve hacia atrás: la segunda dice «1», la tercera «2»… y a ti te llega la respuesta final.

Fíjate en las dos piezas de esa historia:

• El caso base: la primera persona de la cola sabe la respuesta sin preguntar a nadie (cero). Es el punto donde la recursión para.
• El caso general: cualquier otra persona responde «1 (la de delante) + lo que me diga la de delante». Resuelve su problema usando la respuesta a un problema más pequeño (una cola con una persona menos).

En Python queda así:

def cuantos_delante(delante):
    """Cuenta las personas que hay delante en la cola del comedor."""
    if delante == []:                               # caso base: no hay nadie
        return 0
    else:                                           # caso general
        return 1 + cuantos_delante(delante[:-1])    # el de delante + los suyos


cola = ["Ana", "Luis", "Marta", "Pablo"]
print(cuantos_delante(cola))
print(cuantos_delante(["Ana"]))
print(cuantos_delante([]))

4
1
0

Entre líneas:

• delante es la lista de las personas que tienes delante, de la primera a la que está justo delante de ti. Esa última es delante[-1], y las que tiene ella delante son delante[:-1] (todas menos la última).
• Caso base: si delante está vacía, no hay nadie y la respuesta es 0, sin llamar a nadie.
• Caso general: 1 + cuantos_delante(delante[:-1]). La función se llama a sí misma con una lista una persona más corta. Cada llamada está más cerca del caso base, y eso garantiza que la recursión termina.
• Funciona con cuatro personas, con una y con ninguna. El caso base hace que la cola vacía también tenga respuesta.

Caso base y caso general: cómo se piensa una solución recursiva

Lo difícil de la recursividad no es escribirla, sino pensarla. En clase nos dieron cuatro preguntas que funcionan con casi cualquier problema. Vamos a aplicarlas a calcular el total que paga la cola (una lista de precios de bandejas):

Pregunta	Para el total de las bandejas
¿Qué determina el tamaño del problema?	El número de bandejas de la lista
¿Cómo paso a una versión más pequeña?	Quitando la primera: precios[1:]
¿Cuándo no puedo dividir más (caso base)?	Cuando no hay bandejas: el total es 0
¿Cómo combino la solución pequeña con lo que me queda?	Sumando el precio de la primera: precios[0] + total(precios[1:])

Con esas cuatro respuestas, la función casi se escribe sola. Y la misma receta sirve para contar cuántos menús vegetarianos hay en la cola:

def total(precios):
    """Suma los precios de todas las bandejas."""
    if precios == []:                       # sin bandejas, no se paga nada
        return 0
    return precios[0] + total(precios[1:])  # la primera + el total del resto


def contar_vegetarianos(menus):
    """Cuenta cuántos menús vegetarianos hay en la cola."""
    if menus == []:
        return 0
    if menus[0] == "vegetariano":           # el primero cuenta
        return 1 + contar_vegetarianos(menus[1:])
    return contar_vegetarianos(menus[1:])   # el primero no cuenta


print(total([5.50, 5.00, 2.25]))
print(contar_vegetarianos(["normal", "vegetariano", "normal", "vegetariano"]))

12.75
2

Entre líneas:

• Las dos funciones tienen la misma forma: un if para el caso base y un return que combina el primer elemento con la llamada sobre el resto. Esa forma es el esquema de casi todas las funciones recursivas sobre listas.
• En total, la combinación es una suma: precios[0] + total(precios[1:]). Para [5.50, 5.00, 2.25] da 5.50 + (5.00 + (2.25 + 0)).
• En contar_vegetarianos hay dos casos generales: si el primero es vegetariano, suma 1; si no, no suma nada. En los dos se llama con menus[1:], así que la lista siempre encoge.
• Aquí usamos la vista «primero y resto» (lista[0] y lista[1:]), mientras que en la cola usamos «resto y último» (delante[:-1]). Las dos son válidas: lo importante es que la llamada recursiva reciba algo más pequeño.

La pila de llamadas: qué pasa por dentro

Cuando una función se llama a sí misma, la llamada anterior no termina: se queda esperando la respuesta. Python guarda cada llamada pendiente, con sus propias variables, en una estructura llamada pila de llamadas (call stack): la última que entra es la primera que sale, como una pila de bandejas.

Para verlo, añadimos un parámetro nivel que solo sirve para sangrar la salida, y un par de print:

def cuantos_delante(delante, nivel=0):
    sangria = "    " * nivel
    print(f"{sangria}¿Cuántos tienes delante? {delante}")
    if delante == []:
        print(f"{sangria}Nadie: respondo 0")
        return 0
    respuesta = 1 + cuantos_delante(delante[:-1], nivel + 1)
    print(f"{sangria}Respondo {respuesta}")
    return respuesta


print("Total:", cuantos_delante(["Ana", "Luis", "Marta"]))

¿Cuántos tienes delante? ['Ana', 'Luis', 'Marta']
    ¿Cuántos tienes delante? ['Ana', 'Luis']
        ¿Cuántos tienes delante? ['Ana']
            ¿Cuántos tienes delante? []
            Nadie: respondo 0
        Respondo 1
    Respondo 2
Respondo 3
Total: 3

Lee la salida de arriba abajo:

• Fase de ida (bajada): cada llamada pregunta y se queda esperando. Fíjate en que la sangría crece: hay cuatro llamadas activas a la vez, cada una con su propia delante. Ninguna ha terminado todavía.
• Caso base: la cuarta llamada recibe [] y es la primera que puede responder sin preguntar: 0.
• Fase de vuelta (subida): las respuestas recorren la pila al revés. La tercera llamada recibe el 0 y responde 1; la segunda recibe el 1 y responde 2; la primera recibe el 2 y responde 3.
• Lo que va antes de la llamada recursiva se ejecuta a la ida; lo que va después, a la vuelta. Por eso los «¿Cuántos tienes delante?» salen en orden y los «Respondo» salen al revés.

El límite de la pila

La pila no es infinita. Python pone un límite al número de llamadas que pueden estar esperando a la vez:

import sys


def cuantos_delante(delante):
    if delante == []:
        return 0
    return 1 + cuantos_delante(delante[:-1])


print(sys.getrecursionlimit())
print(cuantos_delante(["alumno"] * 500))

1000
500

El límite por defecto es 1000. Con 500 personas en la cola, la pila llega a 501 llamadas y todo va bien. Con una cola de 5000, la función sería correcta, pero Python lanzaría RecursionError antes de llegar al caso base. Es exactamente el error del principio del artículo, solo que allí no era por una cola enorme, sino por una recursión que no paraba nunca.

Profundidad y eficiencia: tres formas de calcular una potencia

Dos soluciones recursivas del mismo problema pueden comportarse de forma muy distinta. El ejemplo clásico (y el que nos pusieron en clase) es la potencia base ** exp. Lo vemos con tres versiones, y con una variable llamadas que cuenta cuántas veces se llama cada función:

llamadas = 0


def potencia_lineal(base, exp):
    global llamadas
    llamadas += 1
    if exp == 0:
        return 1
    return base * potencia_lineal(base, exp - 1)


def potencia_doble(base, exp):
    global llamadas
    llamadas += 1
    if exp == 0:
        return 1
    if exp % 2 == 0:
        return potencia_doble(base, exp // 2) * potencia_doble(base, exp // 2)
    return base * potencia_doble(base, exp // 2) * potencia_doble(base, exp // 2)


def potencia_rapida(base, exp):
    global llamadas
    llamadas += 1
    if exp == 0:
        return 1
    mitad = potencia_rapida(base, exp // 2)     # una sola llamada
    if exp % 2 == 0:
        return mitad * mitad
    return base * mitad * mitad


for exp in [8, 16, 32]:
    llamadas = 0
    resultado = potencia_lineal(2, exp)
    print(f"lineal  2^{exp} = {resultado}: {llamadas} llamadas")
    llamadas = 0
    resultado = potencia_doble(2, exp)
    print(f"doble   2^{exp} = {resultado}: {llamadas} llamadas")
    llamadas = 0
    resultado = potencia_rapida(2, exp)
    print(f"rápida  2^{exp} = {resultado}: {llamadas} llamadas")

lineal  2^8 = 256: 9 llamadas
doble   2^8 = 256: 31 llamadas
rápida  2^8 = 256: 5 llamadas
lineal  2^16 = 65536: 17 llamadas
doble   2^16 = 65536: 63 llamadas
rápida  2^16 = 65536: 6 llamadas
lineal  2^32 = 4294967296: 33 llamadas
doble   2^32 = 4294967296: 127 llamadas
rápida  2^32 = 4294967296: 7 llamadas

Las tres dan el mismo resultado, pero mira las llamadas:

• **potencia_lineal** usa base ** exp = base * base ** (exp - 1). Cada llamada hace una llamada con el exponente uno más pequeño, así que para 2^8 hay 9 llamadas (de 8 a 0), y todas están activas a la vez: la profundidad de la recursión es 9. Llamadas y profundidad crecen igual que el exponente.
• **potencia_doble** usa base ** exp = base ** (exp // 2) * base ** (exp // 2). El exponente se divide por la mitad en cada nivel, así que la profundidad es muy pequeña (para 2^8: 8, 4, 2, 1, 0, es decir, 5 niveles). Pero cada llamada hace dos llamadas, y el número de llamadas se duplica en cada nivel: 31 para 2^8, 127 para 2^32. Usa poca memoria, pero trabaja mucho más que la lineal.
• **potencia_rapida se da cuenta de que las dos llamadas de la doble calculan exactamente lo mismo. La hace una sola vez**, guarda el resultado en mitad y lo multiplica por sí mismo. Mantiene la profundidad pequeña de la doble y deja una sola llamada por nivel: 5 llamadas para 2^8 y solo 7 para 2^32.
• global llamadas permite que la función cambie la variable de fuera; lo usamos solo para medir. En tus funciones normales, evita global.

La diferencia tiene dos caras que conviene separar:

Medida	Qué es	Lineal	Doble	Rápida
Profundidad	Cuántas llamadas están activas a la vez (memoria)	Crece como exp	Crece como log₂(exp)	Crece como log₂(exp)
Número de llamadas	Cuántas se hacen en total (tiempo)	exp + 1	Se duplica en cada nivel	Una por nivel

Recursividad sobre secuencias: primero y resto

Muchas estructuras se pueden ver de forma recursiva. Una lista no vacía es «un primer elemento seguido de una lista más pequeña», y eso encaja con el esquema recursivo. Dos ejemplos: buscar a alguien en la cola y buscar un número de turno en una lista ordenada.

def esta(cola, nombre):
    """¿Está nombre en la cola? Mira el primero y pregunta al resto."""
    if cola == []:
        return False
    if cola[0] == nombre:
        return True
    return esta(cola[1:], nombre)


def esta_turno(turnos, turno):
    """Búsqueda binaria en una lista ORDENADA de turnos."""
    if turnos == []:
        return False
    medio = len(turnos) // 2
    if turnos[medio] == turno:
        return True
    if turnos[medio] > turno:                        # está en la mitad izquierda
        return esta_turno(turnos[:medio], turno)
    return esta_turno(turnos[medio + 1:], turno)     # está en la mitad derecha


cola = ["Ana", "Luis", "Marta", "Pablo"]
print(esta(cola, "Marta"), esta(cola, "Lucía"))
turnos = [3, 8, 12, 15, 21, 27, 30, 34]
print(esta_turno(turnos, 27), esta_turno(turnos, 20))

True False
True False

Entre líneas:

• **esta es una búsqueda lineal: mira al primero de la cola y, si no es quien buscas, pregunta al resto. Tiene dos casos base**: la cola vacía (no está, False) y encontrar el nombre (sí está, True). En el peor caso, recorre toda la cola, así que su profundidad crece con el largo de la lista.
• **esta_turno es una búsqueda binaria (o dicotómica), que solo funciona si la lista está ordenada. Mira el elemento del medio: si es el turno, lo ha encontrado; si es mayor, el turno solo puede estar en la mitad izquierda; si es menor, en la derecha. Cada llamada descarta la mitad** de la lista, así que la profundidad crece como log₂ del largo: para 8 turnos, como mucho 5 llamadas (con 8, 4, 2, 1 y 0 elementos).
• Las dos usan slices (cola[1:], turnos[:medio]) para pasar la parte más pequeña. Funciona, pero tiene un coste escondido que veremos dentro de poco.

Listas encadenadas: una estructura recursiva de verdad

Hasta ahora hemos mirado las listas de forma recursiva. Pero también se pueden construir estructuras que son recursivas por definición. En clase vimos la lista encadenada hecha con tuplas: cada eslabón es una tupla (valor, resto), donde resto es otra lista encadenada, y la lista vacía es la tupla vacía ().

La cola del comedor encaja perfecto: «Ana, y detrás de ella, la cola de Luis; y detrás de Luis, la de Marta; y detrás de Marta, nadie».

vacia = ()                    # una cola vacía es una tupla vacía
cola = ("Marta", vacia)       # Marta y, detrás de ella, nadie
cola = ("Luis", cola)         # Luis y, detrás, la cola anterior
cola = ("Ana", cola)
print(cola)


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


def esta(cola, buscado):
    if cola == ():
        return False
    nombre, resto = cola
    if nombre == buscado:
        return True
    return esta(resto, buscado)


print(longitud(cola))
print(esta(cola, "Luis"), esta(cola, "Pablo"))

('Ana', ('Luis', ('Marta', ())))
3
True False

Entre líneas:

• La cola se construye de atrás hacia delante: primero Marta (con la cola vacía detrás), después Luis delante de Marta y, por último, Ana. El print muestra las tuplas anidadas: ('Ana', ('Luis', ('Marta', ()))).
• Cada tupla se llama nodo o eslabón: guarda un nombre y una referencia al siguiente nodo. La variable cola apunta, en realidad, solo al primero.
• nombre, resto = cola desempaqueta el nodo en sus dos partes. A partir de ahí, las funciones siguen el esquema de siempre: caso base con la cola vacía () y caso general con resto.
• Una ventaja: pasar resto a la llamada recursiva no copia nada, porque resto ya es la cola más pequeña. Una desventaja: no puedes ir directamente a la posición 2 como con lista[2]; para llegar al tercer nodo, tienes que pasar por los dos anteriores.

Inmersión recursiva: resolver un problema más general

Volvamos a la búsqueda binaria. Cada turnos[:medio] y cada turnos[medio + 1:] crea una lista nueva: ya lo viste en el tema anterior, un slice es una copia. Para buscar en una lista de un millón de turnos, la primera llamada copiaría medio millón de elementos solo para descartar la otra mitad. Además, la función solo dice si está, no dónde: la posición dentro de un slice no es la posición en la lista original.

La solución que nos dieron se llama inmersión: en lugar de resolver «¿está el turno en la lista?», resolvemos un problema más general que lo contiene, «¿está el turno entre las posiciones inf y sup de la lista?». La lista ya no se copia; solo cambian los dos índices:

def buscar_en_rango(turnos, turno, inf, sup):
    """Busca turno entre las posiciones inf (incluida) y sup (excluida)."""
    if inf >= sup:                                   # zona vacía
        return -1
    medio = (inf + sup) // 2
    if turnos[medio] == turno:
        return medio
    if turnos[medio] > turno:
        return buscar_en_rango(turnos, turno, inf, medio)
    return buscar_en_rango(turnos, turno, medio + 1, sup)


def buscar_turno(turnos, turno):
    """Devuelve la posición de turno en la lista ordenada, o -1."""
    return buscar_en_rango(turnos, turno, 0, len(turnos))


turnos = [3, 8, 12, 15, 21, 27, 30, 34]
print(buscar_turno(turnos, 27))
print(buscar_turno(turnos, 3), buscar_turno(turnos, 34))
print(buscar_turno(turnos, 20))

5
0 7
-1

Entre líneas:

• buscar_en_rango recibe la lista entera siempre y dos números que marcan la zona que queda por mirar: desde inf (incluida) hasta sup (excluida), igual que en un range.
• El caso base ahora es inf >= sup: la zona está vacía, así que el turno no está y devolvemos -1.
• Como trabajamos con las posiciones reales, cuando lo encontramos podemos devolver medio: la posición en la lista original. El 27 está en la posición 5.
• buscar_turno es la función que usa todo el mundo: mantiene la interfaz sencilla (lista y turno) y sumerge el problema en el general llamando con la zona completa, 0 y len(turnos). Por eso se llama inmersión: el problema original es un caso particular del general.

La misma idea sirve para cualquier recorrido. Si en vez de cortar la cola con slices llevas la posición como parámetro, tampoco copias nada:

def contar_desde(cola, pos):
    """Cuenta las personas de la cola desde la posición pos."""
    if pos == len(cola):
        return 0
    return 1 + contar_desde(cola, pos + 1)


def contar(cola):
    return contar_desde(cola, 0)


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

4

¿Recursivo o iterativo?

Todo lo que se hace con recursividad se puede hacer con bucles, y al revés. Entonces, ¿cuándo usar cada cosa?

Usa recursividad cuando…	Usa un bucle cuando…
El problema se define de forma recursiva (potencias, búsqueda binaria, estructuras anidadas)	El problema es un recorrido sencillo (sumar, contar, buscar en una lista)
La estructura es recursiva (listas encadenadas, listas de listas de profundidad variable)	La estructura es plana y puede ser muy larga
La profundidad es pequeña (por ejemplo, logarítmica)	La profundidad podría superar el límite de 1000 llamadas
La solución recursiva es mucho más clara	La solución con bucle es igual de clara

En Python, contar una cola o sumar una lista es más eficiente con un bucle (o con len y sum). La recursividad brilla cuando cada llamada divide el problema (búsqueda binaria, potencia rápida) o cuando la estructura anida datos dentro de datos, como verás en la práctica con un pedido de grupo lleno de subpedidos.

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 (frame) con sus propias variables: es la mejor forma de ver la pila de llamadas. Elige Python 3 y pega este programa:

def cuantos_delante(delante):
    if delante == []:
        return 0
    return 1 + cuantos_delante(delante[:-1])


cola = ["Ana", "Luis", "Marta"]
total = cuantos_delante(cola)
print(total)

Salida esperada:

3

Qué observar, paso a paso:

1. En la primera llamada aparece un marco cuantos_delante con delante = ["Ana", "Luis", "Marta"]. Al llegar al return 1 + …, la función no termina: aparece un segundo marco debajo.
2. Sigue avanzando: verás cuatro marcos apilados, cada uno con su propia delante (de tres nombres, de dos, de uno y vacía). Cuatro variables distintas con el mismo nombre.
3. En el cuarto marco, delante es [] y se cumple el caso base. Python Tutor muestra el Return value: 0 y ese marco desaparece.
4. Ahora mira la vuelta: el tercer marco recibe el 0 y devuelve 1, el segundo devuelve 2 y el primero devuelve 3. La pila se va vaciando en orden inverso al que se llenó.
5. Cuando el último marco termina, total vale 3 en el marco global y el print lo muestra.

Resumen

Concepto	Lo esencial
Recursividad	Una función que se llama a sí misma con una versión más pequeña del problema
Caso base	El caso que se resuelve sin llamadas recursivas; sin él, la recursión no termina
Caso general	Resuelve el problema combinando una llamada sobre algo más pequeño
Cuatro preguntas	Tamaño, cómo reducirlo, cuándo no se puede reducir, cómo combinar
Pila de llamadas	Cada llamada pendiente espera con sus propias variables; límite de 1000
RecursionError	Falta el caso base, no se alcanza o la recursión es demasiado profunda
Profundidad	Llamadas activas a la vez (memoria)
Número de llamadas	Llamadas en total (tiempo); repetir una llamada lo multiplica
Primero y resto	l[0] y l[1:]: el esquema de las funciones recursivas sobre listas
Búsqueda binaria	En una lista ordenada, descarta la mitad en cada llamada
Lista encadenada	Tuplas (valor, resto) que terminan en ()
Inmersión	Resolver un problema más general (con índices o acumuladores) y llamarlo desde el original

Tres ideas para llevarte:

1. Toda función recursiva tiene dos partes: un caso base que para y un caso general que se acerca a él. Si la llamada recursiva no recibe algo más pequeño, la función no terminará nunca.
2. Las llamadas se apilan y esperan. Lo que va antes de la llamada se ejecuta a la ida y lo que va después, a la vuelta. Seguir esa pila con una traza o con Python Tutor es la forma de entender cualquier función recursiva.
3. No todas las recursiones cuestan lo mismo. Dividir el problema por la mitad reduce la profundidad; no repetir llamadas reduce el trabajo; y la inmersión con índices evita copiar listas en cada llamada.

En la práctica de recursividad aplicarás todo esto a la cola del comedor, a una búsqueda de turnos con traza y a un pedido de grupo con subpedidos dentro. Después, los ejercicios te pondrán a prueba. Y en el siguiente tema llegan los contenedores asociativos: los diccionarios.

Siguiente paso: prácticaRecursividad 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)

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