La lección anterior terminó con dos deudas: la búsqueda binaria tenía una versión «más elegante» que no podíamos escribir, y el mergesort necesitaba ordenar dos mitades que son, a su vez, listas por ordenar. Las dos piden lo mismo, y es lo que aprenderás aquí: una función que se llama a sí misma.

La recursión desconcierta la primera vez porque parece un truco circular, y no lo es: es una forma distinta de descomponer problemas, complementaria de la descomposición en funciones de 04-04. En vez de partir el problema en subproblemas distintos, lo partes en versiones más pequeñas del mismo problema hasta llegar a un caso tan simple que se resuelve sin pensar. En esta lección la entenderás, la trazarás, descubrirás por qué en Python conviene desconfiar de ella, y la usarás en los tres sitios donde gana de calle.

1. La idea: cajas dentro de cajas
2. Las dos piezas obligatorias
3. La pila de llamadas y el RecursionError
4. Ejemplos progresivos con su traza
5. El árbol de llamadas: factorial y Fibonacci
6. Recursión frente a iteración
7. El coste oculto de la recursión ingenua
8. Memoización: recordar lo ya calculado
9. Donde la recursión sí gana
10. Búsqueda binaria recursiva y ordenación por mezcla
11. TareaFácil v0.14: días de un desglose anidado
12. Errores comunes y consejos
13. Ejercicios
14. Conclusión

Imagina que en el almacén de Estudio Alba te piden contar cuántos folios hay, y el almacén contiene cajas, algunas de las cuales contienen otras cajas. No necesitas un procedimiento distinto para cada nivel de profundidad. Necesitas una sola regla:

Para contar los folios de una caja: si dentro solo hay folios, cuéntalos. Si dentro hay otras cajas, cuenta los folios de cada una y suma los resultados.

Fíjate en lo que acabas de hacer: has definido «contar los folios de una caja» en términos de sí mismo, aplicado a algo más pequeño. Y funciona porque las cajas no son infinitas: tarde o temprano llegas a una que solo contiene folios y ahí paras. Lo mismo pasa con las muñecas rusas, con las carpetas dentro de carpetas del disco duro o con la definición de «antepasado»: tus padres, y los antepasados de tus padres. Esa es toda la recursión: una función recursiva se llama a sí misma con una versión más pequeña del problema, confiando en que esa llamada le devolverá la respuesta correcta.

Toda función recursiva tiene exactamente dos partes, y ninguna de las dos puede faltar:

Al escribir una función recursiva, hazte siempre las tres preguntas en este orden: ¿cuál es el caso más simple que sé resolver sin pensar? (ese es el base), ¿cómo reduzco el problema hacia ese caso? (esa es la llamada recursiva) y ¿qué hago con lo que me devuelva? (ese es el trabajo de este nivel). Y hay un requisito que va más allá de tener las dos piezas: el caso recursivo debe acercarse al base. cuenta_atras(n - 1) se acerca a cero; cuenta_atras(n) no se acerca a nada y se cuelga igual que si no hubiera caso base.

En 04-01 viste que cuando una función llama a otra, la primera espera a que la segunda termine. Python guarda cada llamada pendiente en la pila de llamadas, con sus variables y el punto exacto al que hay que volver. La recursión apila llamadas de la misma función:

La pila crece hasta el caso base y después se desapila en orden inverso. Eso tiene una consecuencia práctica de primer orden: cada llamada pendiente ocupa memoria. Python limita la profundidad a unas 1.000 llamadas y, si se supera, aborta con RecursionError: maximum recursion depth exceeded.

Ese RecursionError es, en realidad, una buena noticia: Python te avisa de un fallo lógico —falta el caso base o no te acercas a él— antes de agotar la memoria. Subir el límite existe, pero es casi siempre la respuesta equivocada: si tu recursión necesita más de mil niveles, lo que necesitas es un bucle.

Factorial. El factorial de n es el producto de los enteros de 1 a n, y su definición matemática ya es recursiva: n! = n × (n-1)!, con 0! = 1.

Traza de factorial(4); las primeras columnas son la ida, apilando llamadas, y la última es la vuelta, cuando cada nivel recibe su resultado y lo multiplica:

Lee la tabla de abajo arriba en la última columna y verás cómo se construye el resultado: 1, 2, 6, 24. Nada se calcula en la ida; todo el trabajo real ocurre al volver. El mismo esquema sirve sobre colecciones: la suma de una lista es su primer elemento más la suma del resto, y una cadena invertida es el resto invertido más su primer carácter.

valores[1:] es la rebanada de 05-01: «todos menos el primero». Cada llamada recibe una colección un elemento más corta, así que se acerca al caso base. Con [3, 5, 2] sale 3 + (5 + (2 + 0)), es decir, 10; y con "Alba", invertir("lba") + "A" → ("ab" + "l") + "A" → "ablA". En producción escribirías sum(valores) y texto[::-1]; esto es para ver la mecánica.

El factorial genera una cadena de llamadas: cada nivel llama una sola vez. Fibonacci —cada número es la suma de los dos anteriores, empezando por 0 y 1— genera un árbol, porque cada nivel llama dos veces:

Mira los nodos marcados: fib(3) se calcula dos veces y fib(2) tres veces, con todo su subárbol repetido cada vez. Y eso solo con n = 5. La diferencia entre las dos formas es total: el factorial hace n llamadas, Fibonacci hace aproximadamente el doble por cada unidad que sube n. Esa explosión es el asunto de la sección 7.

Todo lo que se puede escribir con recursión se puede escribir con un bucle, y al revés. La elección es de claridad y coste, no de posibilidad.

El factorial iterativo cabe en cuatro líneas —resultado = 1, un for i in range(2, n + 1) que hace resultado *= i, y un return— y es más rápido que el recursivo. La regla práctica en Python es sencilla y conviene tomársela en serio: prefiere iterar, salvo que el problema sea naturalmente recursivo. Y lo es cuando sus datos tienen forma de árbol —carpetas dentro de carpetas, diccionarios dentro de diccionarios, subtareas dentro de tareas— o cuando el algoritmo divide el problema en trozos que se resuelven igual, como el mergesort. Para recorrer, contar o acumular, el bucle gana siempre. Otros lenguajes (Scheme, Haskell, Erlang) optimizan cierto tipo de recursión para que no consuma pila, con una técnica llamada tail call optimization; Python no lo hace, deliberadamente, y esa es una razón más para desconfiar aquí de la recursión profunda.

El fibonacci de la sección 5 es correcto y es un desastre. Midámoslo con time.perf_counter(), como en 06-02, envolviendo la llamada entre dos lecturas del reloj y restándolas:

Cada cinco unidades de n el tiempo se multiplica por diez, y fib(50) tardaría más de una hora en calcular un número que cabe en una línea. El motivo está en el árbol de la sección 5: el algoritmo recalcula una y otra vez lo que ya había calculado; para fib(35) calcula fib(10) decenas de miles de veces obteniendo siempre lo mismo. Ojo, entonces: el problema no es la recursión, es el trabajo repetido, y la solución no es quitar la recursión sino dejar de repetir.

Memoizar es guardar el resultado de cada cálculo en un diccionario para no repetirlo. Es el intercambio tiempo-memoria de 06-01 en su forma más pura: gastamos memoria para no gastar tiempo.

El diccionario es la estructura perfecta para esto por lo que aprendiste en 06-01: consultar n in memoria es prácticamente instantáneo gracias a la tabla hash. Y fíjate en el memoria=None: nunca uses un diccionario o una lista vacíos como valor por defecto de un parámetro, porque Python los crea una sola vez al definir la función y se compartirían entre todas las llamadas. El efecto es espectacular: fibonacci_memo(35) pasa de 4 segundos a menos de una diezmilésima, porque cada fib(k) se calcula una sola vez y el árbol se convierte en una cadena. Python trae esto hecho en un decorador de la biblioteca estándar:

Esa línea que empieza por @ es un decorador: una anotación que envuelve la función y le añade comportamiento —aquí, la memoria de resultados— sin tocar su código. No los estudiaremos en este curso; quédate con que @lru_cache es la forma profesional de memoizar, con que fibonacci_rapido.cache_info() informa de sus aciertos, y con que solo funciona si los argumentos son inmutables (números, textos, tuplas), porque los usa como claves de un diccionario.

Hasta aquí la recursión ha quedado como una versión bonita y más lenta del bucle. Cambia por completo cuando los datos tienen forma de árbol, porque entonces un bucle no basta: harían falta tantos bucles anidados como niveles, y no sabes cuántos hay. Retomemos el diccionario de diccionarios de 05-04, ahora con profundidad desconocida:

El caso base es «esto ya no contiene nada dentro»; el caso recursivo es «para cada cosa que hay dentro, repite». El parámetro nivel no dirige la recursión, solo lleva la cuenta del sangrado: es un patrón habitual, pasar información hacia abajo. Y isinstance(x, dict) es imprescindible porque no sabemos qué nos vamos a encontrar en cada nivel. El mismo esquema recorre carpetas de disco; pathlib (05-05) ya trae el recorrido recursivo con rglob, pero escribirlo enseña la estructura:

Aquí la recursión no es una elección estética: es la única forma razonable de hacerlo, porque nadie sabe cuántos niveles de carpetas hay. Y el caso base no es un if al principio, sino la situación natural en que la carpeta no contiene subcarpetas y el for no llama a nadie.

Lo prometido en 06-01: la búsqueda binaria es naturalmente recursiva, porque «buscar en este trozo» es el mismo problema que «buscar en la mitad de este trozo».

Compárala con la versión iterativa de 06-01 y verás la traducción exacta: el while se ha convertido en la llamada recursiva y la condición de salida izquierda <= derecha en el caso base izquierda > derecha, invertida. Los parámetros por defecto (04-02) permiten llamarla como binaria_recursiva(codigos, 170) sin pasar los límites. Trazando la búsqueda de 170 en [102, 118, 134, 156, 170, 189, 203, 240]:

¿Cuál es mejor? La iterativa, en Python, porque hace lo mismo sin consumir pila; la recursiva se lee mejor y es la que verás en los libros. Y en producción, ni una ni otra: bisect.

Lo prometido en 06-02, y el ejemplo canónico de divide y vencerás: partir la lista por la mitad, ordenar cada mitad recursivamente y fusionar las dos mitades ya ordenadas.

mezclar es la pieza no recursiva y la más importante: recorre las dos listas en paralelo con dos índices, cogiendo siempre el menor de los dos frentes, en una sola pasada. Ese <= en lugar de < es lo que hace estable al algoritmo: ante un empate coge el de la izquierda, que venía antes. Y la última línea añade lo que quede sin recorrer de una de las dos listas, que por construcción ya está ordenado. Traza de mergesort([3, 5, 2, 4]):

La lista se parte por la mitad hasta llegar a trozos de un elemento —que están ordenados por definición— y después se reconstruye fusionando. Con 1.000 elementos hay unos 10 niveles de división y cada nivel cuesta una pasada completa: unas 10.000 operaciones, frente al millón de la burbuja. Esa es la diferencia que veías en la tabla de tiempos de 06-02, y Timsort usa exactamente esta función mezclar para unir los tramos que ordena con inserción.

Marta ha empezado a desglosar los encargos grandes en subtareas, y estas a su vez en subtareas más pequeñas, sin un número fijo de niveles, y necesita saber cuántos días suma un proyecto entero. Es el caso de la sección 9, y solo se resuelve bien con recursión.

Salida por pantalla, donde cada rama muestra su propio total: Identidad Panaderia Sole 10d, y dentro Logotipo 3d (con Bocetos 2d y Vectorizado 1d sangradas debajo), Papeleria 3d y Rotulo del local 4d. Tres observaciones sobre este código:

• El caso base no es un if. Cuando subtareas está vacía, el for no se ejecuta ninguna vez y la función devuelve directamente tarea["dias"]. Es la forma más limpia de escribir el caso base al recorrer una colección: la lista vacía lo es por sí misma.
• La estructura de datos y el algoritmo encajan. Cada nodo tiene la misma forma —nombre, dias, subtareas—, sea la raíz o la última hoja, y por eso la misma función sirve para todos los niveles: diseñar los datos con esa uniformidad es lo que hace posible la recursión. Y así ninguna de las dos funciones sabe cuántos niveles hay, que es exactamente lo que se pedía; con bucles anidados habría que fijar de antemano una profundidad máxima. Y ojo: mostrar_desglose recalcula el total de cada rama, repitiendo trabajo igual que Fibonacci. Con tres niveles es irrelevante; si el desglose creciera, tocaría memoizar.

Olvidar el caso base o no acercarse a él. Los dos síntomas son el mismo RecursionError. Comprueba que existe un if que devuelve sin llamarse y que el argumento de la llamada recursiva está más cerca de ese caso en cada paso. Y olvidar el return delante de la llamada recursiva. factorial(n - 1) sin return calcula el resultado y lo tira; la función devuelve None y al multiplicar salta TypeError. En una función recursiva que devuelve un valor, casi todas las ramas llevan return.

Usar {} o [] como valor por defecto de un parámetro, típico al memoizar. Python crea ese objeto una sola vez y lo comparte entre todas las llamadas: los resultados de una consulta contaminan la siguiente. Usa None y créalo dentro. Y cuidado con la recursión sobre listas con rebanadas: suma(valores[1:]) copia la lista entera en cada llamada, así que sumar 1.000 números copia medio millón de elementos; para colecciones grandes, pasa índices o usa un bucle.

Consejo: confía en la llamada recursiva. El error de aprendizaje más común es intentar seguir mentalmente todos los niveles. No lo hagas: da por bueno que factorial(n - 1) devuelve el factorial correcto y limítate a comprobar el caso base y el paso. Si ambos están bien, la función está bien. Y si dudas, dibuja el árbol: tres niveles en papel bastan para ver si el problema se reduce y si hay trabajo repetido, como el de Fibonacci. Es la prueba de escritorio de 01-05 aplicada a la recursión.

Traza suma([4, 1, 6]) indicando en una tabla cada llamada, a qué espera y qué devuelve. Después, dibuja el árbol de llamadas de fibonacci(4) y cuenta cuántas veces se calcula fibonacci(2). Por último, explica qué imprime cuenta_atras(2) si intercambias las dos últimas líneas del cuerpo de la función.

Sobre la estructura de subtareas del apartado 11, escribe dos funciones recursivas: contar_hojas(tarea), que devuelve cuántas subtareas sin subtareas propias hay en toda la rama (las hojas del árbol, es decir, el trabajo real); y tarea_mas_larga(tarea), que devuelve el nombre de la hoja con más días de toda la rama.

Escribe potencia(base, exponente) recursiva que calcule base ** exponente sin usar el operador **, con esta propiedad: si el exponente es par, base^n = (base^(n/2))²; si es impar, base^n = base × base^(n-1). Compara cuántas llamadas hace, con exponente = 16, frente a la versión que resta uno al exponente cada vez.

Solución 1. Traza de suma([4, 1, 6]):

En el árbol de fibonacci(4), fibonacci(2) se calcula dos veces: una colgando de fib(3) y otra directamente de fib(4). Y si en cuenta_atras se intercambian el print(n) y la llamada recursiva, la cuenta sale al revés: primero Ya! y después 1, 2. El motivo es el de la sección 4: lo que va antes de la llamada se ejecuta en la ida y lo que va después, en la vuelta.

Solución 2.

contar_hojas distingue explícitamente la hoja —que vale 1— de la rama, que vale la suma de sus hijas. tarea_mas_larga usa un truco importante: devuelve una tupla (nombre, dias) en vez de solo el nombre, porque para comparar candidatas en el nivel superior hacen falta los días. Es el «devolver varios valores» de 04-02 al servicio de la recursión: cada nivel devuelve lo que el nivel de arriba necesita para decidir.

Solución 3.

La clave está en mitad = potencia(base, exponente // 2) guardada en una variable: si escribieras potencia(...) * potencia(...) calcularías dos veces lo mismo y volverías al problema de Fibonacci. Con exponente 16 el reparto es 16 → 8 → 4 → 2 → 1 → 0: cinco llamadas, frente a las diecisiete de la versión que resta uno cada vez. Es la misma idea de dividir entre dos de la búsqueda binaria y del mergesort, aplicada a la aritmética; en Python, por supuesto, se escribe base ** exponente.

Una función recursiva se llama a sí misma con una versión más pequeña del mismo problema, y solo funciona si tiene sus dos piezas: un caso base que devuelve sin llamarse y un caso recursivo que se acerca a él. Cada llamada pendiente vive en la pila de llamadas, que Python limita a unos mil niveles antes de lanzar RecursionError; subir el límite con sys.setrecursionlimit casi nunca es la solución correcta. En la ida se apilan las llamadas y en la vuelta se construye el resultado, como muestran las trazas del factorial, la suma de una lista y la inversión de una cadena. El factorial genera una cadena de llamadas y Fibonacci un árbol, y ahí está la trampa: el Fibonacci ingenuo repite tanto trabajo que fib(40) tarda cuarenta y cinco segundos. La cura no es abandonar la recursión sino dejar de repetir, con memoización —un diccionario de resultados ya calculados, o el decorador @lru_cache—, que es el intercambio tiempo-memoria en estado puro. Frente a la iteración, la recursión pierde en memoria y velocidad y gana en claridad cuando los datos tienen forma de árbol (estructuras anidadas, carpetas de disco, desgloses de subtareas) o cuando el algoritmo divide el problema: la búsqueda binaria recursiva prometida en 06-01 y el mergesort prometido en 06-02, cuya función mezclar recorre dos listas ordenadas en una sola pasada y es la misma que usa Timsort. TareaFácil llega a la v0.14 y calcula los días de un proyecto desglosado en subtareas a cualquier profundidad.

Con esto tienes todas las piezas del módulo, y también un montón de afirmaciones sueltas que hemos ido haciendo sin poder demostrarlas: «veinte comparaciones frente a un millón», «doblar los datos cuadruplica el trabajo», «el árbol se convierte en una cadena», «esto es un intercambio tiempo-memoria». Todas describen lo mismo —cuánto cuesta un programa según el tamaño de sus datos— y todas piden un vocabulario preciso. En Eficiencia y notación Big-O lo tendrás por fin, y con él podrás mirar cualquier función y decir en voz alta cuánto va a costar antes de ejecutarla.